现在晚上睡觉之前都会看一会讲算法的书。因为大三的时候，没有怎么好好学习过算法，而之前C/C++也一直没认真上过课，所以这次看书也像新学一样从头开始看。最先讲的算法肯定是排序算法。冒泡算法还是一看就明白了，插入也能看明白，但希尔算法看了两个晚上也没能搞明白。今天终于通过代码实现了。希尔算法也是基于插入排序算法的，但比简单的插入排序效率要高很多。当待排序数目更多时，效率高得更明显。以下是完整C源代码：

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define NUM 1000

void insertSort(int * a, int len) {
    int i, j, t, countChange = 0;//countChange记录数据移动次数
//    int k = 0;
    for(i = 1; i < len; i++) {
        t = a[i];
        j = i-1;
        while(j >= 0 && t < a[j]) {
            a[j+1] = a[j];
            j--;
            countChange++;
        }
        a[j+1] = t;
//        k++;
//      printf("第%d次排序后的结果：", k);//显示第k次排序后的结果
//        for(j = 0; j < len; j++)
//            printf("%d ", a[j]);
//        printf("\n");
    }
    printf("完成排序一共移动数据次数：%d\n", countChange);
}

void shellSort(int * a, int len) {
    int i, j, r, t, countChange = 0;
//    int k = 0;
    for (r = len/2; r >= 1; r /= 2) {
        for (i = r; i < len; i++) {
            t = a[i];
            j = i-r;
            while (j >= 0 && t < a[j]) {
                a[j+r] = a[j];
                j -= r;
                countChange++;
            }
            a[j+r] = t;
//            k++;
//            printf("第%d排序后的结果：", k);
//            for (j = 0; j < len; j++)
//                printf("%d ", a[j]);
//            printf("\n");
        }
    }
    printf("完成排序一共移动数据次数：%d\n", countChange);
}

int main()
{
    int a[NUM], b[NUM], i;
    srand(time(NULL));//设置随机种子

    for(i = 0; i < NUM; i++)//随机生成数组数据
        a[i] = b[i] = rand();

    printf("Before sorting: ");//输出排序前的数据序列
    for(i=0; i<NUM; i++)
        printf("%d ", a[i]);

    printf("\n\n插入排序：\n");
    insertSort(a, NUM);

    printf("\n希尔排序：\n");
    shellSort(b, NUM);
    printf("\n");

    printf("After sorting: ");//输出排序后的数据序列
    for(i=0; i<NUM; i++)
        printf("%d ", a[i]);

    printf("\n");
    return 0;
}

去除代码注释可以查看每次排序后的结果。

当数组规模为10时，希尔排序数据移动次数只有插入排序的一半；当数组规模为100时，插入排序需要移动次数大概是希尔排序的5倍；当数组规模为100时，插入排序需要移动次数大概是希尔排序的30倍。

（原博客发布时间：2011-10-27 14:03:51）