劃重點：特定算法是依賴特定的數據結構的，帶著問題去學習，是最有效的學習方法

本節分析冒泡排序、插入排序、選擇排序三種排序算法

如何分析一個排序算法？

分析一個排序算法，要從以下幾個方面入手：

排序算法的執行效率

最好、最壞、平均時間復雜度：給出最好情況、最壞情況、平均情況下的時間復雜度。除此之外，你還要說出最好、最壞時間復雜度對應的要排序的原始數據是什么樣的。

時間復雜度的系：系數、常數、低階：時間復雜度反應的是數據規模n很大時候的增長趨勢，常常忽略了系數、常數、低階。但是實際開發中排序的可能是規模很小的數據例如100個、1000個，因此對比算法性能時候需要考慮系數、常數、低階

比較次數和交換（移動）次數：基于比較的排序算法的執行過程，會涉及兩種操作，一是元素比較大小，二是元素交換或移動，因此分析排序算法的執行效率的時候，應該把比較次數和交換（或移動）次數也考慮進去

排序算法的內存消耗

內存消耗可以通過空間復雜度來衡量。對于排序算法的空間復雜度，引入原地排序這個概念。原地排序算法，就是特指空間復雜度是 O(1) 的排序算法。

排序算法的穩定性

針對排序算法，我們還有一個重要的度量指標，穩定性。這個概念是說，如果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變。這個概念是說，如果待排序的序列中存在值相等的元素，經過排序之后，相等元素之間原有的先后順序不變。

舉例：有一組數據 2，9，3，4，8，3，按照大小排序之后就是 2，3，3，4，8，9。這組數據里有兩個 3。經過某種排序算法排序之后，如果兩個 3 的前后順序沒有改變，那我們就把這種排序算法叫作穩定的排序算法；如果前后順序發生變化，那對應的排序算法就叫作不穩定的排序算法。

為什么有時候需要穩定的排序算法？

很多數據結構和算法課程，在講排序的時候，都是用整數來舉例，但在真正軟件開發中，我們要排序的往往不是單純的整數，而是一組對象，我們需要按照對象的某個 key 來排序。比如說，要給電商交易系統中的“訂單”排序。訂單有兩個屬性，一個是下單時間，另一個是訂單金額。如果我們現在有 10 萬條訂單數據，我們希望按照金額從小到大對訂單數據排序。對于金額相同的訂單，我們希望按照下單時間從早到晚有序。對于這樣一個排序需求，我們怎么來做呢？

方法一：先按照金額對訂單數據進行排序，然后，再遍歷排序之后的訂單數據，對于每個金額相同的小區間再按照下單時間排序。這種排序思路理解起來不難，但是實現起來會很復雜。

方法二：先按照下單時間給訂單排序，注意是按照下單時間，不是金額。排序完成之后，用穩定排序算法，按照訂單金額重新排序。兩遍排序之后，我們得到的訂單數據就是按照金額從小到大排序，金額相同的訂單按照下單時間從早到晚排序的；穩定排序算法可以保持金額相同的兩個對象，在排序之后的前后順序不變。

分析排序算法的三個問題：是原地排序算法嗎？是穩定的排序算法嗎？時間復雜度是多少？

冒泡排序（Bubble Sort）

• 冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都會對相鄰的兩個元素進行比較，看是否滿足大小關系要求。如果不滿足就讓它倆互換
• 一次冒泡會讓至少一個元素移動到它應該在的位置，重復 n 次，就完成了 n 個數據的排序工作

冒泡過程還可以優化：當某次冒泡操作已經沒有數據交換時，說明已經達到完全有序，不用再繼續執行后續的冒泡操作。

冒泡排序的實現代碼如下：

//冒泡排序算法 a表示數組，n表示數組大小public static void bubbleSort(int[] a, int n) {if (n <= 1) return;for (int i = 0; i < n; i++) {for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {int temp = a[j];a[j] = a[j + 1];a[j+1] = temp;}}}}

冒泡排序算法回答：

• 冒泡的過程只涉及相鄰數據的交換操作，只需要常量級的臨時空間，所以它的空間復雜度為 O(1)，是一個原地排序算法
• 在冒泡排序中，只有交換才可以改變兩個元素的前后順序。為了保證冒泡排序算法的穩定性，當有相鄰的兩個元素大小相等的時候，我們不做交換，相同大小的數據在排序前后不會改變順序，所以冒泡排序是穩定的排序算法
• 最好情況時間復雜度是 O(n)。而最壞的情況是，要排序的數據剛好是倒序排列的，我們需要進行 n 次冒泡操作，所以最壞情況時間復雜度為 O(n2)
• 平均時間復雜度分析：n個數據有n!種組合順序

數組有序情況下改進版冒泡排序算法

public void bubbleSort(int arr[]) {boolean flag;for(int i = 0, len = arr.length; i < len - 1; i++) {didSwap = false;for(int j = 0; j < len - i - 1; j++) {if(arr[j + 1] < arr[j]) {swap(arr, j, j + 1);flag= true;}}if(flag == false)return;} }

對于包含 n 個數據的數組，這 n 個數據就有 n! 種排列方式。不同的排列方式，冒泡排序執行的時間肯定是不同的。比如我們前面舉的那兩個例子，其中一個要進行 6 次冒泡，而另一個只需要 4 次。如果用概率論方法定量分析平均時間復雜度，涉及的數學推理和計算就會很復雜。這里一種思路，通過“有序度”和“逆序度”這兩個概念來進行分析。

有序度是數組中具有有序關系的元素對的個數。有序元素對用數學表達式表示就是這樣：有序元素對：a[i] <= a[j], 如果i < j。

逆序度的定義正好跟有序度相反（默認從小到大為有序）：對于一個倒序排列的數組，比如 6，5，4，3，2，1，有序度是 0；對于一個完全有序的數組，比如 1，2，3，4，5，6，有序度就是 n*(n-1)/2，也就是 15。我們把這種完全有序的數組的有序度叫作滿有序度。關于這三個概念，我們還可以得到一個公式：逆序度 = 滿有序度 - 有序度。我們排序的過程就是一種增加有序度，減少逆序度的過程，最后達到滿有序度，就說明排序完成了。

冒泡排序包含兩個操作原子，比較和交換。每交換一次，有序度就加 1。不管算法怎么改進，交換次數總是確定的，即為逆序度，也就是n*(n-1)/2–初始有序度。此例中就是 15–3=12，要進行 12 次交換操作。最壞情況初始的有序度是0，進行n*(n-1)/2交換操作。最好情況下不需要進行交換。平均情況下，需要 n*(n-1)/4 次交換操作，比較操作肯定要比交換操作多，而復雜度的上限是 O(n2)，所以平均情況下的時間復雜度就是 O(n2)。這個平均時間復雜度推導過程其實并不嚴格，但是很多時候很實用，畢竟概率論的定量分析太復雜不實用。快排時會再次用這種“不嚴格”的方法來分析平均時間復雜度。

插入排序（Insertion Sort）

有序數組插入一個數據，找到對應的位置然后進行數據搬移，接著插入數據即可。

插入排序的核心：

• 將數組中的數據分為兩個區間，已排序區間和未排序區間
• 初始已排序區間只有一個元素，就是數組的第一個元素。
• 核心思想是取未排序區間中的元素，在已排序區間中找到合適的插入位置將其插入，并保證已排序區間數據一直有序。重復這個過程，直到未排序區間中元素為空，算法結束。

示意圖：

插入排序也包含兩種操作，一種是元素的比較，一種是元素的移動。當我們需要將一個數據 a 插入到已排序區間時，需要拿 a 與已排序區間的元素依次比較大小，找到合適的插入位置。找到插入點之后，我們還需要將插入點之后的元素順序往后移動一位，這樣才能騰出位置給元素 a 插入。對于不同的查找插入點方法（從頭到尾、從尾到頭），元素的比較次數是有區別的。但對于一個給定的初始序列，移動操作的次數總是固定的，就等于逆序度。

插入排序代碼：

//插入排序算法 a表示數組，n表示數組大小public static void InsertionSort(int[] a, int n) {if (n <= 1) return;for (int i = 1; i < n; i++) {int value = a[i];int j = i - 1;//查找插入的位置for (; j >= 0; --j) {if (a[j] > value) {a[j + 1] = a[j];//數據移動} else {break;}}a[j + 1] = value;//插入數據}}

總結：插入排序不需要額外的存儲空間，因此是原地排序算法，空間復雜度O（1）；插入排序可以選擇將后面出現的元素，插入到前面出現元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩定的排序算法；

插入排序的時間復雜度：如果要排序的數據已經是有序的，我們并不需要搬移任何數據。如果我們從尾到頭在有序數據組里面查找插入位置，每次只需要比較一個數據就能確定插入的位置。所以這種情況下，最好是時間復雜度為 O(n)。注意，這里是從尾到頭遍歷已經有序的數據；數組是倒序的，每次插入都相當于在數組的第一個位置插入新的數據，所以需要移動大量的數據，所以最壞情況時間復雜度為 O(n2)。

選擇排序（Selection Sort）

選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。但是選擇排序每次會從未排序區間中找到最小的元素，將其放到已排序區間的末尾。

選擇排序空間復雜度為 O(1)，是一種原地排序算法。選擇排序的最好情況時間復雜度、最壞情況和平均情況時間復雜度都為 O(n2)。你可以自己來分析看看。選擇排序是一種不穩定的排序算法。從我前面畫的那張圖中，你可以看出來，選擇排序每次都要找剩余未排序元素中的最小值，并和前面的元素交換位置，這樣破壞了穩定性。

問題思考：插入排序和冒泡排序的時間復雜度相同，都是 O(n2)，在實際的軟件開發里，為什么我們更傾向于使用插入排序算法而不是冒泡排序算法呢？

解答：冒泡排序不管怎么優化，元素交換的次數是一個固定值，是原始數據的逆序度。插入排序是同樣的，不管怎么優化，元素移動的次數也等于原始數據的逆序度。但是，從代碼實現上來看，冒泡排序的數據交換要比插入排序的數據移動要復雜，冒泡排序需要 3 個賦值操作，而插入排序只需要 1 個。

冒泡排序中數據的交換操作： if (a[j] > a[j+1]) { // 交換int tmp = a[j];a[j] = a[j+1];a[j+1] = tmp;flag = true; }插入排序中數據的移動操作： if (a[j] > value) {a[j+1] = a[j]; // 數據移動 } else {break; }

我們把執行一個賦值語句的時間粗略地計為單位時間（unit_time），然后分別用冒泡排序和插入排序對同一個逆序度是 K 的數組進行排序。用冒泡排序，需要 K 次交換操作，每次需要 3 個賦值語句，所以交換操作總耗時就是 3*K 單位時間。而插入排序中數據移動操作只需要 K 個單位時間。雖然冒泡排序和插入排序在時間復雜度上是一樣的，都是 O(n2)，但是如果我們希望把性能優化做到極致，那肯定首選插入排序。

評價一個排序算法，需要從執行效率、內存消耗和穩定性三個方面來看

我們今天講的幾種排序算法，都是基于數組實現的。如果數據存儲在鏈表中，這三種排序算法還能工作嗎？如果能，那相應的時間、空間復雜度又是多少呢？

一般而言，考慮只能改變節點位置，冒泡排序相比于數組實現，比較次數一致，但交換時操作更復雜；插入排序，比較次數一致，不需要再有后移操作，找到位置后可以直接插入，但排序完畢后可能需要倒置鏈表；選擇排序比較次數一致，交換操作同樣比較麻煩。綜上，時間復雜度和空間復雜度并無明顯變化，若追求極致性能，冒泡排序的時間復雜度系數會變大，插入排序系數會減小，選擇排序無明顯變化。

總結

以上是生活随笔為你收集整理的11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。