#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,constchar * 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;

}