插入排序详见:点这里
希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。其是基于插入排序改进而来的。
希尔排序大致分为两步预排序和插入排序两大步。
预排序是将变量分为 n 组,然后将每组相应位置的数当做一组进行升序或降序的排列,这样做的好处是将小的数往前排,将大的数向后排,使整个数组越接近有序,到最后排序时就耗费的时间越小。
我们先来看预排序
一次预排序的单趟排序代码为
int gap = 3;
//比较一次循环,还要防止数组越界的情况发生,所以 j < n - gap
for (int j = 0 + i; j < n - gap; j += gap)
{
int end = j;
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;
}
则一次预排序的代码为
int gap = 3;
//控制循环总次数
for (int i = 0; i < gap; i++)
{
//比较一次循环,还要防止数组越界的情况发生,所以 j < n - gap
for (int j = 0 + i; j < n - gap; j += gap)
{
int end = j;
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;
}
}
对于这个代码,我们可以对其进行改动,让其更加简洁,但代码的效率不变。
int gap = 3;
//比较一次循环,还要防止数组越界的情况发生,所以 j < n - gap
for (int j = 0; j < n - gap; j++)
{
int end = j;
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 每次的变化,都认为除三是比较好的。
希尔排序代码为:
// 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
//确保最后一次gap为1时,排序后终止循环
while (gap > 1)
{
//确保最后一次gap为1
gap = gap / 3 + 1;//gap变化数值为4 2 1
//比较一次循环,还要防止数组越界的情况发生,所以 j < n - gap
for (int j = 0; j < n - gap; j++)
{
int end = j;
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),一看这个数值就知道,这个时间复杂度不好计算,所以我们直接记结论就好。