虽然我们有了Array.prototype.sort()
,但是要知其所以然。
Sedgewick在《算法中提到了》学习排序算法的意义:
对排序算法的分析有助于全面理解算法性能的不计较
类似的技术也能有效解决其他类型的问题
排序算法往往是解决其他问题的第一步
辅助工具 为了方便算法的比较与测试,封装常用方法至utils.js
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 module .exports = { makeNum(size, max) { let out = [] for (let i = 0 ; i < size; i++) { let n = 1 + Math .floor(Math .random() * max) out.push(n) } console .log(`生成的数组为:${out} ` ) return out }, exchange(arr, pos1, pos2) { let temp = arr[pos1] arr[pos1] = arr[pos2] arr[pos2] = temp } }
如果可以,尽可能在原数组上交换,而不是开辟新的数组,以减少内存耗费
选择排序 选择排序的核心思想是极简的,即外循环从头逐位向后推进中,内循环从外循环头部之后找到一个最小的元素 跟头部元素交换,如此进行下去。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 const utils = require ('./utils' )function selectSort (arr ) { let len = arr.length, times = 0 console .time('选择排序' ) for (let i = 0 ; i < len; i++) { let min = i for (let j = i + 1 ; j < len; j++) { if (arr[j] < arr[min]) { exchage(arr, j, min) } } } console .timeEnd('选择排序' ) return arr }
插入排序 插入排序的思想类似于打扑克牌,从头开始,异次挑外循环元素进内循环中对比,直到该元素在内循环中插入到合适的位置。对比过程中该元素可能不断向左。插入排序常数性快与选择排序。
1 2 3 4 5 6 7 8 9 10 11 12 function insertSort (arr ) { let len = arr.length, times = 0 for (let i = 0 ; i < len; i++) { for (let j = i; j > 0 && arr[j] < arr[j - 1 ]; j--) { utils.exchage(arr, j, j - 1 ) times++ console .log(`第${times} 次修改,数组为${arr} ` ) } } return arr }
希尔排序 希尔排序是插入排序的带间隔翻版,核心思想是以固定间隔分隔数组,在分隔出的子数组中应用插入排序。一轮之后,再缩小间隔继续排序,直到间隔为1。
经本人测试,希尔排序在随机自然数列的排序中快过Array.prototype.sort()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function shellSort (arr ) { let len = arr.length, gap = 1 console .time('希尔排序' ) while (gap < len / 3 ) { gap = gap * 3 + 1 } while (gap >= 1 ) { for (let i = gap; i < len; i++) { for (let j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) { utils.exchange(arr, j, j - gap) } } gap = Math .floor(gap / 3 ) } console .timeEnd('希尔排序' ) return arr }
归并排序 归并排序在牺牲了一定内存(使用了辅助数列)的情况下,实现了时间复杂度为(NlgN),是一种稳健的排序方法。其核心是使用分治 的思想,递归地将大问题化小,用小问题的答案解决大问题。而归并排序另外一个问题在于引入了递归,会受到常规语言的调用栈限制(如chrome67,V8引擎:约13000次)。
下面先给出实现,为了理解其分治的过程,打印过程以便观察
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 const utils = require ('./utils' )function mergeSort (arr ) { console .log(`slice:[${arr} ]` ) let len = arr.length if (len < 2 ) { return arr } let mid = Math .floor(len / 2 ), left = arr.slice(0 , mid), right = arr.slice(mid) return sort(mergeSort(left), mergeSort(right)) } function sort (left, right ) { console .log(`sortLeft:[${left} ],sortRight:[${right} ]` ) let result = [] while (left.length && right.length) { let item = (left[0 ] <= right[0 ]) ? left.shift() : right.shift() result.push(item) } return result.concat(left.length ? left : right) } let a = utils.makeNum(5 , 100 )console .log(mergeSort(a))
输出如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 > node merge.js 生成的数组为:9,21,65,77,55 slice:[9,21,65,77,55] slice:[9,21] slice:[9] slice:[21] sortLeft:[9],sortRight:[21] slice:[65,77,55] slice:[65] slice:[77,55] slice:[77] slice:[55] sortLeft:[77],sortRight:[55] sortLeft:[65],sortRight:[55,77] sortLeft:[9,21],sortRight:[55,65,77] [ 9, 21, 55, 65, 77 ]
可以看到,开始算法先对数组切分,产生一个以原数组为根的树形结构,树枝粒度为1。以深度优先的方式触底,返回后进入Sort环节进行排序操作,得到有序的大数组,最后汇聚成有序的数组。
快速排序 快速排序应该是当今使用最广泛的一种排序。顾名思义,其效率高,且占用内存少。其内循环小于绝大多数算法。类似于归并排序,其核心思想依然为分治 。简要的说就是选数组中任意一点进行分割(partition) ,然后将大于该点值得元素放置于元素左边,小于的放于右边。
归并排序:递归调用发生在处理整个数组之前
快速排序:递归调用发生在处理整个数组之后
快速排序的代码如下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 const utils = require ('./utils' )function quick (arr, lo, hi ) { var lo = typeof lo === 'number' ? lo : 0 , hi = typeof hi === 'number' ? hi : arr.length -1 , index if (lo < hi) { index = partition(arr, lo, hi) quick(arr, lo, index - 1 ) quick(arr, index + 1 , hi) } return arr } function partition (arr, lo, hi ) { var pivot = lo for (var i = lo + 1 ; i <= hi; i++) { arr[i] < arr[lo] && utils.exchange(arr, i, ++pivot) } utils.exchange(arr, pivot, lo) return pivot }
各种排序算法的比较 在熟知各种算法的优缺点后,我们可以根据实际问题的需要选择最合适的排序算法。其中考量点包括问题规模,数组有序程度以及空间限制等等。
算法
时间复杂度
最好
最坏
空间复杂度
稳定性*
选择
O(n^2)
O(n^2)
O(n^2)
1
不稳定
冒泡
O(n^2)
O(n)
O(n^2)
1
稳定
插入
O(n^2)
O(n)
O(n^2)
1
稳定
希尔
不确定
O(n)
O(n^2)
1
不稳定
归并
O(nlogn)
O(nlogn)
O(nlogn)
N
稳定
快速
O(nlogn)
O(nlogn)
O(n^2)
lgN
不稳定
堆
O(nlogn)
O(nlogn)
O(nlogn)
1
不稳定
*注:稳定性指在排序完成后,值相等的两个元素会不会改变相对位置,若改变则为不稳定。反之稳定。