希尔排序:Javascript

参考书:
严蔚敏-数据结构

希尔排序(Shell’s Sort)

希尔排序又称”缩小增量排序”,归属于插入排序一类,简单来说,和我们的插入排序比,它更快.

奇妙的记忆点:

  • 内排序(内存排序就够了)
  • 不稳定(排序后原始顺序无法保证) 希尔排序重点在于分割.

    基本思想:

    将整个待排序记录序列分割为若干个子序列,然后对每一个子序列进行直接插入排序.

直接插入排序:

不得不先讲一下直接插入排序了,毕竟希尔排序要使用到直接插入排序.
直接插入算法重点在于分区,有序区与无序区.假设我们有一个数组arr

1
2
3
4
5
6
7
8
9
for(var i = 1;i<arr.len;i++){
var temp = arr[i];
var j = i-1;
while(j>=0&&arr[j]>temp){
arr[j+1] = arr[j];
j--;
}
arr[j] = temp;
}

其中i=1,i~arr.len-1为我们的无序区,而i=0为我们的有序区.temp用于记录无序区准备进入有序区的元素,j用于从右往左遍历有序区并将元素往后推,找出相应的插入位置,将temp插入对应位置.

希尔排序:代码

希尔排序关键在于增量的设置,根据增量分割数组并逐步进行直接插入排序,增量逐趟减少,并最后使得整个数组基本有序,再对整体进行直接插入排序.

记忆点

  • best condition: T(n) = O(n*log2 n)
  • baddest condition: T(n) = O(n*log2 n)
  • average condition: T(n) = O(n*log n)

基本的思路就是根据增量分割数组,如var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
我们增量为5,则分割为
[3,15,46]
[44,36,4]
[38,26,19]
[5,27,50]
[47,2,48]
并对每一组进行直接插入排序
再把增量变为2(减半),再进行分割,直到增量为1,再对全体进行一次直接插入排序就可以了.
简略的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var len =arr.length;
gap = Math.floor(len/2);
while(gap!==0){
for(var i = gap;i<len;i++){
var temp = arr[i];
var j;
for(j=i-gap;j>=0&&temp<arr[j];j-=gap){
arr[j+gap] = arr[j];
}
arr[j+gap] = temp;
}
gap=Math.floor(gap/2);
}
return arr;

简单说一下,i从gap位开始,那么每组的有序区已经确定了一位,接下来将i-gap位的数根据组的不同插入有序区,就完成了每组的直接插入排序了.

相关流程图

图片描述

动态定义间隔序列

这是我在掘金看来的

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列,也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。

while(gap < len/5) { //动态定义间隔序列
    gap =gap*5+1;
}

参考来源:http://gold.xitu.io/post/57dcd394a22b9d00610c5ec8
详细介绍了十种算法,大家可以去学习下.

以后大概会尽量每天更新一个算法学习吧,温故而知新