计数排序

\(O(n)\) 级的排序算法存在已久，但他们只能用于特定的场景。计数排序就是一种时间复杂度为 \(O(n)\) 的排序算法，该算法于 1954 1954 年由哈罗德·H·苏厄德（Harold H. Seward）提出。在对一定范围内的整数排序时，它的复杂度为 \(O(n+k)\) （其中 k 是整数的范围大小）。

伪计数排序

特殊的，对于整数数组，可以根据整数本身大小和计数数量来进行排序。

class Solution {
public:
    void countingSortFake1(vector<int>& nums) {
        const int MAX_ELEMENT_VALUE = 10;
        vector<int> counting(MAX_ELEMENT_VALUE, 0);
        for (int num : nums) {
            counting[num]++;
        }
        int j = 0;
        for (int i = 0; i < counting.size(); i++) {
            int k = counting[i];
            while (k-- > 0) {
                nums[j++] = i;
            }
        }
    }
};

算法非常简单，但这里的排序算法 并不是 真正的计数排序。因为现在的实现有一个非常大的弊端：排序完成后，树组中记录的元素已经不再是最开始的那个元素了，他们只是值相等，但却不是同一个对象。

伪计数排序 2.0

对于这个问题，有一个解决方案：在统计元素出现的次数时，同时把真实的元素保存到对应排序值的队列中，输出时从队列中取真实的元素。

class Solution {
public:
    void countingSortFake2(vector<int>& nums) {
        const int MAX_ELEMENT_VALUE = 10;
        unordered_map<int, queue<int>> countingQueueMap;
        for (int num : nums) {
            countingQueueMap[num].push(num);
        }
        int j = 0;
        for (int i = 0; i < MAX_ELEMENT_VALUE; i++) {
            if (countingQueueMap.count(i) > 0) {
                auto& q = countingQueueMap[i];
                while (!q.empty()) {
                    nums[j++] = q.front();
                    q.pop();
                }
            }
        }
    }
};

真正的计数排序

区别在于计数排序并不是把计数数组的下标直接作为结果输出，而是通过计数的结果，计算出每个元素在排序完成后的位置，然后将元素赋值到对应位置。

class Solution {
public:
    void countingSort(vector<int>& nums) {
        const int MAX_ELEMENT_VALUE = 10;
        vector<int> counting(MAX_ELEMENT_VALUE, 0);
        for (int num : nums) {
            counting[num]++;
        }
        int preCount = 0;
        for (int i = 0; i < counting.size(); i++) {
            int tmp = counting[i];
            counting[i] = preCount;
            preCount += tmp;
        }
        vector<int> result(nums.size());
        for (int num : nums) {
            int index = counting[num];
            result[index] = num;
            counting[num]++;
        }
        for (int i = 0; i < result.size(); i++) {
            nums[i] = result[i];
        }
    }
};

• https://leetcode.cn/leetbook/read/sort-algorithms/ozyo63/