每日一道算法题--leetcode 75--颜色分类--C++(快排)

【题目描述】

【方法一：计数排序】

最简单的思路是扫描一遍数组分别对三个类别的数量做个统计，然后再按照每类的数量给数组赋值即可。代码如下：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left=0;
        int right=nums.size()-1;
        sec(nums);
    }
void sec(vector<int>& nums){
    int a=0;
    int b=0;
    int c=0;
    for(int i=0;i<nums.size();i++){
        if(nums[i]==0){
            a++;
        }else if(nums[i]==1){
            b++;  
        }else if(nums[i]==2){
            c++;
        }  
    }
    for(int i=0;i<a;i++){
        nums[i]=0;
    }
    for(int i=a;i<a+b;i++){
        nums[i]=1;
    }
    for(int i=a+b;i<nums.size();i++){
        nums[i]=2; 
    }
}
};

【方法2：快排】

换个思路的话，这道题其实就是排序，我想到的是快排，是排序中的基础方法,顺便就练习一下。把数组中的第一个元素作为哨，我们知道一趟快排结束之后，哨将找到它最终排序所在的位置，再递归的对哨左边和右边进行快排即可。简单介绍一下快排，图片来自百度百科：

代码为：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left=0;
        int right=nums.size()-1;
        Qsort(nums,left,right);
    }
    void Qsort(vector<int>& a, int low, int high){
    if(low >= high)
    {
        return;
    }
    int first = low;
    int last = high;
    int key = a[first];
 
    while(first < last)
    {
        while(first < last && a[last] >= key)
        {
            --last;
        }
 
        a[first] = a[last];
 
        while(first < last && a[first] <= key)
        {
            ++first;
        }
         
        a[last] = a[first];    
    }
    a[first] = key;
    Qsort(a, low, first-1);
    Qsort(a, first+1, high);
}
};