資訊專欄INFORMATION COLUMN
在介紹希爾排序之前，先了解一下直接插入排序
x插入一個有序區間
這里end是指向數組最后一個元素
根據上面的單趟排序啟發
end是數組的最后一個元素，end之后的元素都是待排序
一個關鍵的判斷點，end和x比較大小
這里end < x
還需要再做改善
可以發現有兩個循環，一個循環時end倒著遍歷完之后，使得最開始的end結束的數組加入x后是一個有序數組，最后再返回這個新數組的最后一個元素所在位置
注意公共部分
end--；x = a[end + 1];外面是一個for循環，從第二個到最后一個元素
for(i = 0; i < n - 1; i++){ }代碼：
//插入排序void InsetSort(int* a, int n){ int end = 0; int i = 0; for (i = 0; i < n - 1; i++) { end = i; int x = a[end + 1]; while (end >= 0) { if (a[end] > x) { a[end + 1] = a[end]; a[end] = x; } else { break; } end--; } } }時間復雜度O(N2)
測試：
int main(){ int a[4] = { 2, 6, 5, 3 }; InsetSort(a, 4); //ShellSort(a, 4); int i = 0; for (i = 0; i < 4; i++) { printf("%d ", a[i]); } printf("/n"); return 0;}希爾排序法又稱縮小增量法
希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成
gap個組，所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，重復上述分組和排序的工作。當到達gap=1時，所有記錄在統一組內排好序。
希爾排序是根據直接插入排序的基礎上，先進行分組排序
以3個為一組進行排序
時間復雜度：
每次排可以看作長度為gap的數組直接插入排序
一共有gap組，當然并不是每組都是gap/n個元素，但當數據相當多的時候我們看作每個數組都有gap/n個元素
所以是 (1+2……+n/gap)gap
//希爾排序void ShellSort(int* a, int n){ int end = 0; int i = 0; int j = 0; int gap = 6; //預排序 for (j = 0; j < gap; j++) { //最后一個數一定是1 gap = gap / 2; for (i = 0; i < n - gap; i++) { end = i; //這里其實就是直接插入排序，而數組的每個元素間隔是gap int x = a[end + gap]; while (end >= 0) { if (a[end] > x) { a[end + gap] = a[end]; a[end] = x; } else { break; } end -= gap; } } }}測試用例還是上面直接插入排序的例子
結果還是成功的
//性能測試void TestOP(){ srand(time(0)); //以1000個數字為例 const int N = 10000; int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; } //這里clock是運行到這里的時間 int begin1 = clock(); InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); //end-begin為排序所用時間 printf("%d/n%d/n", end1 - begin1, end2 - begin2);}可以看出希爾排序比直接排序快得多，但希爾排序因為gap可以改變，目前沒有一個統一的時間復雜度，先按照時間復雜度為O(n1.3)來吧
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/123611.html
本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀 排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...
摘要：動態定義間隔序列參考來源詳細介紹了十種算法大家可以去學習下以后大概會盡量每天更新一個算法學習吧溫故而知新 參考書:嚴蔚敏-數據結構 希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點: 內排序(內存排序就夠了) 不穩定(排序后原始順序無法保證) 希爾排序重點在于分割. 基本思想: 將整個待排序記錄序...
摘要：常見的內部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數排序等。這里主要介紹希爾排序。一圖勝千言算法介紹算法描述希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進版本。但希爾排序是非穩定排序算法。 常見的內部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數排序等。這里主要介紹希爾排序。 一圖勝千言： showImg(h...
閱讀 2708·2023-04-25 14:59
閱讀 902·2021-11-22 11:59
閱讀 644·2021-11-17 09:33
閱讀 2471·2021-09-27 13:34
閱讀 3904·2021-09-09 11:55
閱讀 2326·2019-08-30 15:44
閱讀 1130·2019-08-30 14:06
閱讀 1930·2019-08-29 16:55
