插入排序和希尔排序详解

插入排序详见：点这里

希尔排序(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 - gapfor (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为1gap = gap / 3 + 1;//gap变化数值为4  2  1//比较一次循环，还要防止数组越界的情况发生,所以 j < n - gapfor (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)，一看这个数值就知道，这个时间复杂度不好计算，所以我们直接记结论就好。