C++数据结构与算法之排序桶排序

桶排序的基本思想

原来：把数值记作桶号，遍历整个数组，将相应的桶进行计数
第一步：遍历原数组，找到最大值max，并且申请max+1个桶，初始化为0（下标从0到max），即vector bucket(max+1,0);
第二步：遍历原数组，找到每个数值对应的桶号，并对桶计数++，即bucket[vec[i]]++；
第三步：遍历桶数组，看对应的桶内计数为几就取出几个下标值，放到原数组，即while(bucker[i]–) vec[index++]=bucket[i];

桶排序的代码

intfindMax(vector<int>&vec){if(vec.size()==0)return INT_MIN;int max= vec[0];for(int i=1;i<vec.size();i++){ 		max= max>vec[i]?max:vec[i];}return max;}voidbucketSort(vector<int>&vec){int max=findMax(vec); 	vector<int>bucket(max+1,0);//遍历原数组，对桶进行计数for(int i=0;i<vec.size();i++){ 		bucket[vec[i]]++;}//遍历桶，得到排序结果for(int i=0;i<bucket.size();i++){int index=0;while(bucket[i]--){ 				vec[index++]= bucket[i];}}}