选择排序
选择排序：找下标0-N-1上的最小值，将最小值下标与0位置交换。循环依次确定下标1、下标2的值。
function selectSort(arr) { for (let i = 0; i < arr.length; i++) { let minIndex = i for (let j = i + 1; j < arr.length; j++) { minIndex = arr[minIndex] > arr[j] ? j : minIndex } let temp = arr[i] arr[i] = arr[minIndex] arr[minIndex] = temp } return arr }
冒泡排序
两两比较，大的放后面,小的放前面。每次先确定最后一个。
function bubbleSort(arr) { for (let i = 0; i < arr.length - 1; i++) { for (let j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp } } } return arr }
插入排序
第一次循环，0-1内有序；第二次循环，0-2内有序。。。
function insertSort(arr) { if (arr.length < 2) return for (let i = 1; i < arr.length; i++) { for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { // let temp = arr[j] // arr[j] = arr[j + 1] // arr[j + 1] = temp swap(arr, j, j + 1) } } return arr } // 异或运算 只能两个不同位置的内存区域交换，否则自己和自己交换会变成0 function swap(arr, i, j) { arr[i] = arr[i] ^ arr[j] arr[j] = arr[i] ^ arr[j] arr[i] = arr[i] ^ arr[j] }
归并排序
将一个数组l-mid上有序， mid--r上有序，最后合并两个。
核心方法：定义一个辅助数组，两个指针，分别从左数组、右数组开始。比较，把最小的放到辅助数组中。
function mergeSort1(arr) { if (arr === null || arr.length < 2) return arr process(arr, 0, arr.length - 1) return arr } function process(arr, l, r) { if (l === r) return let mid = l + Math.floor((r - l) >> 1) process(arr, l, mid) process(arr, mid + 1, r) merge(arr, l, mid, r) } function merge(arr, l, mid, r) { let p1 = l, p2 = mid + 1 let h = [], index = 0 while (p1 <= mid && p2 <= r) { h[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++] } while (p1 <= mid) { h[index++] = arr[p1++] } while (p2 <= r) { h[index++] = arr[p2++] } for (let i = 0; i < h.length; i++) { arr[l + i] = h[i] } }
快速排序
快排的核心就是把比某个数小的放到左边，大的放到右边，相等的在中间。
在此，介绍的是随机快排。 随机获取数组中的一个数，把它作为基准，与最后的交换，把基准数放到最后。划分小于区域、大于区域。
- 比这个数大的就交换，大区域前进一步,停留当前下标继续比较
- 相等的继续下一步，
- 小于， 小区域前进一步,继续执行下一步
function quickSort3(arr) { if (arr.length < 2 || arr === null) return arr return randomProcess(arr, 0, arr.length - 1) } function randomProcess(arr, l, r) { if (l >= r) return let m = netherlandsFlag2(arr, l, r) randomProcess(arr, l, m.l - 1) randomProcess(arr, m.r + 1, r) return arr } function netherlandsFlag2(arr, l, r) { if (l > r) return { l: -1, r: -1 } if (l === r) return { l, r } let less = l - 1, more = r, index = l let random = Math.floor(Math.random() * (r - l + 1) + l) let m = arr[random] swap3(arr, random, r) while (index < more) { if (arr[index] > m) { swap3(arr, index, --more) } else if (arr[index] < m) { swap3(arr, ++less, index++) } else { index++ } } swap3(arr, more, r) // console.log(m, arr, less, more) return { l: less + 1, r: more } } function swap3(arr, i, j) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp }
堆排序
思路：数组先变成大根堆。把堆顶和最后一个值交换，减少堆的大小，再排成大根堆，周而复始直到堆的小为0。
在循环时，可以使用heapInsert或者heapify。但是heapify方法在循环中，中的事件复杂度为O（nlogn）。
上升： 将刚要插入的节点与父节点相比 子节点大就交换，下标跑到父节点处，再与它的父节点相比。直到堆顶。
下沉：父节点与子节点比较，子节点取最大的，最大子节点和父节点相比，父节点大break，子节点大交换。将最大值得节点放到父节点上，下标跑到最大值节点处。继续比较，直到left超过堆长度。
function heapSort(arr) { if (arr === null || arr.length < 2) return arr for (let i = arr.length - 1; i >= 0; i--) { heapify(arr, i, arr.length) } let heapSize = arr.length swap(arr, 0, --heapSize) while (heapSize > 0) { heapify(arr, 0, heapSize) swap(arr, 0, --heapSize) } return arr } // 上升 function heapInsert(arr, index) { while (arr[index] > arr[Math.floor((index - 1) >> 1)]) { swap(arr, index, Math.floor((index - 1) >> 1)) index = Math.floor((index - 1) >> 1) } } // 下沉 function heapify(arr, index, heapSize) { let left = (index << 1) + 1 while (left < heapSize) { let largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left largest = arr[index] > arr[largest] ? index : largest if (largest === index) break swap(arr, index, largest) index = largest left = (index << 1) + 1 } } function swap(arr, i, j) { let temp = arr[i] arr[i] = arr[j] arr[j] = temp }
稳定性与时间、额外空间复杂度比较
稳定性：相等的数在排序后仍然保持排序前的相对顺序
- 时间复杂度O(n^2)
- 选择排序，不稳定 额外空间复杂度O(1)
- 冒泡排序，稳定 额外空间复杂度O(1)
- 插入排序，稳定 额外空间复杂度O(1)
- 时间复杂度O(nlogn)
- 归并排序，（相等时先拷贝左边的稳定） 额外空间复杂度O(nlogn)
- 快速排序，不稳定（划分小中大） 额外空间复杂度O(nlogn)
- 堆排序，不稳定 额外空间复杂度O(nlogn)
- 希尔排序，不稳定
三个排序，归并较稳定，快排速度快，堆排序空间少
计数排序 O(n) 额外空间复杂度O(M) 基数排序 O(n) 额外空间复杂度O(n)
总结
- 不基于比较的排序，对样本数据有严格要求，不易改写
- 基于比较的排序只要规定好两个样本怎么比较大小就直接可以复用
- 基于比较排序的时间复杂度极限是O(nlogn)
- 时间复杂度O(nlogn)、额外空间复杂度低于O(N)、且稳定的基于比较排序是不存在的
- 归并较稳定，快排速度快，堆排序空间少
作者：ClyingDeng
链接：https://juejin.cn/post/6976624204821037087
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
