【C++】排序算法 --快速排序与归并排序

颜色分类（数组分三块思想）

给定⼀个包含红⾊、⽩⾊和蓝⾊、共 n 个元素的数组 nums ，原地对它们进⾏排序，使得相同颜⾊
的元素相邻，并按照红⾊、⽩⾊、蓝⾊顺序排列。
我们使⽤整数 0、 1 和 2 分别表⽰红⾊、⽩⾊和蓝⾊。
必须在不使⽤库的 sort 函数的情况下解决这个问题。
示例 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();//数组分三块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){//递归结束条件if(l >= r) return;//要么区间不存在，要么只剩下一个元素int i = l;int left = l-1,right = r+1;int key = nums[i];//数组分块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){//递归结束条件if(left==right) return;//先分治int mid = (left + right) >> 1;msort(nums,left,mid);msort(nums,mid+1,right);//归并int cur1 = left;//遍历左区间int cur2 = mid+1;//遍历右区间int i = 0;//temp数组使用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}}
};