溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
1、如何進(jìn)行希爾排序
希爾排序是直接插入排序的優(yōu)化，具體實(shí)現(xiàn)是先進(jìn)行以gap間隔分別進(jìn)行排序，將數(shù)組排成快要接近有序，最后一次gap為1的排序，實(shí)際上是直接插入排序，因?yàn)橹苯硬迦肱判蛟诮咏行驎r(shí)時(shí)間復(fù)雜度最小，所以以此進(jìn)行優(yōu)化，gap大于1的排序稱為預(yù)排序。
2、程序
void ShellSort(int* a,size_t size)
{
assert(a);
int gap = size;
while(gap>1)
{
gap = gap/3+1;//保證最后一次gap為1
//多路排序并行
for(int i = 0; i < size-gap; i++)
{
int end = i;
int tmp = a[end + gap];
while(end >= 0 && tmp < a[end])//間距為gap的插入排序
{
a[end+gap] = a[end];
end -= gap;
}
a[end+gap] = tmp;
}
}
}3、時(shí)間復(fù)雜度
時(shí)間復(fù)雜度在O(N)和O(N*N)之間，大概是O(N^1.25 - 1.6N^1.25)。在初始數(shù)組數(shù)據(jù)已經(jīng)接近有序時(shí)，優(yōu)化效率最低。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼