大家好，欢迎来到IT知识分享网。
算法-排序之希尔排序
希尔
排序得名于其设计者设计者希尔（Donald Shell），设计体现了计算机领域的“分治法”思想。在众多排序算法中，目前而言，希尔排序是唯一能在效率上与快速排序（【算法-排序之二】快速排序）一较高低的算法，目前只有这两种排序算法的时间复杂度突破O(n2)。值得一提的是，希尔排序与快速排序都基于“分治法”，从这里或许可以解释这两种排序算法在效率上的得天独厚。
1. 希尔排序ShellSort()
核心:先将序列分成较多个子序列分别进行排序，再分成较少个子序列分别进行排序，直到最后为一个序列排序。
形象的说：比如先分成 8 个子序分别排序，再 4 个子序，再 2 个子序，最后 1 个（1个也就是全部序列啦）。
希尔排序的实现方法：
1.1如何划分子序列：希尔排序采用每隔固定距离选取一个数的方法划分子序。其中间隔距离称为增量。如图：
通过图示，增量的概念很容易理解吧，增量就是隔多少距离的数都为同一个子序。通过这种方法，如果增量选择为N，那么可以分为N个子序，想想是不是这样哦。每次子序都排好后，增量减半，增量减少意味着子序数减少，直到增量为1，便是全部的数序了，希尔排序完成。
1.2子序内部怎么排序：
讲述1的过程中，说道划分子序后对子序分别排序，那么采取什么排序方法？希尔排序的子序排序方法为插入排序（【算法-排序之三】插入排序）。
算法实现：
希尔排序的代码并不复杂，通过增量是否为1控制整个排序的结束。在增量为为d时,遍历此时的d个子序，从k=0到k=d-1。随后对每个子序进行插入排序操作。
void ShellSort(int Array[],int n){ int d=n/2; //设置起始增量 while(d >= 1) { //增量为1时排序结束 for(int k=0;k =k && Array[j]>temp) { Array[j+d]=Array[j]; j=j-d; } Array[j+d]=temp; } } d=d/2; //缩小增量 } } 2.算法复杂度：
希尔排序的算法复杂度分析可类比快速排序（【算法-排序之二】快速排序）复杂度分析，一般认为希尔排序时间复杂度为：O(nlogn)。
3.空间复杂度:
希尔排序的空间复杂度显然为O(1)，仅仅需要一个交换变量。相比快速排序递归调用产生的巨大栈消耗，希尔排序O(1)的空间消耗显得十分让人惊喜。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/157308.html
