- 相關推薦
排序算法的算法思想和使用場景總結
總結就是把一個時間段取得的成績、存在的問題及得到的經驗和教訓進行一次全面系統的總結的書面材料，它可以幫助我們有尋找學習和工作中的規律，快快來寫一份總結吧。那么如何把總結寫出新花樣呢？下面是小編收集整理的排序算法的算法思想和使用場景總結，供大家參考借鑒，希望可以幫助到有需要的朋友。
1.概述
排序算法是計算機技術中最基本的算法，許多復雜算法都會用到排序。盡管各種排序算法都已被封裝成庫函數供程序員使用，但了解排序算法的思想和原理，對于編寫高質量的軟件，顯得非常重要。
本文介紹了常見的排序算法，從算法思想，復雜度和使用場景等方面做了總結。
2.幾個概念
（1）排序穩定：如果兩個數相同，對他們進行的排序結果為他們的相對順序不變。例如A={1,2,1,2,1}這里排序之后是A = {1,1,1,2,2}穩定就是排序后第一個1就是排序前的第一個1，第二個1就是排序前第二個1，第三個1就是排序前的第三個1。同理2也是一樣。不穩定就是他們的順序與開始順序不一致。
（2）原地排序：指不申請多余的空間進行的排序，就是在原來的排序數據中比較和交換的排序。例如快速排序，堆排序等都是原地排序，合并排序，計數排序等不是原地排序。
總體上說，排序算法有兩種設計思路，一種是基于比較，另一種不是基于比較。《算法導論》一書給出了這樣一個證明：“基于比較的算法的最優時間復雜度是O（N lg N）”。對于基于比較的算法，有三種設計思路，分別為：插入排序，交換排序和選擇排序。非基于比較的排序算法時間復雜度為O(lg N)，之所以復雜度如此低，是因為它們一般對排序數據有特殊要求。如計數排序要求數據范圍不會太大，基數排序要求數據可以分解成多個屬性等。
3.基于比較的排序算法
正如前一節介紹的，基于比較的排序算法有三種設計思路，分別為插入，交換和選擇。對于插入排序，主要有直接插入排序，希爾排序；對于交換排序，主要有冒泡排序，快速排序；對于選擇排序，主要有簡單選擇排序，堆排序；其它排序：歸并排序。
3.1插入排序
（1）直接插入排序
特點：穩定排序，原地排序，時間復雜度O(N*N)
思想：將所有待排序數據分成兩個序列，一個是有序序列S，另一個是待排序序列U，初始時，S為空，U為所有數據組成的數列，然后依次將U中的數據插到有序序列S中，直到U變為空。
適用場景：當數據已經基本有序時，采用插入排序可以明顯減少數據交換和數據移動次數，進而提升排序效率。
（2）希爾排序
特點：非穩定排序，原地排序，時間復雜度O(n^lamda)(1 < lamda < 2), lamda和每次步長選擇有關。
思想：增量縮小排序。先將序列按增量劃分為元素個數近似的若干組，使用直接插入排序法對每組進行排序，然后不斷縮小增量直至為1，最后使用直接插入排序完成排序。
適用場景：因為增量初始值不容易選擇，所以該算法不常用。
3.2交換排序
（1）冒泡排序
特點：穩定排序，原地排序，時間復雜度O(N*N)
思想：將整個序列分為無序和有序兩個子序列，不斷通過交換較大元素至無序子序列首完成排序。
適用場景：同直接插入排序類似
（2）快速排序
特點：不穩定排序，原地排序，時間復雜度O(N*lg N)
思想：不斷尋找一個序列的樞軸點，然后分別把小于和大于樞軸點的數據移到樞軸點兩邊，然后在兩邊數列中繼續這樣的操作，直至全部序列排序完成。
適用場景：應用很廣泛，差不多各種語言均提供了快排API
3.3選擇排序
（1）簡單選擇排序
特點：不穩定排序（比如對3 3 2三個數進行排序，第一個3會與2交換），原地排序，時間復雜度O(N*N)
思想：將序列劃分為無序和有序兩個子序列，尋找無序序列中的最小（大）值和無序序列的首元素交換，有序區擴大一個，循環下去，最終完成全部排序。
適用場景：交換少
（2）堆排序
特點：非穩定排序，原地排序，時間復雜度O(N*lg N)
思想：小頂堆或者大頂堆
適用場景：不如快排廣泛
3.4其它排序
（1）歸并排序
特點：穩定排序，非原地排序，時間復雜度O(N*N)
思想：首先，將整個序列（共N個元素）看成N個有序子序列，然后依次合并相鄰的兩個子序列，這樣一直下去，直至變成一個整體有序的序列。
適用場景：外部排序
4.非基于比較的排序算法
非基于比較的排序算法主要有三種，分別為：基數排序，桶排序和計數排序。這些算法均是針對特殊數據的，不如要求數據分布均勻，數據偏差不會太大。采用的思想均是內存換時間，因而全是非原地排序。
4.1基數排序
特點：穩定排序，非原地排序，時間復雜度O(N)
思想：把每個數據看成d個屬性組成，依次按照d個屬性對數據排序（每輪排序可采用計數排序），復雜度為O(d*N)
適用場景：數據明顯有幾個關鍵字或者幾個屬性組成
4.2桶排序
特點：穩定排序，非原地排序，時間復雜度O(N)
思想：將數據按大小分到若干個桶（比如鏈表）里面，每個桶內部采用簡單排序算法進行排序。
適用場景：0
4.3計數排序
特點：穩定排序，非原地排序，時間復雜度O(N)
思想：對每個數據出現次數進行技術（用hash方法計數，最簡單的hash是數組！），然后從大到小或者從小到大輸出每個數據。
使用場景：比基數排序和桶排序廣泛得多。
5. 總結
對于基于比較的排序算法，大部分簡單排序(直接插入排序，選擇排序和冒泡排序)都是穩定排序，選擇排序除外；大部分高級排序（除簡單排序以外的）都是不穩定排序，歸并排序除外，但歸并排序需要額外的存儲空間。對于非基于比較的排序算法，它們都對數據規律有特殊要求，且采用了內存換時間的思想。排序算法如此之多，往往需要根據實際應用選擇最適合的排序算法。
【排序算法的算法思想和使用場景總結】相關文章：
解放思想是做好工作的前提和基礎的總結10-10
關于個人思想和工作總結（精選16篇）10-24
思想和業務技術工作總結（精選10篇）10-20
教師教學經驗和思想工作總結11-15
實驗思想總結09-21
犯罪思想總結06-13
思想總結大全09-21
聽課思想總結08-15
教育思想總結08-17