一、引言

在力扣刷題的旅程中，排序類題目是繞不開的重要板塊。今天就來分享兩道經典排序題——912. 排序數組和75. 顏色分類的解題思路與代碼實現，帶你深入理解排序算法在實際題目中的應用 。

二、題目剖析與解題思路

（一）912. 排序數組

題目要求

給定整數數組 ?nums?，需在不使用內置排序函數、時間復雜度為 ?O(nlog(n))??且空間復雜度盡可能小的條件下，將數組升序排列。

解題思路——快速排序

快速排序是分治思想的典型應用，平均時間復雜度為 ?O(nlog(n))??，空間復雜度主要是遞歸棧空間，合理實現可做到較小空間占用。

1.?劃分分區：從數組中選取一個基準值（?key?），通過一趟遍歷，將數組分成兩部分，小于基準值的元素放到左邊，大于基準值的放到右邊。這里為了避免最壞情況（如數組有序時基準值選兩端導致時間復雜度退化到 ?O(n2)??），采用隨機選取基準值的方式（?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 ）的排序場景。

刷題過程中，理解算法思想并靈活運用到不同題目場景至關重要，大家可以多嘗試不同解法，加深對排序算法的掌握，助力力扣刷題之路～ ?后續也會繼續分享更多有趣的力扣題目解法，歡迎持續關注呀！