一、引言

在力扣刷题的旅程中，排序类题目是绕不开的重要板块。今天就来分享两道经典排序题——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 ）的排序场景。

刷题过程中，理解算法思想并灵活运用到不同题目场景至关重要，大家可以多尝试不同解法，加深对排序算法的掌握，助力力扣刷题之路～  后续也会继续分享更多有趣的力扣题目解法，欢迎持续关注呀！