数据结构--排序之希尔排序

●六个人主页:你帅你先说.
●欢迎点赞关注收藏
●既选择了远方，便只顾风雨兼程。
●蘭欢迎大家有问题随时私信我！
●類版权：本文由[你帅你先说.]原创，CSDN首发，侵权必究。

希尔排序基本思想及代码实现

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序是在直接插入排序的思想上进行优化的，它主要分为两步:
1.分组预排序–数组接近有序
2.直接插入排序
图解过程


上述过程用代码实现就是这样:

//橙色组单趟的希尔排序void ShellSort(int*a,int n){int gap = 3;int end = 0;int x = a[end+gap];while(end>=0){if(a[end]>x){a[end+gap] = a[end];end-=gap;}else{break;}}a[end+gap] = x;}

上述过程用代码实现就是这样:

//橙色整个组的希尔排序void ShellSort(int*a,int n){int gap = 3;for(int i = 0;i=0){if(a[end]>x){a[end+gap] = a[end];end-=gap;}else{break;}}}a[end+gap] = x;}

同样，对绿色组和蓝色组进行插入排序。

上述过程用代码描述就是这样的:

//橙色整个组的希尔排序void ShellSort(int*a,int n){int gap = 3;for(int j = 0;j=0){if(a[end]>x){a[end+gap] = a[end];end-=gap;}else{break;}} } }a[end+gap] = x;}

动图演示:

到这一步，我们先来分析一下它的时间复杂度。
最好时间复杂度:O(N)
最坏时间复杂度:F(N,gap) = (1+2+3+… N g a p frac{N}{gap} gapN​)*gap

从图中我们可以发现这样的规律:
gap越大预排越快,预排后越不接近有序
gap越小预排越慢,预排后越接近有序

接下来我们就进行多组排序,过程我就不画了,大家可以自己动手画画,直接上代码。

//多个组一起排序void ShellSort(int*a,int n){int gap = 3;for(int i = 0;i=0){if(a[end]>x){a[end+gap] = a[end];end-=gap;}else{break;}} }a[end+gap] = x;}

现在只差最后一步了,控制gap。

void ShellSort(int*a,int n){int gap = n;while(gap> 1){gap /= 2;//gap = gap/3+1;这种方法也可以for(int i = 0;i=0){if(a[end]>x){a[end+gap] = a[end];end-=gap;}else{break;} } } }a[end+gap] = x;}

那整个希尔排序的时间复杂度是多少呢?
如果是 gap /= 2，那么时间复杂度就是O(N l o g 2 N log_2N log2​N)
如果是 gap/=3+1 那么时间复杂度就是O(N l o g 3 N log_3N log3​N)
有的书上针对于这个时间复杂度还会给一种答案

即时间复杂度为: O( N 1.3 N^{1.3} N1.3)。

觉得写的不错可以给个一键三连 点赞关注收藏
