ShellSort希尔排序
希尔排序法又称缩小增量法。
- 希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个 组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工 作。当到达=1时，所有记录在统一组内排好序。
- 希尔排序=预排序+直接插入排序
- 预排序：让大的数值更快的到达后面，小的数值更快的到达前面。（达到一个让数组元素接近顺序的效果）
- gap是间距值❗
- 直接插入排序相当于gap==1，希尔排序相当gap存在值了。
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就 会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 稳定性：不稳定
4. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的 希尔排序的时间复杂度都不固定：
《数据结构(C语言版)》--- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
整体思路
- gap是数值之间的间距值❗
- 直接插入排序相当于gap==1，希尔排序相当gap存在值了。
- gap是几，就可以把整体分为几组。（除去gap = n的情况)（gap=gap/2或者gap=gap/3+1)
- 分组和每组里面的元素个数的关系
- gap = n（gap随着n的变换而变化，gap的值不固定）
- gap/2（每次gap组，每组里面的元素个数：2，4，8......)*2 【n/2，n/4，n/8....】
- gap/3+1 (每次gap组，每组里面的元素个数：3，9，27...）*2【n/3，n/9，n/27....】
- 随着gap的变小，组数会变小，每组里面的数值个数会变大。
- gap的值
- 一个数无论是奇数还是偶数/2 最后都等于1
- gap的值不是固定的，可以是gap/2或者gap/3+1
- gap值无论是/2 /3，最后都必须==1 ，最后要直接插入排序
- gap>1时时预排序，目的是让整体数值更加接近有序
- gap == 1的时候就是直接插入排序，目的是让整体值有序。
- gap的值越大，大的值更快的调到后面，小的值可以更快的调到前面，越不接近有序。
- gap的值越小，大的值更慢的调到后面，小的值可以慢的调到前面，越接近有序。
- gap的值不是固定的，gap的值是随着整体n的大小变化而变化的。
- 随着gap的变小，组数会变小，每组里面的数值个数会变大。
- 预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。
- 整体思路
- 一趟：类似直接插入排序的一趟，间距从1变为gap
- 一组：加入循环，完成一组的排序（类似直接插入排序整体）
- 多组：加入三层嵌套循环/多组并排。（完成多组排序）（gap是多少就有多少组）
- 整体：完成整个数组的排序（多次预排序直到最后插入排序gap=1)（n个值）gap=n（gap=gap/2或者gap=gap/3+1)
图解分析
- gap是数值之间的间距值❗
- gap=n（n是整个的数值个数）
- gap=gap/2
- gap=10/2=5
- gap=5/2=2
- gap=2/2=1
- 注意：无论gap用gap/2或者gap/3+1或者其他最后gap的值必须为1，因为最后要进行直接插入排序，完成整体的排序。
【1】预排序
为了理解，这里我们先把gap理解为固定值gap == 3是一个固定值。 假设n=11
单组排序
- 一组一组排序
- 三个嵌套循环
- 控制起始位置i=j（0/1/2）
- i=0（0/3/6）
- i=1（1/4/7）
- i=2（2/5）
- i=0/3/6/1/4/7/2/5
- 控制数组元素下标，防止越界i<n-gap（i<11-3=8)
//升序 //写法1：三层嵌套循环 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 tmp = a[end + gap]; //一趟 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else//<= { break; } } a[end + gap] = tmp; } } }
多组并排
- 多组并排
- 两个嵌套循环
- 控制起始位置i=0/1/2
- i=0/1/2/3/4/5/6/7
- 控制数组元素下标，防止越界i<n-gap（i<11-3=8)
//写法2 //多组并排 void ShellSort(int* a, int n) { //多组 int gap = 3; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; //一趟 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else//<= { break; } } a[end + gap] = tmp; } }
【2】直接插入排序
实际上如果整体的数量过大，gap为3是非常不合适的。所以，gap不可能为固定值，gap的取值是随着n变化的，所以gap有两种方式去取值。
关于gap取值
- gap=gap/2
- gap=gap/3+1
- 注意：无论gap用gap/2或者gap/3+1或者其他。最后gap的值必须为1，因为最后要进行直接插入排序，完成整体的排序。
- gap是几，就可以把整体分为几组。（除去gap = n的情况)（gap=gap/2或者gap=gap/3+1)
- 分组和每组里面的元素个数的关系
- gap = n（gap随着n的变换而变化，gap的值不固定）
- gap/2（每次gap组，每组里面的元素个数：2，4，8......)*2 【n/2，n/4，n/8....】
- gap/3+1 (每次gap组，每组里面的元素个数：3，9，27...）*2【n/3，n/9，n/27....】
- 随着gap的变小，组数会变小，每组里面的数值个数会变大。
void ShellSort(int* a, int n) { //整体 int gap = n; while (gap > 1) { //每组 //gap = gap / 2; gap = gap / 3 + 1; //.......... } } }
总代码实现
void ShellSort(int* a, int n) { //整体 int gap = n; while (gap > 1) { //每组 //gap = gap / 2; gap = gap / 3 + 1; for (int i = 0; i < n - gap; i++) { int end = i; int tmp = a[end + gap]; //一趟 while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else//<= { break; } } a[end + gap] = tmp; } } }
时间复杂度
- 希尔排序的时间复杂度O(N^1.3)
- O(N^1.3)比O（N*logN)略慢，效率略低一点。
- 希尔排序VS直接插入排序（秒入过万VS分入过万）
- 预排序gap的上一个值排完之后会对下一个值得排序调整次数产生影响。
- O(N^1.3)需要套用数学模型，统计学来计算，这里只是近似计算。记住最后结论即可。
🙂感谢大家的阅读，若有错误和不足，欢迎指正。下篇选择排序&堆排序。大家新年快乐！！
