為了讓大家掌握多種排序方法的基本思想，本篇文章帶著大家對數(shù)據(jù)結構的常用七大算法進行分析：包括直接插入排序、希爾排序、冒泡排序、快速排序、簡單選擇排序、堆排序、歸并排序等，并能夠用高級語言實現(xiàn)。

希望通過對這些算法效率的比較，加深對算法的理解。

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

排序算法的分析圖解：

用隨機數(shù)（介于1-100）產(chǎn)生10個待排序數(shù)據(jù)元素的關鍵字值）。

① 采用直接插入排序和希爾排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

② 采用冒泡排序、快速排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

③ 采用簡單選擇排序、堆排序方法對上述待排數(shù)據(jù)進行排序并輸出序后的有序序列；

④ 采用歸并排序方法對上述待排數(shù)據(jù)進行排序并輸出排序后的有序序列；

代碼分析

頭文件：

①插入排序

②折半插入排序

③選擇排序

④起泡排序

⑤快速排序

⑥希爾排序

⑦堆排序

⑧歸并排序

隨機生成函數(shù)

輸出函數(shù)

結論

（1）若n較?。ɡ鏽<50），可采用直接插入排序、冒泡排序或簡單選擇排序。如果記錄中的數(shù)據(jù)較多，移動較費時的，應采取簡單選擇排序法。

（2）若記錄的初始狀態(tài)已經(jīng)按關鍵碼基本有序，則選用直接插入排序或冒泡排序法為宜。

（3）若n較大，則應采用改進排序方法，如快速排序、堆排序或歸并排序法。這些排序算法的時間復雜度均為O(nlog2n)，但就平均性能而言，快速排序被認為是目前基于比較記錄關鍵碼的內(nèi)部排序中最好的排序方法，但遺憾的是，快速排序在最壞情況下的時間復雜度是O(n2)，堆排序與歸并排序的最壞情況時間復雜度仍為O(nlog2n)。堆排序和快速排序法都是不穩(wěn)定的排序。若要求穩(wěn)定排序，則可選用歸并排序。

（4）基數(shù)排序可在O (d×n) 時間內(nèi)完成對n個記錄的排序，d是指單邏輯關鍵碼的個數(shù)，一般遠少于n。但基數(shù)排序只適用于字符串和整數(shù)這類有明顯結構特征的關鍵碼。

（5）前面討論的排序算法，除基數(shù)排序外，都是在順序存儲上實現(xiàn)的。當記錄本身的信息量很大時，為避免大量時間用在移動數(shù)據(jù)上，可以用鏈表作為存儲結構。插入排序和歸并排序都易在鏈表上實現(xiàn)，但有的排序方法，如快速排序和堆排序在鏈表上卻很難實現(xiàn)。

寫在最后：對于準備學習C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

微信公眾號：C語言編程學習基地

C語言零基礎入門教程（83集全）

整理分享（多年學習的源碼、項目實戰(zhàn)視頻、項目筆記，基礎入門教程）

歡迎轉(zhuǎn)行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！

編程學習視頻分享：

粉絲編程交流：