十大经典算法（优化篇）

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 = [2, 54, 58, 56, 48, 12, 69, 87, 85, 94]
function bubbleSort1(arr) {
  console.time(&#39;冒泡v1耗时：&#39;)
  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(&#39;冒泡v1耗时：&#39;)
  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(&#39;冒泡v2耗时：&#39;)
  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(&#39;冒泡v2耗时：&#39;)
  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(&#39;冒泡v3耗时：&#39;)
  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(&#39;冒泡v3耗时：&#39;)
  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(&#39;选择耗时：&#39;)
  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(&#39;选择耗时：&#39;)
  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) === &#39;Array&#39;) {
console.time(&#39;插入耗时：&#39;)
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(&#39;插入耗时：&#39;)
return array
  } else {
return &#39;array is not an Array&#39;
  }
}
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) === &#39;Array&#39;) {
console.time(&#39;二分插入耗时：&#39;)
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(&#39;二分插入耗时：&#39;)
return array
  } else {
return &#39;array is not an Array&#39;
  }
}
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(&#39;希尔排序耗时:&#39;)
  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(&#39;希尔排序耗时:&#39;)
  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(&#39;归并耗时：&#39;)
  while (left.length && right.length) {
if (left[0] < right[0])
   tmp.push(left.shift())
else
   tmp.push(right.shift())
  }
  console.timeEnd(&#39;归并耗时：&#39;)
  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(&#39;快排耗时：&#39;)
  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(&#39;快排耗时：&#39;)
  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

		自动登录	找回密码
密码			立即注册

十大经典算法（优化篇）

本帖子中包含更多资源