希爾排序: 針對插入排序的改進，縮小增量的思想，非穩定排序
希爾排序(Shell sort)也稱“縮小增量排序”。它的做法不是每次一個元素挨一個元素的比較。而是先將整個待排記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄基本有序時，再對全體記錄進行一次直接插入排序。這樣大大減少了記錄移動次數，提高了排序效率。
算法思路：先取一個正整數d1（d1＜n），把全部記錄分成d1個組，所有距離為dl的倍數的記錄看成是一組，然后在各組內進行插入排序；接著取d2（d2＜d1），重復上述分組和排序操作；直到di=1 (i＞＝1)，即所有記錄成為一個組為止。希爾排序對增量序列的選擇沒有嚴格規定，一般選d1約為n／2，d2為d1／2，d3為d2／2，…，di＝1。
在希爾排序開始時增量較大，分組較多，每組的記錄數目少，故各組內直接插入較快，后來增量di逐漸縮小，分組數逐漸減少，而各組的記錄數目逐漸增多，但由于已經按di-1作為距離排過序，使文件較接近于有序狀態，所以新的一趟排序過程也較快。因此，希爾排序在效率上較直接插人排序有較大的改進。
希爾排序是按照不同步長對元素進行插入排序，當剛開始元素很無序的時候，步長最大，所以插入排序的元素個數很少，速度很快；當元素基本有序了，步長很小，插入排序對于有序的序列效率很高。所以，希爾排序的時間復雜度會比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩定性就會被打亂，所以shell排序是不穩定的。
void
shell_sort(int *array, int len)
{
int i, j, step, backup;
for(step=len>>1; step>0; step>>=1) {
for(i=step; i<len; ++i) {
backup = array[i];
for(j=i-step; j>=0 && array[j]>backup; j-=step)
array[j+step] = array[j];
array[j+step] = backup;
}
}
}