数据结构|希尔排序——直插排序的更好优化 c|数据结构|算法|c语言|#排序

希尔排序是直接排序的更好优化
如果没有听过直接插入排序的可以看这里——直接插入排序
目录
希尔排序的思路
代码实现
【数据结构|希尔排序——直插排序的更好优化】如何变得完全有序？
完整代码

直接插入排序是一个一个的插入，然后排序
但是希尔排序不一样
希尔排序的思路：分组排序，将一个数组排到相对有序，然后在进行插入排序
例如这样的一个数组

文章图片

我们将每间隔为2的分为一组

文章图片

然后我们进行每组的排序

文章图片

我们将间隔减少继续排列

文章图片

根据这样的思想，我们就得到了希尔排序

2.代码实现我们默认间隔为gap
首先我们先完成一组内的排序（与直接插入排序相似）
先将需要插入的数存起来

int tmp = arr[end + gap];

然后我们对这组内的数字进行遍历比较

while (end) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } }

当循环停止时（两种情况）
1.找到了比他小的数
2.找完了也没找到比他小的数
就是我们要放入这个数的时候

arr[end + gap] = tmp;

这是一组的比较，那么我们一共要进行多组
引入循环

for (int i = 0; i < n - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; }

当循环结束的时候，我们就将这个数组变得相对有序
那么我们该如何将他变得完全有序呢？答案是：改变gap
gap每变小一次，数组就相对有序，直到gap变为1，数组完全有序
gap我们希望第一次是n/2，每次gap/=2；
因此引入gap，进行多次排序使得，数组完全有序
完整代码

void ShellSort(int* arr,int n) { int gap = n/2; while (gap /= 2) { for (int i = 0; i < n - gap; i++) { int end = i; int tmp = arr[end + gap]; while (end) { if (arr[end] > tmp) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = tmp; } } }