什么是希尔排序

对整个数组进行预排序，即分组排序：按间距为gap分为一组，分组进行插入排序。

预排序的作用与特点

大的数更快地到后面，小的数更快地到前面；

gap越大，跳得越快，排完接近有序慢；

gap越小，跳得越慢，排完接近有序快。

图解希尔排序

代码实现

#include <stdio.h>
#include "ShellSort.h"//希尔排序typedef int ShSoDataType;void ShellSort(ShSoDataType* a, int n)
{//gap的值依次为，n/2， n/4， n/8， ......，2for (int gap = n / 2; gap > 1; gap /= 2){//间隔为gap的第i组进行插入排序//第i组：i， i + gap， i + 2gap，...... ，j(j = i + N * gap)// j再加gap就过nfor (int i = 0; i < n; ++i){//找第i组的最后一个元素的下标int j = i;while (j < n - gap)j += gap;for (int k = i; k <= j; k += gap){int end = k;int tmp = a[end];while (end > i){if (a[end - gap] > tmp){a[end] = a[end - gap];end -= gap;}else break;}a[end] = tmp;}}}
}void PrintfArr(int* a, int n)
{for (int i = 0; i < n; ++i)printf(" %d ", a[i]);printf("\n");
}int main()
{int arr[] = { 3, 3, 2, 4, 1, 2, 3, 7, 1, 2 };int arrsize = sizeof(arr) / sizeof(arr[0]);ShellSort(arr, arrsize);printf("ShellSort:");PrintfArr(arr, arrsize);return 0;
}