十大经典算法（优化篇）

super1

<hr/>title: 十大经典算法-优化篇 date: 2019-01-01 15:06:09 tags:
<hr/>算法，一个算法的优劣可以用空间复杂度和时间复杂度来衡量。


来看已经总结的算法：


(n：数据规模 k：“桶”的个数 In-place：占用常熟内存 Out-place：占用额外内存)
冒泡排序（Bubble Sort）

可能网上大部分是C语言来实现的，我们这里用JavaScript写，并且加上执行时间来看看
// 冒泡排序
// v1
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function bubbleSort1(arr) {
  console.time('冒泡v1耗时：')
  var len = arr.length - 1
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        var temp = arr[j+1]
        arr[j+1] = arr[j]
        arr[j] = temp
      }
    }
  }
  console.timeEnd('冒泡v1耗时：')
  return arr
}
console.log(bubbleSort1(arr))
冒泡v1耗时：: 0.608ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
优化
// 冒泡排序v2
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
// 冒泡排序v2
function bubbleSort2(arr) {
  console.time('冒泡v2耗时：')
  var len = arr.length - 1
  while (len > 0) {
    var pos = 0
    for (var j = 0; j < len; j++) {
      if (arr[j] > arr[j+1]) {
        pos = j
        var temp = arr[j]
        arr[j] = arr[j+1]
        arr[j+1] = temp
      }
      len = pos
    }
  }
  console.timeEnd('冒泡v2耗时：')
  return arr
}
console.log(bubbleSort2(arr))
冒泡v2耗时：: 0.159ms
[ 2, 54, 58, 56, 48, 12, 69, 87, 85, 94 ]
测试版
// 冒泡排序v3
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function bubbleSort3(arr) {
  var low = 0
  var high = arr.length - 1
  var temp,j
  console.time('冒泡v3耗时：')
  while (low < high) {
    for (j = low; j < high; ++j) {
      if (arr[j] > arr[j+1]) {
        temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp
      }
    }
    --high
    for (j = high; j > low; --j) {
      if (arr[j] < arr[j-1]) {
        temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp
      }
    }
    ++low
  }
  console.timeEnd('冒泡v3耗时：')
  return arr
}
console.log(bubbleSort3(arr))
冒泡v3耗时：: 0.463ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
选择排序

// 选择排序
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function selectionSort(arr) {
  var len = arr.length
  var minIndex, temp
  console.time('选择耗时：')
  for (var i = 0; i < len - 1; i++) {
    minIndex = i
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    temp = arr
    arr = arr[minIndex]
    arr[minIndex] = temp
  }
  console.timeEnd('选择耗时：')
  return arr
}
console.log(selectionSort(arr))
选择耗时：: 0.551ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
插入排序

// 插入排序
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function insertionSort(array) {
  if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
    console.time('插入耗时：')
    for (var i = 1; i < array.length; i++) {
      var key = array
      var j = i - 1
      while (j >= 0 && array[j] > key) {
        array[j + 1] = array[j]
        j--
      }
      array[j + 1] = key
    }
    console.timeEnd('插入耗时：')
    return array
  } else {
    return 'array is not an Array'
  }
}
console.log(insertionSort(arr))
插入耗时：: 0.615ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
查找插入位置时使用二分查找
// 插入排序v2 查找插入位置时使用二分查找
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function insertionSort2(array) {
  if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
    console.time('二分插入耗时：')
    for (var i = 1; i < array.length; i++) {
      var key = array, left = 0, right = i - 1
      while (left <= right) {
        var middle = parseInt((left + right) / 2)
        if (key < array[middle]) {
          right = middle - 1
        } else {
          left = middle + 1
        }
      }
      for (var j = i - 1; j >= left; j--) {
        array[j + 1] = array[j]
      }
      array[left] = key
    }
    console.timeEnd('二分插入耗时：')
    return array
  } else {
    return 'array is not an Array'
  }
}
console.log(insertionSort2(arr))
二分插入耗时：: 0.601ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
希尔排序

// 希尔排序
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function shellSort(arr) {
  var len = arr.length,
      temp,
      gap = 1
  console.time('希尔排序耗时:')
  while (gap < len/5) {          //动态定义间隔序列
      gap =gap*5+1
  }
  for (gap; gap > 0; gap = Math.floor(gap/5)) {
      for (var i = gap; i < len; i++) {
          temp = arr
          for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
              arr[j+gap] = arr[j]
          }
          arr[j+gap] = temp
      }
  }
  console.timeEnd('希尔排序耗时:')
  return arr
}
console.log(shellSort(arr))
希尔排序耗时:: 0.658ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
归并排序

递归
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
console.log(mergeSort(arr))
function merge(left, right) {
  var tmp = []
  console.time('归并耗时：')
  while (left.length && right.length) {
    if (left[0] < right[0])
      tmp.push(left.shift())
    else
      tmp.push(right.shift())
  }
  console.timeEnd('归并耗时：')
  return tmp.concat(left, right)// 合并数组
}
function mergeSort(a) {
  if (a.length === 1) {
    return a
  }
  var mid = Math.floor(a.length / 2)
  var left = a.slice(0, mid)
  var right = a.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}
如果在数组很大的情况下，自调用会发生栈溢出的错误。
迭代
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
console.log(mergeSort2(arr))
function merge (left, rigth) {
  var result = []
  while (left.length && rigth.length) {
    if (left[0] <= rigth[0]) {
      result.push(left.shift())
    } else {
      result.push(rigth.shift())
    }
  }
  return result.concat(left, rigth)
}
function mergeSort2 (arr) {
  if (arr.length === 1) {
    return arr
  }
  var work = []
  for (var i = 0, len = arr.length; i < len; i++) {
    work.push([arr])
  }
  work.push([])
  for (var lim = len; lim > 1; lim = Math.floor((lim + 1) / 2)) {
    for (var j = 0, k = 0; k < lim; j++, k += 2) {
      work[j] = merge(work[k], work[k + 1])
    }
    work[j] = []
  }
  return work[0]
}快速排序

快排2
// 快排2
var arr = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94, 56, 85, 74, 25, 46]
console.log(quickSort2(arr))

function quickSort2(arr) {
  console.time('快排耗时：')
  if (arr.length <= 1) {
    return arr
  }
  var pivotIndex = Math.floor(arr.length / 2)
  var pivot = arr.splice(pivotIndex, 1)[0]
  var left = []
  var right = []
  for (var i = 0; i < arr.length; i++) {
    if (arr < pivot) {
      left.push(arr)
    } else {
      right.push(arr)
    }
  }
  console.timeEnd('快排耗时：')
  return quickSort2(left).concat([pivot], quickSort2(right))
}
快排耗时：: 0.375ms
快排耗时：: 0.041ms
快排耗时：: 0.009ms
快排耗时：: 0.008ms
快排耗时：: 0.006ms
快排耗时：: 0.005ms
快排耗时：: 0.006ms
快排耗时：: 0.005ms
[ 2, 12, 25, 46, 48, 54, 56, 56, 58, 69, 74, 85, 85, 87, 94 ]
待续。。。


参考博客：
   https://blog.csdn.net/qq_40803710/article/details/80642703