算法思路

1. 插入排序的改進(jìn)版，選擇插入距離遠(yuǎn)的元素
2. 選擇一個(gè)間距，將序列分成很多子序列并行插入排序
3. 降低間距，并重復(fù)插入元素，直到間距將為1，完成排序。

算法實(shí)現(xiàn)

void shell_sort(vector<int> &arr, int beg, int gap) {//gap為1時(shí)即直接插入排序for (int i = beg + gap; i< arr.size(); i += gap) {int tem = arr[i];int j = i - gap;for (;j >=0 && tem < arr[j]; j -= gap) {arr[j+gap] = arr[j];}arr[j+gap] = tem;}
}void shell(vector<int> &arr) {int gap = arr.size() / 2;while(gap > 0) {int beg = gap - 1;while(beg >=0) {//使用當(dāng)前gap，將所有元素位置按照要求進(jìn)行調(diào)整shell_sort(arr, beg, gap);beg --;}gap /= 2;}
}

算法分析

時(shí)間復(fù)雜度：時(shí)間復(fù)雜度和增量gap有關(guān)，當(dāng)gap為1時(shí)，為直接插入排序O(n^2)
希爾排序開始時(shí)增量較大，分組較多，每組的記錄數(shù)目少，各組直接插入較快
gap逐漸減小，分組減少，各組記錄的數(shù)目增多，但由于已按照d[i-1]進(jìn)行排序，則新的排序數(shù)組效率也很高；
希爾排序整體的時(shí)間復(fù)雜度為O(n^3/2)

空間復(fù)雜度：O(1)保存元素

總結(jié)

以上是生活随笔為你收集整理的希尔排序 算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。