计数排序

计数排序应用场景

计数排序只适用于**的序列的排序**，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。

步骤

1. 先找出序列中最大值和最小值，计算出计数数组的范围
2. 遍历序列，统计出现的次数
3. 为了使排序具有稳定性（保证相同值的前后顺序），计数数组累计求和，累计和就是该元素要存放的位置
4. 倒叙遍历序列，查找该元素存放的位置（）

代码实现

#include <iostream>  
#include <vector>  
#include <climits>  
#include <algorithm> //min_element(),max_element()返回下标
using std::cout;  
using std::endl;  
using std::vector;  
  
void countSort(const vector<int>& nums, vector<int>& result) {  
    if (nums.empty()) {  
        return; // 如果输入为空，则直接返回，避免不必要的操作  
    }  
    
    //int maxNum = *max_element(nums.begin(), nums.end());
    //int minNum = *min_element(nums.begin(), nums.end());
   
    int maxNum = nums[0];  
    int minNum = nums[0];  
    for (int num : nums) {  
        if (num > maxNum) {  
            maxNum = num;  
        }  
        if (num < minNum) { // 不需要else if，因为可能同时遇到更大和更小的数  
            minNum = num;  
        }  
    }  
    int range = maxNum - minNum + 1;  
      
    vector<int> countVec(range, 0);  //此时记录的是出现的次数
    for (int num : nums) {  
        ++countVec[num - minNum];  
    }  
  
    // 累积计数，注意从第二个元素开始（index为1）  
    for (size_t i = 1; i < countVec.size(); ++i) {  
        countVec[i] += countVec[i - 1];  //此时元素下标代表元素，而元素值代表应该放置的位置
    }  
      
    // 反向遍历输入数组，以便稳定排序  
    result.resize(nums.size());  
    for (int i = nums.size() - 1; i >= 0; --i) {  
        result[countVec[nums[i] - minNum] - 1] = nums[i]; // 特别注意索引调整  
        --countVec[nums[i] - minNum]; // 递减计数  
    }  
}  
  
void printVec(const vector<int>& nums) {  
    for (int num : nums) {  
        cout << num << ' ';  
    }  
    cout << endl;  
}  
  
int main() {  
    vector<int> nums = {22, 22, 21, 16, 29};  
    printVec(nums);  
      
    vector<int> result;  
    countSort(nums, result);  
    printVec(result);  
  
    return 0;  
}

时间复杂度：O ( N + r a n g e ) 空间复杂度：O ( r a n g e ) 。