排序与算法：希尔排序

执行效果 希尔排序的执行效果是这样的：

呃……看不懂吗？没关系，接着往下看介绍 

算法介绍 希尔排序算法（Shell Sort）是按其设计者希尔（Donald Shell）的名字命名，该算法由 1959 年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。 该算法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个步长的元素组成的）分别进行直接插入排序，然后依次缩减步长再进行排序，待整个序列中的元素基本有序（步长足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。

算法档案 时间复杂度：O(n2) 最优时间复杂度：O(n) 平均时间复杂度：根据步长序列的不同而不同 空间复杂度：总共 O(n) 稳定性：不稳定

算法步骤

先取一个正整数步长 d1（d1 < length），把全部记录分成 d1 个组，所有距离为 d1 的倍数的记录看成一组，然后在各组内进行插入排序然后取 d2（d2 < d1）重复 1 和 2 两个步骤，直到 di = 1（i >= 1）位置，即所有记录成为一个组，最后对这个组进行插入排序

注：一般选 d1 约为 length/2，d2 为 d1 /2， d3 为 d2/2 ，…， di = 1。

算法实现

#include <stdio.h> void shell_sort(int array[], int length); void shell_sort(int array[], int length) { int i, j, step, temp; for (step = length / 2; step > 0; step /= 2) { for (i = step; i < length; i++) { temp = array[zxsq-anti-bbcode-i]; for (j = i - step; j >= 0 && array[zxsq-anti-bbcode-j] > temp; j -= step) { array[j+step] = array[zxsq-anti-bbcode-j]; } array[j+step] = temp; } } } int main(void) { int array[] = {73, 108, 111, 118, 101, 70, 105, 115, 104, 67, 46, 99, 111, 109}; int i, length; length = sizeof(array) / sizeof(array[zxsq-anti-bbcode-0]); shell_sort(array, length); printf("排序后的结果是："); for (i = 0; i < length; i++) { printf("%d ", array[zxsq-anti-bbcode-i]); } putchar('\n'); return 0; }

程序实现如下：