数据结构——哈希排序

哈希排序，就是用空间换取时间的一种排序方式，空间利用率达O（n）。

算法思想

如果一个元素序列a里没有重复的元素，而我们需要找最大值或者前几个最大值时，怎么办呢？
1、将这个a序列排序，然后直接选出目标值；
2、开辟一个b数组，a里的每一个元素对应b数组的下标，并将b数组该下标的元素设置为1。然后将b数组逆序遍历，就能得到目标值。方式2就是哈希排序的思想。
比如a的元素是[5,1,2,3,7],那么就是b[5]、b[1]、b[2]、b[3]、b[7]设置为1，其它位置的元素都是0。然后逆序遍历，从尾部往头开始遍历，先到b[7]时值为1，就输出下标7，以此类推就找到目标值了。
这个排序要求原始序列里元素各不相同，即每个元素都是唯一的。当然，如果有相同的数，那么只会输出一次（除非里面加上个循环输出）。

示例

输入10个不同的数字，找出前三大的值。

10个数字看不出来，貌似用其他排序算法排速度也差不多对吧？那我们大量一点的元素来看看：
如果我们设置28000个不同的数字，用快速排序和哈希排序的方式找出前三大的数字，会怎样呢？
这里我们引入时间函数来计算两者的耗时，得出了如下结果：

强行用空间换取时间很暴力吧？哪怕是用快速排序在28000个不同的元素里找出前三大的数字，都得用60ms，而哈希只需要1ms便完成了任务。

源代码

#include<iostream>
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define maxnum 30000
int a[maxnum];
int b[maxnum];

void haxi(){
	int len;
	cout<<"数组长度？"; 
	cin>>len;
	for(int i=0;i<len;i++){
		cin>>b[i];
		a[b[i]]=1;
	}
	int premax;
	cout<<"找出前几大的数字？"; 
	cin>>premax;
	for(int i=maxnum;i>=0,premax>0;i--){
		if(a[i]==1){
			cout<<i<<" ";
			premax--;
		}
	}
}

int main(){	
	haxi();
	return 0;
}