思路
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
所以，由上述我们可知：希尔排序，是多组的直接插入排序，如果不了解直接插入排序，可参考这篇文章：直接插入排序
所以，先选定一个gap值，让其分组，再排序。
但是，最后gap的值总归会等于1，完成最后的排序，只不过此时的数组基本趋近于有序，此时的直接插入的时间复杂度就比较低。
但是要实现希尔排序，gap应该怎么设定呢？
首先要确保，最后一组的gap必须是1，所以我们这样规定：gap = gap / 3 + 1
这样就可以保证最后一个的gap总是1文章来源：https://www.toymoban.com/news/detail-798535.html
ShellSort
文章来源地址https://www.toymoban.com/news/detail-798535.html
//希尔排序
void ShellSort(int* a, int n)
{
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 (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
break;
}
a[end + gap] = tmp;
}
}
//直接插入排序
//InsertSort(a, n);
}
到了这里，关于【数据结构 | 希尔排序法】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
