希尔排序的实质就是分组插入排序[平均时间 O(nlogn) 最差时间O(n^s) 1<s<2,不稳定],该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

#include <stdio.h>

void printArray(int a[], int n)
{
for(int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
printf("\n");
}

int shellSort(int a[], int n)
{
int tmp, k;
for(int gap = n / 2; gap > 0; gap /= 2) {
for(int i = 0; i < n; i++) {
for(int j = i + gap; j < n; j += gap) {
tmp = a[j];
for(k = j; k > 0 && a[k - gap] > tmp; k--) {
a[k] = a[k - 1];
}
a[k] = tmp;
}
}
}
}

int main()
{
int a[] = {4,6,3,2,7,9,1,5};
printArray(a, 8);
shellSort(a, 8);
printArray(a, 8);
}