排序算法总结（三）希尔排序

访问www.tomcoding.com网站，学习Oracle内部数据结构，详细文档说明，下载Oracle的exp/imp，DUL，logminer，ASM工具的源代码，学习高技术含量的内容。

如果你在网上搜一下希尔排序，都会告诉你希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。然后列一些图标或动画演示，最后给出一个算法函数。你看了以后还是不知道什么是希尔排序，里面的图太复杂，你看上好几遍也不能抓住重点。

我们来看一下希尔排序算法要解决的问题，都说希尔算法是插入排序的改进版，那么为什么要改进呢？原因是插入排序要进行大量的元素交换（位置移动），在完全升序排列的数组中，算法最高效，不需要进行交换，在完全降序的数组中，算法效率最低。为了改善这种情况，希尔排序把数组中的元素先进行多个分组，然后把每个分组按照插入排序算法升序排列，然后减少分组的个数，再进行插入排序，最后预排序的数组不再分组，进行最后一次插入排序。预排序的目的就是把数组中数值小的元素尽量放到数组前面，减少最后一次排序元素交换的次数。

那么怎样分组呢？最容易想到的就是第一次分组使得两个元素一组，那么如果有n个元素，就有n/2个分组，如果n不能被2整除，那么留下一个元素不分组。第二次分组把第一次分组的个数再减半，依次类推，直到再减半就是0了，说明是最后一次分组了，那么把最后一次分组进行一次插入排序，数组中的元素就按升序排列好了。这里数组元素个数为单数时，最后一个元素不参与分组排序，直到最后一次插入排序时才参与。

看一下程序。

static void shell_sort(int *ai, int n)

{

    int         i, j;

    int         gap, ne;

    int         *t;

    /* gap是间隙，表示每隔gap值的元素分为一组

     * ne是每一组中包含多少个元素

     * 在这里先分配跟原数组大小一样的数组，用于分组

     */

    if ((t = (int *)malloc(n*sizeof(int))) == NULL)

        return;

    /* 起始gap取元素个数的半数值，这样每一组只包含两个元素

     * gap每次循环后减半，直到为1，退出循环，进行最后一次插入排序

     */

    for (gap = n/2, ne = n/gap; gap > 1; gap /= 2, ne = n/gap) {

        /* 把原数组ai中的元素分组，分完组后进行插入排序 */

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

            /* 下面的循环完成后，生成了一个分组 */

            for (j = 0; j < ne; j++)

                t[i*ne+j] = ai[i+j*gap];

            /* 对刚生成的分组排序 */

            insertion_sort(&t[i*ne], ne);

        }

        /* 每一次分组排序结束后，把排序后的元素恢复到原来数组的位置上 */

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

            for (j = 0; j < ne; j++)

                ai[i+j*gap] = t[i*ne+j];

        }

    }

    /* gap=1，进行最后一次排序，这时如果元素个数是单数，最后一个元素也会参与排序 */

    insertion_sort(ai, n);

    /* 释放掉分配的内存 */

    free(t);

}

上面实现的这个排序算法，看起来臃肿，还需要辅助的数组，但直观的表现了希尔算法是分组插入排序算法的本质。

其实每个组都是相同间隔的元素组成的，还是在同一个数组中，这样把插入排序算法揉进分组里去，就能简化代码，看一下整合后的函数。

void shell_sort(int *ai, int n) {

    int     i, j;

    int     gap, t;

    for(gap = n/2; gap > 0; gap /= 2) {

        for(i = gap; i < n; i++) {

            for(j = i - gap; j >= 0 && ai[j] > ai[j+gap]; j -= gap) {

                /* 交换元素位置 */

                t         = ai[j];

                ai[j]     = ai[j+gap];

                ai[j+gap] = t;

            }

        }

    }

}