#include <stdio.h>

/* 希尔排序

 基本思想：希尔排序又称为缩小增量排序，对简单插入排序的优化。（外部分组gap，组内部插入排序！！）

 特点：一种不稳定的排序

 */

void ShellSort(int array[],int len){

    int i,j;

    int gap;// gap

    int temp;

    for (gap = len/2 ; gap >0 ; gap = gap/2){ // 核心就是 array[j+gap]与 array[j]比较，直到gap＝1

        for (i = gap; i < len ; i++){          // i: gap ~ <len(i++)   4、3、2、1...

            temp = array[i];

            for (j = i - gap; j >=0; j-=gap) { // j: i-gap ~ >=0(j=j-gap)

                if (temp < array[j]) {

                    array[j+gap] = array[j];    // 如果待插入元素<前面序列，则后移元素

                }

                else

                    break;

            }

            array[j+gap] = temp;                // 空位填上待插入元素即可

        }

    }

}

int main(int argc,const char * argv[])

{

    int i =0;

    int a[] = {5,4,9,8,7,6,0,1,3,2};

    int len =sizeof(a)/sizeof(a[0]);

    // 希尔排序

    ShellSort(a, len);

    for (i =0; i < len; i++) {

        printf("%d ",a[i]);

    }

    printf("\n\n");

    return0;

}

深入浅出排序算法之－希尔排序