排序【各种题型+对应LeetCode习题练习】

常用排序

快速排序

归并排序

LeetCode 912 排序数组

LeetCode 912 排序数组

常用排序

快速排序

LeetCode 912 排序数组

归并排序

LeetCode 912 排序数组

名称	排序方式	时间复杂度	是否稳定
快速排序	分治	O(n log n)	否
归并排序	分治	O(n log n)	是
冒泡排序	交换	O(n²)	是
插入排序	插入	O(n²)	是
选择排序	选择最值	O(n²)	否
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(n²)
因为数组中大量元素与 pivot 相等，导致“递归深度很深”、“每次只处理一点点”，最终就退化成了冒泡排序，时间复杂度变为 O(n²)。

解决方案是改成随机选 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]