溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
1、如何進行希爾排序
希爾排序是直接插入排序的優化，具體實現是先進行以gap間隔分別進行排序，將數組排成快要接近有序，最后一次gap為1的排序，實際上是直接插入排序，因為直接插入排序在接近有序時時間復雜度最小，所以以此進行優化，gap大于1的排序稱為預排序。
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、時間復雜度
時間復雜度在O(N)和O(N*N)之間，大概是O(N^1.25 - 1.6N^1.25)。在初始數組數據已經接近有序時，優化效率最低。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
