排序算法总结（三）希尔排序
访问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;
}
}
}
}