每天一点算法-希尔排序 (Day6)

介绍

今天介绍第二种插入排序——希尔排序，该方法因D.L.Shell于1959年提出而得名，是第一个时间复杂度突破O(n^2)的排序算法，又叫缩小增量排序，在待排序数据量越大，希尔排序较直接插入排序的优势就越加明显，但也是前面介绍几种算法中较难理解的一种。算法逻辑（升序为例）：
初始时，有一个大小为 10 的无序序列:

1.在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
2.接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
3.按照直接插入排序的方法对每个组进行排序。
4.在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
5.按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。

例子

假设有一个待排序数组[77, 6, 37, 96, 34, 6, 14], js实现如下(升序)：

function shellSort(arr) {
　　var len = arr.length,
　　temp,
　　gap = 1;
　　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[i];
　　　　　　for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
　　　　　　　　arr[j+gap] = arr[j];
　　　　　　}
　　　　　　arr[j+gap] = temp;
　　　　}
　　}
　　return arr;
}
sort([77, 6, 37, 96, 34, 6, 14]); // =>[6, 6, 14, 34, 37, 77, 96]

时间复杂度

时间复杂度为O(n^1.3)。

感谢阅读！欢迎关注！持续更新中...