Counting Sort

• 计数排序的假设：待排序序列各元素均在区间[0, k]上。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> temp{0, 0, 0};
        vector<int> B(nums.size());
        
        //   以下循环操作完成后，temp的第i个位置保存着nums中，值为i的元素的总个数
        for(auto elem:nums)
        {
            temp[elem]++;
        }
        // 以下循环操作完成后，temp的第i个位置保存着nums中，值小于或等于i的元素的总个数
        for(auto i=1; i<temp.size(); ++i)
        {
            temp[i] += temp[i-1];
        }
        //
        for(int i=nums.size()-1; i>-1; --i)
        {
            cout << i << endl;
            B[temp[nums[i]] - 1] = nums[i];
            temp[nums[i]]--; 
        }
        nums = B;
    }
};

总的运行时间是。当时，运行时间为。
结论：可以看出，计数排序的下界优于比较排序算法的下界时间Ω(nlgn)。这是因为计数排序并不是比较排序算法。

参考：https://www.cnblogs.com/dongkuo/p/4832849.html