???????????成長路上不孤單😊😊😊😊😊😊
【😊///計算機愛好者😊///持續分享所學😊///如有需要歡迎收藏轉發///😊】
今日分享關于C++中常用的排序方法之4——希爾排序的相關內容！
關于【C++中常用的排序方法之4——希爾排序】
目錄：
- 一、希爾排序的定義
- 二、希爾排序的發展歷史
- 三、希爾排序的的排序過程
- 四、希爾排序的基本原理
- 五、希爾排序的的特點
- 六、希爾排序的的優點
- 七、希爾排序的的缺點
希爾排序（Shell Sort）
一、希爾排序的定義
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進版本。希爾排序是非穩定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。
??
二、希爾排序的發展歷史
希爾排序按其設計者希爾（Donald Shell）的名字命名，該算法由希爾在 1959 年所發表的論文“A high-speed sorting procedure”?中所描述。
希爾排序是基于插入排序的以下兩點性質而提出改進方法的：?
?1、插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率。
2、但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位。
1961年，IBM 公司的女程序員 Marlene Metzner Norton（瑪琳·梅茨納·諾頓）首次使用?FORTRAN?語言編程實現了希爾排序算法。在其程序中使用了一種簡易有效的方法設置希爾排序所需的增量序列：第一個增量取待排序記錄個數的一半，然后逐次減半，最后一個增量為 1。該算法后來被稱為 Shell-Metzner 算法?，Metzner 本人在2003年的一封電子郵件中說道：“我沒有為這種算法做任何事，我的名字不應該出現在算法的名字中。”
三、希爾排序的排序過程
1、縮小增量
希爾排序屬于插入類排序,是將整個有序序列分割成若干小的子序列分別進行插入排序。
排序過程：先取一個正整數d1數組元素放一組，組內進行直接插入排序；然后取d2
三趟結果
04 13 27 38 49 49 55 65 76 97
2、Shell排序
Shell排序的算法實現:
1． 不設監視哨的算法描述
void ShellPass(SeqList R，int d)
{//希爾排序中的一趟排序，d為當前增量
for(i=d+1;i
if(R[ i ].key
R[0]=R[i];j=i-d； //R[0]只是暫存單元，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]； //后移記錄
j=j-d； //查找前一記錄
}while(j＞0&&R[0].key
R[j+d]=R[0]； //插入R到正確的位置上
} //endif
該方法實質上是一種分組插入方法
比較相隔較遠距離（稱為增量）的數，使得數移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換。D.L.shell于1959年在以他名字命名的排序算法中實現了這一思想。算法先將要排序的一組數按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序，然后再用一個較小的增量對它進行分組，在每組中再進行排序。當增量減到1時，整個要排序的數被分成一組，排序完成。
一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
給定實例的shell排序的排序過程
假設待排序文件有10個記錄，其關鍵字分別是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次為：
5，2，1
四、?希爾排序的基本原理?
希爾排序是基于插入排序的一種改進算法。它將整個待排序的記錄序列分割成若干子序列，分別進行直接插入排序。然后逐漸減小間隔，再次進行插入排序，直到整個序列變為有序。希爾排序通過分組插入的方式，每次比較相距較遠的元素，從而減少了逆序對的數量，提高了排序效率。
五、希爾排序的特點
希爾排序?是一種高效的排序算法，由美國計算機科學家Donald Shell于1959年提出。它是插入排序的一種改進版本，通過分組插入排序和縮小增量的方式，大幅度減少了逆序對的數量，從而提高了排序效率。以下是希爾排序的主要特點：
??分組插入排序?：希爾排序將數組分成若干個子序列，每個子序列通過插入排序進行排序。由于子序列的長度較短，插入排序的時間復雜度較低，從而提高了排序效率?。
?縮小增量?：希爾排序通過逐步縮小增量（通常采用二分法遞減增量），將數組分成更小的子序列進行排序。增量最終減小到1時，整個數組進行一次插入排序?。
?大幅度減少逆序對?：由于希爾排序是通過間隔分組進行插入排序的，每次排序都會將相距較遠的元素進行比較和交換，從而大幅度減少了逆序對的數量。逆序對的數量是衡量一個排序算法效率的重要指標，逆序對越少，排序效率越高?。
?非穩定性?：希爾排序是一種非穩定的排序算法。在排序過程中，相同大小的元素可能會發生交換，導致原來相對順序的改變。盡管如此，希爾排序在實際應用中并不影響排序結果的正確性?。
?適用場景?：希爾排序適用于大部分情況，尤其適用于部分有序的數據集。當數據集接近有序時，希爾排序的效率非常高?。?
六、希爾排序的優點
?希爾排序的優點主要包括以下幾個方面?：?
?減少比較次數?：希爾排序通過分組插入的方式進行排序，每次比較相距較遠的元素，從而大幅度減少了逆序對的數量，提高了排序效率。
?高效處理大數據量?：希爾排序在處理大量數據時表現出色，其時間復雜度通常為O(n^1.3)，并且空間復雜度為O(1)，這意味著它需要的額外空間非常小。
?簡單易實現?：希爾排序的實現相對簡單，易于理解和編寫代碼。
?適用于大規模數據?：希爾排序特別適合處理大規模數據，因為它通過分組和逐步減小增量來排序，避免了直接對整個數據集進行排序的時間和空間復雜度過高的問題。
七、希爾排序的缺點
?非穩定性?：希爾排序是一種非穩定的排序算法，可能會改變相同元素的相對順序。
?性能受增量序列影響?：增量序列的選擇對希爾排序的性能有很大影響。如果增量序列選擇不當，可能會導致時間復雜度退化為O(n^2)甚至更差。
?時間復雜度不確定?：希爾排序的時間復雜度并不固定，通常認為是O(n^1.3)，但最壞情況下可能會更差。
七、插入排序的缺點
?插入排序的主要缺點包括以下幾個方面?：
?時間復雜度較高?：插入排序的時間復雜度在最壞的情況下是O(n^2)，其中n是待排序元素的數量。這意味著當數據量較大時，插入排序的效率會顯著下降，不適合處理大規模數據集?。
?不適用于部分有序的數據?：雖然插入排序在數據部分有序的情況下表現較好，但如果數據已經接近排序狀態，其他排序算法（如歸并排序或快速排序）通常會更高效?。
?不穩定?：插入排序是一種不穩定的排序算法，相同的元素在排序后可能會改變它們原有的順序。這意味著如果輸入數組中有重復的元素，排序后這些元素的相對順序可能會發生變化?。
?不適合實時應用?：由于插入排序的時間復雜度較高，它不適合需要快速響應的應用場景，如實時數據處理系統?。
