希尔排序

学习之后，自己练习手写一下排序算法，加深印象

原理：将相距某个“增量”的记录组成一个子序列，在各个子序列内分别进行直接插入排序后得到基本有序的结果。所谓基本有序，就是小的关键字在前面，大的基本在后面，不大不小的基本在中间，比如{2,1,3,6,4,7,5,8,9}就可以称为基本有序

#define MAXSIZE 10
#include <stdio.h>
struct a{
    int array[MAXSIZE];    //数组用于存储排序数据 
    int length;           //用于存储数组长度信息， 
};

void init_array(struct a *L){   //初始化数组 
    int i;
    L->length = MAXSIZE;
    for (i=1;i<L->length;i++){     //索引为0的项留作备用 
        scanf("%d",&(L->array[i]));
    }
}

void swap(struct a *L,int i,int j){   //交换数组项 
    int temp = L->array[i];
    L->array[i] = L->array[j];
    L->array[j] = temp;
}

void print(struct a *L){    //打印数组项 
    int i;
    for (i=1;i<L->length;i++){
        printf("%d ",L->array[i]);
    }
}

void ShellSort(struct a *L){   //排序算法 
    int i,j;
    int increment = L->length;   //增量初始化为序列的长度 
    do{
        increment = increment/2;    //增量减半 
        for (i=increment+1;i<L->length;i++){   //从第一个序列的第二个数开始，接着是第二个序列的第二个数 
            if (L->array[i] < L->array[i-increment]){  //如果第二个数比已排好序的序列最后一个数还要小，就执行插入操作 
                L->array[0] = L->array[i];  //暂存在索引为0的位置 
                for (j=i-increment;L->array[0] < L->array[j] && j > 0;j-=increment){  //寻找插入位置 
                    L->array[j+increment] = L->array[j];   //依次后移记录位置 
                }
                L->array[j+increment] = L->array[0];  //插入记录 
                printf("\n");
                print(L);    
            }
        }
    }while(increment > 1); //当增量为1时，排序完成 
} 

int main(){
    struct a List;
    init_array(&List);
    printf("排序前:");
    print(&List);
    ShellSort(&List);
    printf("\n排序后:");
    print(&List);
    return 0;
}

• 可以看到，第一次循环时，增量为5，序列{9,1,5,8,3,7,4,6,2}被划分为{9,7}，{1,4}，{5,6}，{8,2}，{3}，第一次循环结束后，子序列{9,7}和{8,2}被排序，最终整个序列为{7,1,5,2,3,9,4,6,8}。
• 接着增量减半，变为2，整个序列又被重新划分为{7,5,3,4,8}，{1,2,9,6}，在第二次循环后变为{3,4,5,7,8}，{1.2,6,9}也就是{3,1,4,2,5,6,7,9,8}。
• 最后增量变为1，变成相邻元素之间的交换，排序完成。

算法时间复杂度：O(n^3/2)，增量的选取至关重要