執行效果
希爾排序的執行效果是這樣的：

呃……看不懂嗎？沒關系，接著往下看介紹?

算法介紹
希爾排序算法（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;
}

程序實現如下：