希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）盗胀，是直接插入排序算法的一種更高效的改進(jìn)版本勋又。
基本思想：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序武福，然后依次縮減增量再進(jìn)行排序竭缝，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對全體元素進(jìn)行一次直接插入排序熏纯。
希爾排序過程
- 空間復(fù)雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
C語言的實(shí)現(xiàn):
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個(gè)組,進(jìn)行插入排序
{
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;
}
