哈希表计数排序算法_哈希表排序

  利用哈希表计数实现排序的算法，待排数组所有元素的数值为key，出现的次数为value，遍历数组所有元素将每个元素及每个元素出现的次数更新到哈希表中并且求出数组最大值和最小值。历即以最小值为起始位置进行遍历，若当前值在哈希表中存在，则得到当前值出现的次数n，在新数组（新数组可以新建也可以直接使用待排数组）尾部加入n个当前值，直到遍历到最大值时程序结束，新数组即为排好序的数组。若从大到小排序反向遍可。
    该算法时间复杂度为O(n+k)，k为数组最大值和最小值之差，k越小排序效率越高，k最小为1，最好的情况下遍历次数等于数组长度加1。当最大值和最小值之差越大时k也就越大，速度就越慢；此算法处理各元素之差较小的数组效率最高，在k值小于10000时，排序速度多数情况比STL的sort()算法快。
    当待排数组无重读元素时创建的哈希表长度最大，此时哈希表等于待排数组长度，空间复杂度为O(n)，重复数字越多哈希表长度越小，当待排数组元素全部相同时哈希表长度最小，此时长度为1，空间复杂度O(1)，平均空间复杂度为O(n);（网上有类似的哈希表计数排序算法，其思想和此文章的思想差不多，只是哈希表操作和最终遍历部分有些差别，导致哈希表长度不可控，容易造成较大的空间浪费）

/*
 * main.cpp
 *
 *  Created on: 2022年8月18日
 *      Author: Administrator
 */
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <ctime>
#include <numeric>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
void has(vector<int>& nums){
	unordered_map<int,int> map;
	int ma = nums[0], mi = nums[0];        //ma为待排数组最大值，mi为待排数组最小值
	for(int i=0;i<nums.size();i++){        //遍历待排数组
		//TODO
		ma = max(ma,nums[i]);                //寻找最大值
		mi = min(mi,nums[i]);                //寻找最小值
		map[nums[i]] += 1;					//哈希表中记录nums[i]出现次数
	}
	vector<int> hashnum;
	hashnum.reserve(nums.size());            //预留空间，减少扩容次数
	for(int i=mi;i<=ma;++i){				//从最小值遍历到最大值
		if(map.find(i) != map.end()){        //判断哈希表中是否存在以key值为i的元素
			//TODO
			hashnum.insert(hashnum.end(),map[i],i);    //将map[i]个i插入到新数组尾部
		}
	}
}
 
 
int getRand(int min, int max) {							//随机数生成
    return ( rand() % (max - min + 1) ) + min ;
}
 
 
 
int main() {
	vector<int> nums(50000,0);
	for(int i=0;i<50000;i++){          //生成五万个随机数用于测试
		//TODO
		nums[i] = getRand(0,1000); //最大值和最小值的差越小哈希表排序效率越高,时间复杂度O(n),n为最大值和最小值的差
	}
	vector<int> num(nums);
	long long start = clock();     
	has(num);
	long long end = clock();
	cout<<"哈希表排序: "<<(end - start) * 1000 / CLOCKS_PER_SEC<<"ms"<<endl;    //计时
	return 0;
}
 
 
 

  当待排序的元素不是纯数字时怎么办呢？
    如对象Student,包含年龄，姓名；对Student按年龄大小进行排序，此时以年龄为key，将一个Student的链表作为哈希表的value，遇到年龄相同的Student时直接插到前一个Students的后面，遍历时也是从最小年龄开始计数，当此年龄在哈希表中存在时，遍历value中的链表，按顺序将链表中的Student加入到新数组中。此时的时间复杂度仍为O(n+k)，k最小为待排数组的长度；空间复杂度也同样为O(n),只不过此时链表元素个数永远等于待排数组的元素个数，空间复杂度比纯数字排序要高一些;由于value中的链表是按照待排数组的遍历顺序排列的，如果遍历待排数组时采用从前向后遍历，则此排序算法稳定，若遍历待排数组时采用从后向前遍历则不稳定。