希爾排序有時(shí)也被稱為縮小增量排序.它的做法不是每次一個(gè)元素和下一個(gè)元素進(jìn)行比較.而是一開(kāi)始時(shí)使用較大的增量為間隔進(jìn)行比較,然后增量縮小,直至增量縮小為1.
希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而改進(jìn)的:
- 插入排序?qū)樞螂s亂度越低的數(shù)組操作時(shí),效率越高.
- 插入排序一般而言都是低效的,因?yàn)槊看沃荒軐?shù)據(jù)移動(dòng)一位.
算法思路:
- 取一個(gè)不大于數(shù)組長(zhǎng)度 n 的正整數(shù)a1(a1 < n), 把全部的數(shù)據(jù)分為 a1個(gè)組(即所以距離為 a1倍數(shù)的數(shù)據(jù)為1組),然后再各組內(nèi)進(jìn)行插入排序.
- 然后取 a2(a2 < a1)
- 重復(fù)上述的操作, 直至 ai = 1(即所有的數(shù)據(jù)為1組), 最后對(duì)這組進(jìn)行插入排序.一般而言, a1 = n/2, a2 = a1/2,....,ai = 1.
double *ShellSort(double *a, int n){
int i, j, Increment;
double tmp;
for(Increment = n/2; Increment > 0; Increment /= 2){
for(i = Increment; i < n; i++){
tmp = a[i];
for (j = i; j >= Increment ; j -= Increment) {
if(tmp < a[j - Increment])
a[j] = a[j - Increment];
else
break;
}
a[j] = tmp;
}
}
return a;
}
