给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
计算排序在使用上很大程度类似hashmap，可以理解为一个有固定长度的hashmap，key是从最小值到最大值，为value就是值出现的次数，没有出现过的为0
为了简单，通常使用数组或者vector代替hashmap
1. 很大的计数排序
std::vector<int> CLeetCode_Solution::sortArray(vector<int>& nums) { //计数排序 int N = nums.size(); //定义所有有效数据总数稍微大点（最大值减去最小值）这就是桶 vector<int> counter(100010, 0); for (int n : nums) { //为了桶下标的从0开始+5000，也就在counter中下标是实际值+5000 //而counter[m]则表示该值出现的次数 counter[n + 50000] ++; } vector<int> res(nums.size()); int idx = 0; //循环整个桶，将数据赋值到res中 for (int i = 0; i < 100010; ++i) { for (int j = 0; j < counter[i]; ++j) { res[idx++] = i - 50000; } } return res; }
2.优化的计数排序
优化的桶就是把 mapsum 的大小固定到最大值和最小值的范围 int len = nums.size();
int minVal = INT_MAX; int maxVal = INT_MIN;
//找出最大最小值 for (int i = 0; i < len; i++) { minVal = min(nums[i], minVal); maxVal = max(nums[i], maxVal); }
//建立vec int mapsum = maxVal - minVal + 1; vector<int> hmap(mapsum); for (int i = 0; i < len;++i) { //下标为实际值-minval, hmap[0]为最小值; 值为数量，如果值没有出现，该处hmap的值为0，将不计入返回值
hmap[nums[i] - minVal]++; } int inx = 0; for (int i = 0; i < mapsum;++i) { for (int j = 0;j < hmap[i];++j) { //hmap的下标+minval就是原始的值 nums[inx++] = i + minVal; } } return nums;