排序【各種題型+對應LeetCode習題練習】

常用排序

快速排序

歸并排序

LeetCode 912 排序數組

LeetCode 912 排序數組

常用排序

快速排序

LeetCode 912 排序數組

歸并排序

LeetCode 912 排序數組

名稱	排序方式	時間復雜度	是否穩定
快速排序	分治	O(n log n)	否
歸并排序	分治	O(n log n)	是
冒泡排序	交換	O(n2)	是
插入排序	插入	O(n2)	是
選擇排序	選擇最值	O(n2)	否
C++ STL sort	快排+內省排序	O(n log n)	否
C++ STL stable_sort	歸并排序	O(n log n)	是

快速排序的核心思想是分治法，所以我們先來了解什么是分治

分治（Divide and Conquer）是一種常見的算法設計思想，核心是三步：
Divide（劃分）
把一個大問題劃分成若干個小問題，通常是遞歸進行的。
Conquer（解決）
把每個子問題單獨解決，直到子問題足夠小，可以直接解決。
Combine（合并）
將子問題的解合并，得到原問題的解。

快速排序就是一個經典的分治應用：

步驟	具體操作
Divide（劃分）	從數組中選一個基準值pivot，把數組劃分成兩部分：左邊：所有小于等于 pivot 的元素右邊：所有大于 pivot 的元素
Conquer（遞歸排序）	對左子數組和右子數組分別遞歸快速排序
Combine（組合）	排序完成后，把左右子數組 + pivot 合成一個完整的有序數組

快速排序 C++ 手寫模板（雙指針+原地交換）

void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return;  // 遞歸終止條件int pivot = nums[left];     // 選擇最左側元素作為基準int i = left + 1, j = right;while (i <= j) {// 找到左邊大于 pivot 的位置while (i <= j && nums[i] <= pivot) i++;// 找到右邊小于 pivot 的位置while (i <= j && nums[j] > pivot) j--;if (i < j) swap(nums[i], nums[j]);  // 交換兩個指針位置的值}swap(nums[left], nums[j]);  // 將 pivot 放到正確位置quickSort(nums, left, j - 1);  // 排左邊quickSort(nums, j + 1, right); // 排右邊
}

調用方式：

vector<int> nums = {4, 2, 7, 1, 5};
quickSort(nums, 0, nums.size() - 1);

思路：
1. 選擇一個基準值 pivot（通常選最左邊的值）
2. 雙指針 i / j 從兩邊往中間找：
i 找第一個大于 pivot 的數
j 找第一個小于等于 pivot 的數
如果 i < j，就交換
3.?最后把 pivot 放到分界點位置 → 即 j 位置
4.?遞歸地快排左邊、右邊子數組
?

class Solution {
public:void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return;int pivot = nums[left];     // 選最左邊為 pivotint i = left + 1, j = right;while (i <= j) {while (i <= j && nums[i] <= pivot) i++; while (i <= j && nums[j] > pivot) j--;  if (i < j) swap(nums[i], nums[j]);      }swap(nums[left], nums[j]);  quickSort(nums, left, j - 1);  quickSort(nums, j + 1, right); }vector<int> sortArray(vector<int>& nums) {quickSort(nums, 0, nums.size() - 1);return nums;}
};

上面的代碼的基準值 pivot 選擇了最左邊的值，如果提交到LeetCode，會有部分案例超出時間限制，比如nums =?[3, 2, 2, 2, ..., 2]? ?這里的2有上千個，快速排序在該極端情況下退化成 O(n2)?
因為數組中大量元素與 pivot 相等，導致“遞歸深度很深”、“每次只處理一點點”，最終就退化成了冒泡排序，時間復雜度變為 O(n2)。

解決方案是改成隨機選 pivot，防止極端退化
這種隨機選擇基準值位置的方法在全是 2 的子數組中能夠高概率選中中間位置的 2 作為基準值，劃分后左右子數組長度 ≈ n/2，時間復雜度平均為?O(n log n)

class Solution {
public:void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return;// 隨機選一個 pivot，避免最壞情況int randomIndex = rand() % (right - left + 1) + left;swap(nums[left], nums[randomIndex]);int pivot = nums[left];int i = left + 1, j = right;while (i <= j) {while (i <= j && nums[i] <= pivot) i++;while (i <= j && nums[j] > pivot) j--;if (i < j) swap(nums[i], nums[j]);}swap(nums[left], nums[j]);quickSort(nums, left, j - 1);quickSort(nums, j + 1, right);}vector<int> sortArray(vector<int>& nums) {srand(time(0)); quickSort(nums, 0, nums.size() - 1);return nums;}
};

但是上面的時間復雜度是平均為 O(n log n)，可以使用三路快排，它針對大量重復值時更高效，即小于 pivot 的放左邊，等于 pivot 的放中間，大于 pivot 的放右邊
這種方法時間復雜度始終為 O(n log n)

class Solution {
public:void quickSort3Way(vector<int>& nums, int left, int right) {if (left >= right) return;// 隨機選 pivot，放到最左邊int randomIndex = rand() % (right - left + 1) + left;swap(nums[left], nums[randomIndex]);int pivot = nums[left];int lt = left;       // 小于 pivot 的最后位置int i = left + 1;    // 當前掃描的位置int gt = right;      // 大于 pivot 的起始位置while (i <= gt) {if (nums[i] < pivot) {swap(nums[i], nums[lt + 1]);lt++;i++;} else if (nums[i] > pivot) {swap(nums[i], nums[gt]);gt--;} else {  // nums[i] == pivoti++;}}swap(nums[left], nums[lt]);// 遞歸左右兩邊quickSort3Way(nums, left, lt - 1);quickSort3Way(nums, gt + 1, right);}vector<int> sortArray(vector<int>& nums) {srand(time(0));quickSort3Way(nums, 0, nums.size() - 1);return nums;}
};

上面代碼將數組劃分為三部分：
[left, lt-1]（小于pivot）、[lt, gt]（等于pivot）、[gt+1, right]（大于pivot）

假設輸入為 [3, 2, 2, 2, 2, 4, 1]
pivot = 2
lt 區（<2）：[1]
= 區（=2）：[2,2,2,2]
gt 區（>2）：[3,4]
遞歸只需要再排 [1] 和 [3,4]，大量相等的值不需要再遞歸，消除了重復元素對性能的影響。

下面來模擬三路快排的劃分過程
數組為 [3, 2, 2, 2, 2, 4, 1]? 假設 pivot = 2（隨機選中了值為 2 的元素，放到了最左邊位置）

快排前準備狀態：

變量	值	說明
pivot	2	基準值，隨機選后放最左邊
lt	0	< pivot 區右邊界
i	1	當前正在看的元素位置
gt	6	> pivot 區左邊界
nums	[2, 3, 2, 2, 2, 4, 1]	初始數組，pivot = 2 放在最左邊

三路快排過程跟蹤表

最后i=5 > gt=4? 跳出循環
循環結束后處理 pivot
swap(nums[left], nums[lt]) → 把 pivot 放回等于區前端
交換前：[2, 1, 2, 2, 2, 4, 3]
交換后：[1, 2, 2, 2, 2, 4, 3]

最終分區情況

區域	元素	含義
< pivot 區	[1]	nums[0]
= pivot 區	[2, 2, 2, 2]	nums[1~4]
> pivot 區	[4, 3]	nums[5~6]

然后遞歸：
左邊：quickSort3Way(nums, 0, 0) → 單個元素，無需處理
右邊：quickSort3Way(nums, 5, 6) → 處理 [4, 3]

歸并排序是穩定排序的經典算法，時間復雜度穩定為 O(n log n)，適用于大規模數據的排序。
歸并排序采用的是分治法

歸并排序流程
假設要排序的數組為 [38, 27, 43, 3, 9, 82, 10]
分解階段：
將數組分成兩半： [38, 27, 43] 和 [3, 9, 82, 10]
繼續遞歸分解，直到每個子數組只剩一個元素。
合并階段：
合并 [38] 和 [27]，得到 [27, 38]
合并 [43] 和 [27, 38]，得到 [27, 38, 43]
對右半部分繼續類似的操作。
最終合并：
將兩個有序的子數組 [27, 38, 43] 和 [3, 9, 10, 82] 合并成一個有序的數組 [3, 9, 10, 27, 38, 43, 82]

> pivot → 與 gt=6 交換

[2, 1, 2, 2, 2, 4, 3]

< pivot → 與 lt+1 交換

[2, 1, 2, 2, 2, 4, 3] （1 與自己）

= pivot → i++

[2, 1, 2, 2, 2, 4, 3]

= pivot → i++

[2, 1, 2, 2, 2, 4, 3]

= pivot → i++

[2, 1, 2, 2, 2, 4, 3]

> pivot → 與 gt=5 交換

[2, 1, 2, 2, 2, 4, 3]（不變）

思路：
1. 使用歸并排序的方法：
遞歸地將數組分解為兩部分。
合并時保持數組的順序。
2. 合并時，比較左右兩部分的元素，確保數組有序。

class Solution {
public:
void merge(vector<int>& nums, int left, int mid, int right) {int n1 = mid - left + 1;  // 左子數組的大小int n2 = right - mid;     // 右子數組的大小vector<int> leftArr(n1), rightArr(n2);  // 創建兩個臨時數組// 復制數據到臨時數組for (int i = 0; i < n1; i++) leftArr[i] = nums[left + i];for (int i = 0; i < n2; i++) rightArr[i] = nums[mid + 1 + i];// 合并兩個臨時數組到原數組numsint i = 0;      // 左子數組索引int j = 0;      // 右子數組索引int k = left;   // 原數組起始索引while (i < n1 && j < n2) {  // 如果左子數組和右子數組還有元素if (leftArr[i] <= rightArr[j]) {nums[k] = leftArr[i];  // 左邊小的放到原數組i++;} else {nums[k] = rightArr[j]; // 右邊小的放到原數組j++;}k++;}// 復制剩余的元素while (i < n1) {   nums[k] = leftArr[i];i++;k++;}while (j < n2) {  nums[k] = rightArr[j];j++;k++;}
}void mergeSort(vector<int>& nums, int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;// 遞歸分割數組mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并兩個有序子數組merge(nums, left, mid, right);}vector<int> sortArray(vector<int>& nums) {mergeSort(nums, 0, nums.size() - 1);return nums;}
};

nums = [5, 2, 3, 1]?

初始數組：[5,2,3,1]
調用 mergeSort(0,3)
├─ 計算 mid=1
├─ 調用 mergeSort(0,1) ?// 處理 [5,2]
│ ?├─ 計算 mid=0
│ ?├─ 調用 mergeSort(0,0) → 終止（[5]）
│ ?├─ 調用 mergeSort(1,1) → 終止（[2]）
│ ?└─ 合并 → [2,5]
├─ 調用 mergeSort(2,3) ?// 處理 [3,1]
│ ?├─ 計算 mid=2
│ ?├─ 調用 mergeSort(2,2) → 終止（[3]）
│ ?├─ 調用 mergeSort(3,3) → 終止（[1]）
│ ?└─ 合并 → [1,3]
└─ 合并 [2,5] 和 [1,3] → [1,2,3,5]