希尔排序

希尔排序(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;
}