内容简介:希尔排序是基于插入排序的以下两点性质而提出改进方法的:先上个维基百科的动图,不知道你们看不看得懂,反正我不是很懂……希尔排序其实就是直接插入排序的升级,原理就是先将整个待排序列按照某个增量(也称步长)分割成若干个子序列分别进行直接插入排序,然后合并,之后依次缩小增量大小在进行排序,当增量足够小(通常为1)时,再对全体元素进行直接插入排序,而此时需排序的数据几乎是已排好的了,所以此时插入排序较快。
希尔排序是基于插入 排序 的以下两点性质而提出改进方法的:
- 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率
- 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位
先上个维基百科的动图,不知道你们看不看得懂,反正我不是很懂……
说说我的个人理解:
希尔排序其实就是直接插入排序的升级,原理就是先将整个待排序列按照某个增量(也称步长)分割成若干个子序列分别进行直接插入排序,然后合并,之后依次缩小增量大小在进行排序,当增量足够小(通常为1)时,再对全体元素进行直接插入排序,而此时需排序的数据几乎是已排好的了,所以此时插入排序较快。
当然如果你觉得文字比较乏味就看下面的这些例子吧
例如,假设有这样一组数 [9 1 5 8 3 7 4 6 2]
,如果我们先以步长为4进行分割,就是这样:
9 1 5 8 3 7 4 6 2 复制代码
然后我们对每列进行排序(注意每列哦):
2 1 4 6 3 7 5 8 9 复制代码
将上述四行数字,依序合并我们得到: [ 2 1 4 6 3 7 5 8 9 ]
。此时2已经往前移,而8、9已经在后两位,然后再以2为步长进行分割:
2 1 4 6 3 7 5 8 9 复制代码
继续排序:
2 1 3 6 4 7 5 8 9 复制代码
合并得到 [ 2 1 3 6 4 7 5 8 9]
,此时序列已经基本有序,需交换数据的情况大为减少,这时整列进行直接插入排序效率就非常高。
最终完成排序过程,也就是步长为1时,得到最终序列为: 1 2 3 4 5 6 7 8 9
。
示例代码(C)
#include <stdio.h> #define MAXSIZE 100 //用于要排序数组的最大值 typedef struct //定义一个顺序表结构 { int r[MAXSIZE+1]; //用于存储要排序数组,r[0]用作哨兵或者临时变量 int length; //用于存储顺序表的最大长度 }SqList; void ShellSort(SqList *L) { int i,j; int gap=L->length; //获取数组长度 for(gap/=2;gap>=1;gap/=2) //步长 for(i=gap+1; i<=L->length; i++) //从第gap+1个元素开始,因为r[0]被当做临时变量 if(L->r[i] < L->r[i-gap]) //每个元素与自己组内的数据进行直接插入排序 { L->r[0]=L->r[i]; //把要交换的数据暂存的L->r[0]中 for(j=i-gap; j>0&&L->r[j] > L->r[0]; j-=gap) L->r[j+gap] = L->r[j]; //记录后移,查找插入位置 L->r[j+gap]=L->r[0]; //插入 } } int main() { int i=0; int array[] = {39,80,76,41,13,29,50,78,30,11,100,7,41,86}; SqList L; L.length = sizeof(array)/sizeof(array[0]); //获取数组长度 for(i=0;i<L.length;i++) { L.r[i+1]=array[i]; //把数组存入顺序表结构 } ShellSort(&L); //输出排序后的数组 for(i=0;i<L.length;i++) { printf("%d ",L.r[i+1]); } return 0; } 复制代码
可能有几个步骤略难懂,这里解释下:
-
第17行:这里的步长采用 ,最终判断条件为gap>=1,这里不管你数组初始长度为多少,除到最后均会等于1,而等于1时,就是执行最后一次循环,这个时候也就是所有元素进行直接插入排序。当然也可写成gap>0。
-
第18行:在前面定义顺序表结构时,我们加多了一位,也就是把r[0]当做交换数据时的临时变量。
-
第22~23行:对于这个循环我们直接拿上面的例子中的一列进行讲解
(9 3 2)
:
当 时,9和3进行了一次交换,变为 (3 9 2)
(位置为1 5 9),之后在 时 ,做出的交换如上图所示(图略差...),分为三个步骤:
- 第一次进入循环 ,执行23行得 ,此时该列数值变为
(3 9 9)
; - 继续第二次循环 ,同样执行循环 ,此时变为
(3 3 9)
; - 跳出循环(注意:跳出循环时多执行了一次 ),执行 ,最终变为
(2 3 9)
。
步长(增量)选择
步长的选取非常关键,但是步长的选择没有统一规定,也没绝对的规律。只要满足最后一个步长为1即可。Donald Shell最初建议步长选择为 ,虽然这样去可以比 类的算法更好,但仍然有减少平均时间和最差时间的余地。维基百科给出的部分步长与最坏情况下复杂度有:
已知的最好步长序列是由Sedgewick提出的(1, 5, 19, 41, 109,...),该序列的项来自 和 这两个算式。这项研究也表明“比较在希尔排序中是最主要的操作,而不是交换。”用这样步长序列的希尔排序比插入排序要快,甚至在小数组中比快速排序和堆排序(后续博客整理),但是在涉及大量数据时希尔排序还是比快速排序慢。
以上所述就是小编给大家介绍的《聊聊希尔排序》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 聊聊快速排序的优化
- 图形化排序算法比较:快速排序、插入排序、选择排序、冒泡排序
- 排序算法下——桶排序、计数排序和基数排序
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介
- 计数排序vs基数排序vs桶排序
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
学习JavaScript数据结构与算法
[巴西] 格罗纳(Loiane Groner) / 孙晓博、邓钢、吴双、陈迪、袁源 / 人民邮电出版社 / 2015-10-1 / 39.00
本书首先介绍了JavaScript语言的基础知识,接下来讨论了数组、栈、队列、链表、集合、字典、散列表、树、图等数据结构,之后探讨了各种排序和搜索算法,包括冒泡排序、选择排序、插入排序、归并排序、快速排序、顺序搜索、二分搜索,还介绍了动态规划和贪心算法等常用的高级算法及相关知识。一起来看看 《学习JavaScript数据结构与算法》 这本书的介绍吧!