计数排序适用的应用场景: 量大但是范围小(全省高考成绩、某大型企业数万名员工年龄的排序) 且知道范围(例如成绩满分和零分 年龄0岁到150岁)
方法: 1、创建另外一个数组用于*计数***,数组的大小则为数值范围加1 (0~100)则数组长度为100-0+1 = 101; 因为我们要用数组的索引值(下标)作为每一个数值所对应的“家”**斜体样式 正好从0开始到100; 2、接着我们遍历原数组,每次读到与计数数组的下标值一样的数值时,则对计数数组改下标所对应的数组值加1(count[ nums[0] ]++);
#include <iostream>
using namespace std;
class Solution {
public:
int sort_arr(vector<int> &nums, int min, int max)
{
int len = nums.size();
int length= max -min +1;
int count[length] ;
for(int i = 0; i < len; i++)
{
count[nums[i]]++;
}
for(int j = 0, k=0; j<length; j++)
{
while(count[i]-- > 0)
nums[k++] = i;
}
for(int i = 0; i<len; i++)
{
cout<<"排序后的数组值为:"<< nums[i]<<endl;
}
return 0;
}
以上代码存在缺陷:1、要排序的数值不是从0开始 怎么办??? 2、要求排序后的相同的数值在原数组和先数组的顺序相同该怎么处理???
|