super1 发表于 2021-7-3 21:57

十大经典算法（优化篇）

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


来看已经总结的算法：


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

可能网上大部分是C语言来实现的，我们这里用JavaScript写，并且加上执行时间来看看
// 冒泡排序
// v1
var arr =
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 > arr) {
      var temp = arr
      arr = arr
      arr = 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 =
// 冒泡排序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 > arr) {
      pos = j
      var temp = arr
      arr = arr
      arr = 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 =
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 > arr) {
      temp = arr; arr = arr; arr = temp
      }
    }
    --high
    for (j = high; j > low; --j) {
      if (arr < arr) {
      temp = arr; arr = arr; arr = 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 =
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 < arr) {
      minIndex = j
      }
    }
    temp = arr
    arr = arr
    arr = temp
}
console.timeEnd('选择耗时：')
return arr
}
console.log(selectionSort(arr))
选择耗时：: 0.551ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
插入排序

// 插入排序
var arr =
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 > key) {
      array = array
      j--
      }
      array = 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 =
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) {
          right = middle - 1
      } else {
          left = middle + 1
      }
      }
      for (var j = i - 1; j >= left; j--) {
      array = array
      }
      array = 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 =
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 > temp; j-=gap) {
            arr = arr
          }
          arr = temp
      }
}
console.timeEnd('希尔排序耗时:')
return arr
}
console.log(shellSort(arr))
希尔排序耗时:: 0.658ms
[ 2, 12, 48, 54, 56, 58, 69, 85, 87, 94 ]
归并排序

递归
var arr =
console.log(mergeSort(arr))
function merge(left, right) {
var tmp = []
console.time('归并耗时：')
while (left.length && right.length) {
    if (left < right)
      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 =
console.log(mergeSort2(arr))
function merge (left, rigth) {
var result = []
while (left.length && rigth.length) {
    if (left <= rigth) {
      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(])
}
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 = merge(work, work)
    }
    work = []
}
return work
}快速排序

快排2
// 快排2
var arr =
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)
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(, 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
页: [1]
查看完整版本: 十大经典算法（优化篇）