顏色分類（數(shù)組分三塊思想）

給定?個包含紅?、??和藍?、共 n 個元素的數(shù)組 nums ，原地對它們進?排序，使得相同顏?
的元素相鄰，并按照紅?、??、藍?順序排列。
我們使?整數(shù) 0、 1 和 2 分別表?紅?、??和藍?。
必須在不使?庫的 sort 函數(shù)的情況下解決這個問題。
示例 1：
輸?：nums = [2,0,2,1,1,0]
輸出：[0,0,1,1,2,2]

class Solution {
public:void sortColors(vector<int>& nums) {int i = 0;int left = i-1;int right = nums.size();//數(shù)組分三塊while(i<right){if(nums[i] == 1) i++;else if(nums[i] == 0) {swap(nums[i],nums[++left]);i++;}else swap(nums[i],nums[--right]);}}
};

快速排序

類似于前序遍歷，先分塊，再分治。

class Solution {
public:vector<int> sortArray(vector<int>& nums) {qsort(nums,0,nums.size()-1);return nums;}void qsort(vector<int>& nums,int l,int r){//遞歸結(jié)束條件if(l >= r) return;//要么區(qū)間不存在，要么只剩下一個元素int i = l;int left = l-1,right = r+1;int key = nums[i];//數(shù)組分塊while(i < right){if(nums[i]==key) i++;else if(nums[i]< key) {swap(nums[i],nums[++left]);i++;}else swap(nums[i],nums[--right]);}//分治qsort(nums,l,left);qsort(nums,right,r);}
};

歸并排序

類似于后序遍歷，先分治，再歸并。

class Solution {
public:vector<int> temp;vector<int> sortArray(vector<int>& nums) {temp.resize(nums.size());msort(nums,0,nums.size()-1);return nums;}void msort(vector<int>& nums,int left,int right){//遞歸結(jié)束條件if(left==right) return;//先分治int mid = (left + right) >> 1;msort(nums,left,mid);msort(nums,mid+1,right);//歸并int cur1 = left;//遍歷左區(qū)間int cur2 = mid+1;//遍歷右區(qū)間int i = 0;//temp數(shù)組使用while(cur1 <= mid && cur2 <= right){if(nums[cur1]>nums[cur2]) temp[i++] = nums[cur2++];else temp[i++] = nums[cur1++];}while(cur1 <= mid) temp[i++] = nums[cur1++];while(cur2 <= right) temp[i++] = nums[cur2++];for(int i =left;i <=right ;i++){nums[i] = temp[i-left];//i-left == 0}}
};