摘要：动态定义间隔序列参考来源详细介绍了十种算法大家可以去学习下以后大概会尽量每天更新一个算法学习吧温故而知新
参考书:
严蔚敏-数据结构
希尔排序(Shell"s Sort)
希尔排序又称"缩小增量排序",归属于插入排序一类,简单来说,和我们的插入排序比,它更快.
奇妙的记忆点:
内排序(内存排序就够了)
不稳定(排序后原始顺序无法保证)
希尔排序重点在于分割.
基本思想:
将整个待排序记录序列分割为若干个子序列,然后对每一个子序列进行直接插入排序.
直接插入排序:
不得不先讲一下直接插入排序了,毕竟希尔排序要使用到直接插入排序.
直接插入算法重点在于分区,有序区与无序区.假设我们有一个数组arr
for(var i = 1;i0&&arr[j-1]>key){
arr[j] = arr[j-1];
j--;
}
arr[j]=key;
}
其中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,再对全体进行一次直接插入排序就可以了.
简略的代码如下:
var len =arr.length;
gap = Math.floor(len/2);
while(gap!==0){
for(var i = gap;i=0&&temp
简单说一下,i从gap位开始,那么每组的有序区已经确定了一位,接下来将i-gap位的数根据组的不同插入有序区,就完成了每组的直接插入排序了.
相关流程图
动态定义间隔序列
这是我在掘金看来的
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的。
while(gap < len/5) { //动态定义间隔序列
gap =gap*5+1;
}
参考来源:http://gold.xitu.io/post/57dc...
详细介绍了十种算法,大家可以去学习下.
以后大概会尽量每天更新一个算法学习吧,温故而知新
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/80421.html
