1、Word 排序算法的算法思想和使用場景總結 排序算法的算法思想和使用場景總結 1. 概述 排序算法是計算機技術中最基本的算法，很多簡單算法都會用到排序。盡管各種排序算法都已被封裝成庫函數(shù)供程序員使用，但了解排序算法的思想和原理，對于編寫高質量的軟件，顯得特別重要。 本文介紹了常見的排序算法，從算法思想，簡單度和使用場景等方面做了總結。 2. 幾個概念 （1）排序穩(wěn)定：假如兩個數(shù)相同，對他們進行的排序結果為他們的相對挨次不變。例如A=1,2,1,2,1這里排序之后是A = 1,1,1,2,2 穩(wěn)定就是排序后第一個1就是排序前的第一個1，其次個1就是排序前其次個1，第三個1就是排序前的第三個1。同

2、理2也是一樣。不穩(wěn)定就是他們的挨次與開頭挨次不全都。 （2）原地排序：指不申請多余的空間進行的排序，就是在原來的排序數(shù)據(jù)中比較和交換的排序。例如快速排序，堆排序等都是原地排序，合并排序，計數(shù)排序等不是原地排序。 總體上說，排序算法有兩種設計思路，一種是基于比較，另一種不是基于比較。算法導論一書給出了這樣一個證明：“基于比較的算法的最優(yōu)時間簡單度是O（N lg N）”。對于基于比較的算法，有三種設計思路，分別為：插入排序，交換排序和選擇排序。非基于比較的排序算法時間簡單度為O(lg N)，之所以簡單度如此低，是由于它們一般對排序數(shù)據(jù)有特別要求。如計數(shù)排序要求數(shù)據(jù)范圍不會太大，基數(shù)排序要求數(shù)據(jù)可以

3、分解成多個屬性等。 3. 基于比較的排序算法 正如前一節(jié)介紹的，基于比較的排序算法有三種設計思路，分別為插入，交換和選擇。對于插入排序，主要有直接插入排序，希爾排序；對于交換排序，主要有冒泡排序，快速排序；對于選擇排序，主要有簡潔選擇排序，堆排序；其它排序：歸并排序。 3.1 插入排序 （1） 直接插入排序 特點：穩(wěn)定排序，原地排序，時間簡單度O(N*N) 思想：將全部待排序數(shù)據(jù)分成兩個序列，一個是有序序列S，另一個是待排序序列U，初始時，S為空，U為全部數(shù)據(jù)組成的數(shù)列，然后依次將U中的數(shù)據(jù)插到有序序列S中，直到U變?yōu)榭铡?適用場景：當數(shù)據(jù)已經(jīng)基本有序時，采納插入排序可以明顯削減數(shù)據(jù)交換和數(shù)據(jù)

4、移動次數(shù)，進而提升排序效率。 （2）希爾排序 特點：非穩(wěn)定排序，原地排序，時間簡單度O(nlamda)(1 lamda 2), lamda和每次步長選擇有關。 思想：增量縮小排序。先將序列按增量劃分為元素個數(shù)近似的若干組，使用直接插入排序法對每組進行排序，然后不斷縮小增量直至為1，最終使用直接插入排序完成排序。 適用場景：由于增量初始值不簡單選擇，所以該算法不常用。 3.2 交換排序 （1）冒泡排序 特點：穩(wěn)定排序，原地排序，時間簡單度O(N*N) 思想：將整個序列分為無序和有序兩個子序列，不斷通過交換較大元素至無序子序列首完成排序。 適用場景：同直接插入排序類似 （2）快速排序 特點：不穩(wěn)定

5、排序，原地排序，時間簡單度O(N*lg N) 思想：不斷查找一個序列的樞軸點，然后分別把小于和大于樞軸點的數(shù)據(jù)移到樞軸點兩邊，然后在兩邊數(shù)列中連續(xù)這樣的操作，直至全部序列排序完成。 適用場景：應用很廣泛，差不多各種語言均供應了快排API 3.3 選擇排序 （1）簡潔選擇排序 特點：不穩(wěn)定排序（比如對3 3 2三個數(shù)進行排序，第一個3會與2交換），原地排序，時間簡單度O(N*N) 思想：將序列劃分為無序和有序兩個子序列，查找無序序列中的最小（大）值和無序序列的首元素交換，有序區(qū)擴大一個，循環(huán)下去，最終完成全部排序。 適用場景：交換少 （2） 堆排序 特點：非穩(wěn)定排序，原地排序，時間簡單度O(N*

6、lg N) 思想：小頂堆或者大頂堆 適用場景：不如快排廣泛 3.4 其它排序 （1） 歸并排序 特點：穩(wěn)定排序，非原地排序，時間簡單度O(N*N) 思想：首先，將整個序列（共N個元素）看成N個有序子序列，然后依次合并相鄰的兩個子序列，這樣始終下去，直至變成一個整體有序的序列。 適用場景：外部排序 4. 非基于比較的排序算法 非基于比較的排序算法主要有三種，分別為：基數(shù)排序，桶排序和計數(shù)排序。這些算法均是針對特別數(shù)據(jù)的，不如要求數(shù)據(jù)分布勻稱，數(shù)據(jù)偏差不會太大。采納的思想均是內存換時間，因而全是非原地排序。 4.1 基數(shù)排序 特點：穩(wěn)定排序，非原地排序，時間簡單度O(N) 思想：把每個數(shù)據(jù)看成d個

7、屬性組成，依次根據(jù)d個屬性對數(shù)據(jù)排序（每輪排序可采納計數(shù)排序），簡單度為O(d*N) 適用場景：數(shù)據(jù)明顯有幾個關鍵字或者幾個屬性組成 4.2 桶排序 特點：穩(wěn)定排序，非原地排序，時間簡單度O(N) 思想：將數(shù)據(jù)按大小分到若干個桶（比如鏈表）里面，每個桶內部采納簡潔排序算法進行排序。 適用場景：0 4.3 計數(shù)排序 特點：穩(wěn)定排序，非原地排序，時間簡單度O(N) 思想：對每個數(shù)據(jù)消失次數(shù)進行技術（用hash方法計數(shù)，最簡潔的hash是數(shù)組?。缓髲拇蟮叫』蛘邚男〉酱筝敵雒總€數(shù)據(jù)。 使用場景：比基數(shù)排序和桶排序廣泛得多。 5. 總結 對于基于比較的排序算法，大部分簡潔排序(直接插入排序，選擇排序和冒泡排序)都是穩(wěn)定排序，選擇排序除外；大部分高級排序