排序算法实战（上）
一、引言
在力扣刷题的旅程中，排序类题目是绕不开的重要板块。今天就来分享两道经典排序题——912. 排序数组和75. 颜色分类的解题思路与代码实现，带你深入理解排序算法在实际题目中的应用 。
二、题目剖析与解题思路
（一）912. 排序数组
题目要求
给定整数数组 nums ，需在不使用内置排序函数、时间复杂度为 O(nlog(n)) 且空间复杂度尽可能小的条件下，将数组升序排列。
解题思路——快速排序
快速排序是分治思想的典型应用，平均时间复杂度为 O(nlog(n)) ，空间复杂度主要是递归栈空间，合理实现可做到较小空间占用。
1. 划分分区：从数组中选取一个基准值（ key ），通过一趟遍历，将数组分成两部分，小于基准值的元素放到左边，大于基准值的放到右边。这里为了避免最坏情况（如数组有序时基准值选两端导致时间复杂度退化到 O(n²) ），采用随机选取基准值的方式（ get 函数实现）。
2. 递归排序：对划分后的左右两个子数组，递归地进行快速排序操作，直到子数组长度为 1（递归终止条件），此时数组自然有序。
（二）75. 颜色分类
题目要求
给定包含 0 （红）、 1 （白）、 2 （蓝）的数组 nums ，需原地排序，使相同颜色相邻，且按红、白、蓝顺序排列，同时不能使用内置 sort 函数。
解题思路——三指针法
利用三个指针来划分不同颜色区域，实现一次遍历完成排序，时间复杂度 O(n) ，空间复杂度 O(1) （原地排序）。
- L 指针标记 0 区域的右边界， R 指针标记 2 区域的左边界， i 指针用于遍历数组。
- 遍历过程中：遇到 0 ，和 L 指针右侧元素交换，同时 L 右移、 i 右移（因为交换来的元素已遍历过，可直接处理下一个）；遇到 1 ，直接 i 右移；遇到 2 ，和 R 指针左侧元素交换， R 左移，但 i 不右移（交换来的元素未遍历过，需重新判断） 。
三、代码实现（C++）
（一）912. 排序数组（快速排序实现）
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;class Solution {
public:vector<int> sortArray(vector<int>& nums) {srand(time(NULL)); // 初始化随机数种子，用于随机选基准值qsort(nums, 0, nums.size() - 1);return nums;}void qsort(vector<int>& nums, int l, int r) {if (l >= r) return; // 递归终止条件，子数组长度为1int i = l, left = l - 1, right = r + 1;int key = get(nums, l, r); // 获取随机基准值while (i < right) {if (nums[i] < key) swap(nums[++left], nums[i++]);else if (nums[i] == key) i++;else swap(nums[--right], nums[i]);}qsort(nums, l, left); // 递归排序左子数组qsort(nums, right, r); // 递归排序右子数组}int get(vector<int>& nums, int l, int r) {int t = rand();return nums[t % (r - l + 1) + l]; // 随机选取基准值}
};
（二）75. 颜色分类（三指针法实现）
#include <vector>
using namespace std;class Solution {
public:void sortColors(vector<int>& nums) {int L = -1, R = nums.size(); // L 初始为 -1，R 初始为数组长度for (int i = 0; i < R;) { // i 遍历数组，R 左侧是未处理区域if (nums[i] == 0) swap(nums[++L], nums[i++]);else if (nums[i] == 1) i++;else if (nums[i] == 2) while (nums[i] == 2 && i < R) swap(nums[i], nums[--R]);}}
};
四、总结
- 912. 排序数组借助快速排序，通过随机选基准值优化，在平均情况下满足 O(nlog(n)) 时间复杂度要求，实现高效排序；
- 75. 颜色分类利用三指针法，巧妙划分不同颜色区域，一次遍历完成排序，时间复杂度 O(n) ，空间复杂度 O(1) ，非常适合这类特定元素（只有 0、1、2 ）的排序场景。
刷题过程中，理解算法思想并灵活运用到不同题目场景至关重要，大家可以多尝试不同解法，加深对排序算法的掌握，助力力扣刷题之路～ 后续也会继续分享更多有趣的力扣题目解法，欢迎持续关注呀！