●🧑个人主页:你帅你先说.
●📃欢迎点赞👍关注💡收藏💖
●📖既选择了远方，便只顾风雨兼程。
●🤟欢迎大家有问题随时私信我！
●🧐版权：本文由[你帅你先说.]原创，CSDN首发，侵权必究。

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

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=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<n-gap;i+=gap){int end = i;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 j = 0;j<gap;j++){for(int i = j;i<n-gap;i+=gap){int end = i;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;
}

🍿动图演示:

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

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

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

//多个组一起排序
void ShellSort(int*a,int n)
{int gap = 3;for(int i = 0;i<n-gap;i++){int end = i;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;
}

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

void ShellSort(int*a,int n)
{int gap = n;while(gap>1){gap /= 2;//gap = gap/3+1;这种方法也可以for(int i = 0;i<n-gap;i++){int end = i;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;
}

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

即时间复杂度为: O($N^{1.3}$)。
🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲
觉得写的不错可以给个一键三连 点赞👍关注💡收藏💖
🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲🍲