希尔排序
希尔排序是插入排序的扩展。希尔排序的一个特点是：子序列的构成不是简单的逐段分割，而是将相隔某个增量的记录组成一个子序列。希尔排序的一个关键是：其步长（也就是增量）的取法，通常认为步长序列中的数字互质很重要。
希尔排序的C/C++代码实现：
- void shell_insert(int sort_array[], int length, int h)
- {
- int i, j, temp;
- for (i = h; i < length; ++i)
- if (sort_array[i] < sort_array[i-h]) {
- temp = sort_array[i];
- sort_array[i] = sort_array[i-h];
- for (j = i - h * 2; j >= 0 && temp < sort_array[j]; j -= h)
- sort_array[j+h] = sort_array[j];
- sort_array[j+h] = temp;
- }
- }
- void shell_sort(int sort_array[], int length)
- {
- int h;
- for (h = 1; h < (length - 1) / 9; h = h * 3 + 1);
- while (h >= 1) {
- shell_insert(sort_array, length, h);
- h /= 3;
- }
- }
和直接插入排序相比，这里的shell_insert只做了两处修改：
1. 前后记录位置的增量不再是1，而是h；
2. sort_array[0]已不能再作为监视哨，而只能作为一个暂存单元，因为式子j -= h并不一定能使j值到达0。因此，这里干脆用一个temp来代替sort_array[0]做为暂存单元，而让sort_array[0]也加入排序，这样的做法也更通用。
关于h，上面程序中，步长序列取的是：1 4 13 40 121 364 1093 3280 9841…（从1开始，通过乘3加1得到下一个步长），这是由Knuth在1969年提出来的，该方法容易实现，而且即使是对中等大小的文件，效率也相对还可以。其时间复杂度最差时是O(n3/2)。
此外，也还存在效率更好的h序列，如：1 8 23 77 281 1073 4193 16577… 但这种序列通常也较难实现，而且相对于上面所用的，效率提高上很难超过20%。比如使用 1 8 23… 这组序列时，时间复杂度最差为O(n4/3)。
另外还有一些取法不好的步长序列，如：1 2 4 8 16 32 64 128 256 512 1024 2048… 这是由当年Shell提出Shell算法时自己给出的序列。但这个序列通常效率比较低，特别是面对最坏的情况下。不过，即使是使用这个序列，希尔排序也要比之前所说的简单排序方法快很多。
希尔排序对不同类型的文件进行操作时效率都不错，不仅仅是随机文件，即使是对大文件时也如此。而且希尔排序代码简单容易执行，相比于其他几种先进的排序方法（如快速排序、堆排序、归并排序），除非n很大，它们最多也只是提高两倍左右效率（n㏒n），而且要复杂的多。因此，希尔排序在很多情况下是一个不错的选择。
文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/10.html
