基本概念

????????排序是對數據進行處理的常見操作，即將數據按某字段規律排列。字段是數據節點的一個屬性，比如學生信息中的學號、分數等，可針對這些字段進行排序。同時，排序算法有穩定性之分，若兩個待排序字段一致的數據在排序前后相對位置不變，則該排序算法是穩定的，否則不穩定。此外，根據數據量與內存的關系，還分為內排序（數據量小，可全部裝入內存處理）和外排序（數據量大，需暫存外存，分批次讀入內存處理）。

一、冒泡排序

（一）核心思想

????????冒泡排序基于相鄰元素比較的思路。從頭到尾讓每兩個相鄰元素進行比較，若順序符合排序要求則保持位置不變，若為逆序則交換位置。經過一輪比較，序列中具有 “極值”（最大值或最小值，取決于排序順序）的數據會被挪至序列末端。

????????例如，對于數組[5, 3, 8, 6, 2]進行升序排序，從第一個元素開始，5 和 3 比較，因為 5 > 3，所以交換位置，數組變為[3, 5, 8, 6, 2]；接著 5 和 8 比較，順序不變；8 和 6 比較，交換位置，數組變為[3, 5, 6, 8, 2]；8 和 2 比較，交換位置，第一輪比較結束后數組變為[3, 5, 6, 2, 8]。可以看到，最大的數 8 被移到了數組末尾。若序列中有n個數據，在最極端情況下，經過n - 1輪比較一定能將所有數據排序完畢。

（二）代碼實現

?
// 冒泡排序，data為數組，len為數組長度
void bubbleSort(int* data, int len) {int i, j;for (i = 0; i < len - 1; i++) {int flag = 1;  // 用于標記某一趟是否有元素交換，若沒有則說明已排序完成for (j = 0; j < len - 1 - i; j++) {if (data[j] > data[j + 1]) {  // 升序排序，若要降序改為data[j] < data[j + 1]int tmp;tmp = data[j];data[j] = data[j + 1];data[j + 1] = tmp;flag = 0;  // 有元素交換，標記為0}}if (flag) {  // 若某一趟沒有元素交換，提前結束排序break;}}
}?

（三）性能分析

????????冒泡排序的時間復雜度為 O(n^2)，其中n是待排序數據的數量。這是因為在最壞情況下，需要進行n - 1輪比較，每輪比較的次數從n - 1逐漸減少到 1。空間復雜度為 O(1)，因為它只需要幾個臨時變量來進行元素交換，不需要額外的大量空間。冒泡排序是一種穩定的排序算法，因為相同元素的相對順序在排序過程中不會改變。

（四）示例圖示

以數組[5, 3, 8, 6, 2]的升序排序為例：

第一輪：

• 比較 5 和 3，交換，數組變為[3, 5, 8, 6, 2]
• 比較 5 和 8，順序不變
• 比較 8 和 6，交換，數組變為[3, 5, 6, 8, 2]
• 比較 8 和 2，交換，數組變為[3, 5, 6, 2, 8]

第二輪：

• 比較 3 和 5，順序不變
• 比較 5 和 6，順序不變
• 比較 6 和 2，交換，數組變為[3, 5, 2, 6, 8]

第三輪：

• 比較 3 和 5，順序不變
• 比較 5 和 2，交換，數組變為[3, 2, 5, 6, 8]

第四輪：

• 比較 3 和 2，交換，數組變為[2, 3, 5, 6, 8]，排序完成。

二、選擇排序

（一）核心思想

????????選擇排序的思路是每一輪從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

????????例如，對于數組[5, 3, 8, 6, 2]進行升序排序，第一輪從數組中找到最小的數 2，與第一個數 5 交換位置，數組變為[2, 3, 8, 6, 5]；第二輪從剩下的[3, 8, 6, 5]中找到最小的數 3，由于它已經在正確位置，無需交換；第三輪從[8, 6, 5]中找到最小的數 5，與 8 交換位置，數組變為[2, 3, 5, 6, 8]；第四輪從[6, 8]中找到最小的數 6，由于它已經在正確位置，無需交換，此時數組已排序完成。

（二）代碼實現

?
// 選擇排序，data為數組，len為數組長度
void selectionSort(int* data, int len) {int i, j, minIndex;for (i = 0; i < len - 1; i++) {minIndex = i;for (j = i + 1; j < len; j++) {if (data[j] < data[minIndex]) {  // 升序排序，若要降序改為data[j] > data[minIndex]minIndex = j;}}if (minIndex != i) {int tmp = data[i];data[i] = data[minIndex];data[minIndex] = tmp;}}
}?

（三）性能分析

????????選擇排序的時間復雜度同樣為 O(n^2)，因為無論數據初始狀態如何，都需要進行n - 1輪選擇和交換操作。空間復雜度為 O(1)，只需要幾個臨時變量。選擇排序是一種不穩定的排序算法，例如數組[5, 5, 3]進行升序排序時，兩個 5 的相對順序可能會改變。

（四）示例圖示

以數組[5, 3, 8, 6, 2]的升序排序為例：

第一輪：

找到最小的 2，與 5 交換，數組變為[2, 3, 8, 6, 5]

第二輪：

在剩下的[3, 8, 6, 5]中找到最小的 3，位置不變

第三輪：

在[8, 6, 5]中找到最小的 5，與 8 交換，數組變為[2, 3, 5, 6, 8]

第四輪：

在[6, 8]中找到最小的 6，位置不變，排序完成。

三、插入排序

（一）核心思想

????????插入排序假設前面已經有i個節點是有序的，那么從第i + 1個節點開始，插入到前面i個節點的合適位置中。由于第一個元素自身總是有序的，因此從第 2 個元素開始，不斷插入前面的有序序列，直到全部排列完畢。

????????例如，對于數組[5, 3, 8, 6, 2]進行升序排序，初始時認為第一個元素 5 是有序的。然后取第二個元素 3，將其與 5 比較，因為 3 < 5，所以將 5 后移一位，把 3 插入到 5 原來的位置，數組變為[3, 5, 8, 6, 2]；接著取第三個元素 8，由于 8 > 5，所以 8 的位置不變，數組仍為[3, 5, 8, 6, 2]；再取第四個元素 6，將其依次與 8、5 比較，找到合適位置插入，數組變為[3, 5, 6, 8, 2]；最后取第五個元素 2，將其依次與 8、6、5、3 比較，找到合適位置插入，數組變為[2, 3, 5, 6, 8]。

（二）代碼實現

?
// 插入排序，data為數組，len為數組長度
void insertionSort(int* data, int len) {int i, j, tmp;for (i = 1; i < len; i++) {tmp = data[i];j = i - 1;while (j >= 0 && data[j] > tmp) {  // 升序排序，若要降序改為data[j] < tmpdata[j + 1] = data[j];j--;}data[j + 1] = tmp;}
}?

（三）性能分析

????????插入排序在最好情況下（數據已經有序）的時間復雜度為 O(n)，因為只需要進行n - 1次比較，無需移動元素。在最壞情況下（數據逆序）的時間復雜度為 O(n^2)，平均時間復雜度也為O(n^2)。空間復雜度為 O(1)，只需要幾個臨時變量。插入排序是一種穩定的排序算法，因為在插入過程中，相同元素的相對順序不會改變。

（四）示例圖示

以數組[5, 3, 8, 6, 2]的升序排序為例：

第一輪：

3 插入到 5 前面，數組變為[3, 5, 8, 6, 2]

第二輪：

8 位置不變，數組仍為[3, 5, 8, 6, 2]

第三輪：

6 插入到 8 前面，數組變為[3, 5, 6, 8, 2]

第四輪：

2 插入到最前面，數組變為[2, 3, 5, 6, 8]，排序完成。

總結

冒泡排序、選擇排序和插入排序都是簡單的排序算法，它們的時間復雜度在最壞情況下都O(n^2)，空間復雜度為O(1)，適用于數據樣本較小的場合。其中，冒泡排序和插入排序是穩定的排序算法，選擇排序是不穩定的排序算法。在實際應用中，可根據數據特點和需求選擇合適的排序算法。