function binaryInsertionSort(array){ var current, i, j, low, high, m; for(i = 1; i < array.length; i++){ low = 0; high = i - 1; current = array[i]; while(low <= high){ //步骤1&2:折半查找 m = (low + high)>>1; if(array[i] >= array[m]){//值相同时, 切换到高半区，保证稳定性 low = m + 1; //插入点在高半区 }else{ high = m - 1; //插入点在低半区 } } for(j = i; j > low; j--){ //步骤3:插入位置之后的元素全部后移一位 array[j] = array[j-1]; } array[low] = current; //步骤4:插入该元素 } return array; }
为了便于对比, 同样以数组 [5,4,3,2,1] 举例🌰. 原数组的演化过程如下(与上述一样):
虽然折半插入排序明显减少了查询的次数, 但是数组元素移动的次数却没有改变. 它们的时间复杂度都是O(n²).
希尔排序希尔排序也称缩小增量排序, 它是直接插入排序的另外一个升级版, 实质就是分组插入排序. 希尔排序以其设计者希尔(Donald Shell)的名字命名, 并于1959年公布.
算法的基本思想:
将数组拆分为若干个子分组, 每个分组由相距一定”增量”的元素组成. 比方说将[0,1,2,3,4,5,6,7,8,9,10]的数组拆分为”增量”为5的分组, 那么子分组分别为 [0,5], [1,6], [2,7], [3,8], [4,9] 和 [5,10].
然后对每个子分组应用直接插入排序.
逐步减小”增量”, 重复步骤1,2.
直至”增量”为1, 这是最后一个排序, 此时的排序, 也就是对全数组进行直接插入排序.
如下是排序的示意图:
可见, 希尔排序实际上就是不断的进行直接插入排序, 分组是为了先将局部元素有序化. 因为直接插入排序在元素基本有序的状态下, 效率非常高. 而希尔排序呢, 通过先分组后排序的方式, 制造了直接插入排序高效运行的场景. 因此希尔排序效率更高.
我们试着抽象出共同点, 便不难发现上述希尔排序的第四步就是一次直接插入排序, 而希尔排序原本就是从”增量”为n开始, 直至”增量”为1, 循环应用直接插入排序的一种封装. 因此直接插入排序就可以看做是步长为1的希尔排序. 为此我们先来封装下直接插入排序.
//形参增加步数gap(实际上就相当于gap替换了原来的数字1) function directInsertionSort(array, gap) { gap = (gap == undefined) ? 1 : gap; //默认从下标为1的元素开始遍历 var length = array.length, index, current; for (var i = gap; i < length; i++) { index = i - gap; //待比较元素的下标 current = array[i]; //当前元素 while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大 array[index + gap] = array[index]; //将待比较元素后移gap位 index -= gap; //游标前移gap位 } if(index + gap != i){ //避免同一个元素赋值给自身 array[index + gap] = current; //将当前元素插入预留空位 } } return array; }
那么希尔排序的算法实现如下:
function shellSort(array){ var length = array.length, gap = length>>1, current, i, j; while(gap > 0){ directInsertionSort(array, gap); //按指定步长进行直接插入排序 gap = gap>>1; } return array; }
同样以数组[5,4,3,2,1] 举例🌰. 原数组的演化过程如下:
对比上述直接插入排序和折半插入排序, 数组元素的移动次数由14次减少为7次. 通过拆分原数组为粒度更小的子数组, 希尔排序进一步提高了排序的效率.
不仅如此, 以上步长设置为了 {N/2, (N/2)/2, …, 1}. 该序列即希尔增量, 其它的增量序列 还有Hibbard：{1, 3, …, 2^k-1}. 通过合理调节步长, 还能进一步提升排序效率. 实际上已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,…). 该序列中的项或者是9*4^i - 9*2^i + 1或者是4^i - 3*2^i + 1. 具体请戳 .