排序算法4---希尔排序算法，改进的直接插入排序

#include <stdio.h>

#define MAXSIZE 9  /* 用于要排序数组个数最大值，可根据需要修改 */
typedef struct
{
    int r[MAXSIZE+1];    /* 用于存储要排序数组，r[0]用作哨兵或临时变量 */
    int length;            /* 用于记录顺序表的长度 */
}SqList;

/* 交换L中数组r的下标为i和j的值 */
void swap(SqList *L,int i,int j) 
{ 
    int temp=L->r[i]; 
    L->r[i]=L->r[j]; 
    L->r[j]=temp; 
}

void print(SqList L)
{
    int i;
    for(i=1;i<=L.length;i++)
        printf("%d,",L.r[i]);
    printf("
");
}

/* 对顺序表L作希尔排序 */
void shellsort(SqList * L){
    int j,i,k=0,increment=L->length;
    do{
        increment=increment/3+1;
        for(i=increment+1; i <= L->length; i++){
            if(L->r[i]<L->r[i-increment]){
                L->r[0]=L->r[i];
                //注意j不要出边界
                for(j=i-increment; j>0 && L->r[j] > L->r[0]; j-=increment){
                    L->r[j+increment]=L->r[j];
                }
                L->r[j+increment]=L->r[0];
            }
        
        }
    printf("第%d趟排序结果为:
",++k);
    print(*L);
    }while(increment>1);//increment=1时是最后一趟遍历
}

int main(){
    SqList L;
    int num[10] = {9,5,3,2,4,6,1,7,8,9};    
    for(int i=0; i<10; i++){
        L.r[i]=num[i];
    }//注意给数组赋值的方法
    L.length=9;
    //希尔排序
    shellsort(&L);
    return 0;
}

增量的选取很关键，最好的情况下时间复杂度可达到O(n^(3/2)),要好于直接排序的O（n^2）.
希尔排序中记录是跳跃式的移动，所以希尔排序不是稳定的排序算法。
意义：突破了慢速排序的时代（超越了O(n^2)）.