排序算法小结
排序算法
1、选择排序
算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
时间复杂度：O(n^2）
// 选择排序 function selectSort(array) { if (!array || array.length <= 0) { return array } const len = array.length; for (let i = 0; i < len - 1; i++) { let minIndex = i; for (let j = i + 1; j < len; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } let temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; selectSort(array) console.log('selectSort result', array) 复制代码2、冒泡排序
算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
时间复杂度：O(n^2）
function bubbleSort(array) { if (!array || array.length <= 0) { return array; } let len = array.length; for(i = 0; i < len - 1; i++) { for(let j = 0; j < len - 1 - i; j++) { if (array[j] > array[j + 1]) { let temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; bubbleSort(array) console.log('bubbleSort result', array) 复制代码3、快速排序
算法步骤
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
时间复杂度：O(n logn) （最坏情况O(n^2））
function quickSort(array, l, r) { if (l < r) { let i = l; let j = r; let x = array[i]; while(i < j) { while(i < j && x < array[j]) { j--; } if (i < j) { array[i] = array[j] i++; } while(i < j && array[i] < x) { i++; } if (i < j) { array[j] = array[i] j--; } } array[i] = x; quickSort(array, l, i - 1) quickSort(array, i + 1, r) } } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; quickSort(array, 0, array.length - 1) console.log('quickSort result', array) 复制代码4、插入排序
算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
时间复杂度：O(n) ~ O(n^2)
function insertSort(array) { if (!array || array.length <= 0) { return array; } let len = array.length; for (let i = 1; i < len; i++) { let x = array[i]; let j = i for (; j >= 1 && array[j - 1] > x; j--) { array[j] = array[j - 1] } array[j] = x; } } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; insertSort(array) console.log('insertSort result', array) 复制代码5、希尔排序
算法思想：希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”是直接插入排序算法的一种更高效的改进版本。
时间复杂度：O(n) ~ O(n^2)
function shellSort(array) { if (!array || array.length <= 0) { return array; } let len = array.length; for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) { for (let i = gap; i < len; i++) { let x = array[i]; let j = i; for (; j >= gap && x < array[j - gap]; j -= gap) { array[j] = array[j - gap]; } array[j] = x } } } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; shellSort(array) console.log('shellSort result', array) 复制代码6、计数排序
算法步骤
（1）找出待排序的数组中最大和最小的元素
（2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
（3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
（4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
时间复杂度：Ο(n+k) （其中k是整数的范围）
function countSort(array) { if (!array || array.length <= 0) { return array; } let len = array.length let countArray = [] for (let i = 0; i < len; i++) { if (countArray[array[i]]) { countArray[array[i]]++ } else { countArray[array[i]] = 1 } } let resArray = [] for (let i = 0; i < countArray.length; i++) { while(countArray[i]) { resArray.push(i) countArray[i]-- } } return resArray } const array = [6, 7, 8, 9, 0, 5, 4, 3, 2, 1]; const arrayRes = countSort(array) console.log('countSort result', arrayRes)
作者：Alwayslinzx
链接：https://juejin.cn/post/7026732501817098277