希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
基本思想：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
希尔排序过程
- 空间复杂度：O(1)
- 稳定性：不稳定
C语言的实现:
shellSort.h
#include <stdio.h>
#include <stdlib.h>
void ShellSort(int a[],int length)
{
int i, j,increment;
for(increment=length/2;increment>0;increment/=2)//增幅减为原来的一半
{
for(i=0;i<increment;i++) //increment个组,进行插入排序
{
for(j=i+increment;j<length;j+=increment)
{
if(a[j]<a[j-increment])
{
int temp=a[j];
int k=j-increment;
while(k>=0 && a[k] > temp)
{
a[k+increment]=a[k];
k-=increment;
}
a[k+increment] = temp;
}
}
}
}
}
shellSort_test.c
#include "shellSort.h"
int main()
{
int i, arr[10] = {2, 8, 6, 9, 4, 3, 1, 7, 0, 5};
for (i = 0; i < 10; i++)
printf("%d ", arr[i]);
printf("\n");
ShellSort(arr,10);
for (i = 0; i < 10; i++)
printf("%d ", arr[i]);
getchar();
return 0;
}
