希爾排序: 針對(duì)插入排序的改進(jìn)，縮小增量的思想，非穩(wěn)定排序
希爾排序(Shell sort)也稱(chēng)“縮小增量排序”。它的做法不是每次一個(gè)元素挨一個(gè)元素的比較。而是先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。這樣大大減少了記錄移動(dòng)次數(shù)，提高了排序效率。
算法思路：先取一個(gè)正整數(shù)d1（d1＜n），把全部記錄分成d1個(gè)組，所有距離為dl的倍數(shù)的記錄看成是一組，然后在各組內(nèi)進(jìn)行插入排序；接著取d2（d2＜d1），重復(fù)上述分組和排序操作；直到di=1 (i＞＝1)，即所有記錄成為一個(gè)組為止。希爾排序?qū)υ隽啃蛄械倪x擇沒(méi)有嚴(yán)格規(guī)定，一般選d1約為n／2，d2為d1／2，d3為d2／2，…，di＝1。
在希爾排序開(kāi)始時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來(lái)增量di逐漸縮小，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但由于已經(jīng)按di-1作為距離排過(guò)序，使文件較接近于有序狀態(tài)，所以新的一趟排序過(guò)程也較快。因此，希爾排序在效率上較直接插人排序有較大的改進(jìn)。
希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開(kāi)始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨摺Ｋ裕柵判虻臅r(shí)間復(fù)雜度會(huì)比o(n^2)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但在不同的插入排序過(guò)程中，相同的元素可能在各自的插入排序中移動(dòng)，最后其穩(wěn)定性就會(huì)被打亂，所以shell排序是不穩(wěn)定的。
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;
}
}
}