排序思想：先进行预排序，每次预排序都调插入排序，把大部分小数置前，大数置后（升序）。然后再进行插入排序。
示意图：
要实现代码先从插入排序看起：插入排序排一趟的代码是
int tmp = a[end + 1];//保存要排序的值 while (end >= 0) { if (a[end] > tmp) //排升序用>， 降序用< { a[end + 1] = a[end]; end -= 1; } else { break; } } a[end + 1] = tmp;
end前面的值都是有序的，上述代码中，end是一个一个往前遍历的，如果设一个变量gap替换上述代码中的1，就实现了跳跃式的插入排序，代码如下
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;
插入排序要排完整个数组需要再套一层循环，代码如下：
for (int i = 0; i < n - 1; i++) { //单趟 int end = i; int tmp = a[end + 1];//保存要排序的值 while (end >= 0) { if (a[end] > tmp) //排升序用>， 降序用< { a[end + 1] = a[end]; end -= 1; } else { break; } } a[end + 1] = tmp; }
这里要提醒一下，为什么循环结束的条件是 i < n - 1,而不是 i <= n - 1。n是个数，n - 1 是最后一个元素的下标，i 会赋值给end, end的意义是有序数组的边界，程序会把有序数组的后一个值（end的后一个值）和前面的有序数组比较并插入到合适的位置，如果end是整个数组的边界（end = i - 1),程序会把随机值和前面的有序数组比较，这样有序数组中就会有随机值。
如果我们想跳跃式的排完一整组也需要再套一层循环，代码如下：
for (int i = 0; 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 < n - gap也同理。但上述代码只完成了以0开头的第1组，但还要排以1开头的第2组……一共有gap组，代码如下：
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; } }
希尔排序的代码的核心逻辑已经完成了，接下来就是gap给多少的问题了，gap代表预排序时数据能够挪动多远，gap越大数据挪动就越快，但一次预排越不接近有序，gap越小数据挪动越慢，但一次预排越接近有序。gap等于1是就是插入排序。所以有大佬就再套了一层循环，让gap和n有关，代码如下：
int gap = n; while (gap > 1) { gap = gap / 3 + 1; 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; } } }
gap除3还要加1是为了让最后一次为gap为1的插入排序，上述代码会进行log以三为底n的对数次的预排序，然后在进行一次gap为1的插入排序。写到这里，希尔排序的代码就算完成了。
时间复杂度：n的1.3次方左右，但这只是一个大概，而且未经证明的，大家记一下结论即可。这其中涉及一些复杂的数学问题。但它的效率在所有排序中属于第一梯队。
还可以再优化一层循环，代码如下：
int gap = n; while (gap > 1) { 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; } }
有人知道是怎么优化的吗？再评论区讲一讲（doge）
