哈希排序算法

说明

哈希算法是一种以空间换取时间的算法。

下面以一个例题的方式来进一步说明这个算法。

• 时间复杂度 O(n)

例题

问题描述

HDU 1425 “Sort”

给你n个整数，请按从大到小的顺序输出其中前m大的数。

输入：每组数据有两行，第一行有两个数n和m(0<n,m<1000000)，第2行包含n个各不相同，且都处于区间[-500000,500000]的整数

输出：对每组测试数据从大到小的顺序排列并输出前m大的数

输入样例：
5 3
3 -35 92 213 -644

输出样例：
213 92 3

问题分析

对于本问题有以下信息

• 区间长度为1000001
• 从大到小输出
• 只输出m个
• 没有相同的数

在没有相同的数的情况下，我们很显然可以用哈希算法排序，且这个数组的大小为1000001。

具体思路就是，在输入数字t的时候，在数组a[500000+t]处标记为1，然后从数组最后开始向前检索，即a[i]处为1则输出500000-i,并依次打印m个这个数

题解

#include <bits/stdc++.h>

using namespace std;

//数组大小
#define MAXSIZE 1000001

//因为全局部分释放在堆中，所以数组写这里可以开得更大
int a[MAXSIZE];

int main()
{
	int n,m;
	
	//因为本题数据较大，所以用ci比较慢改用scanf
	while(~scanf("%d%d",&n,&m))
	{
		//将数组全部置为0以方便后面标记a[i]
		memset(a,0,sizeof(a));
		
		for(int i=0; i<n; i++)
		{
			int t;
			scanf("%d",&t);
			
			//关键步骤
			a[500000+t] = 1;	//数字t,标记在这个位置，这样相当于在存放的时候就已经排好序了
		}
		
		//开始从后往前检索m个数
		for(int i=MAXSIZE-1; m>0; --i)
		{
			//若该处有标记
			if(a[i])
			{
				if(m>1)
					printf("%d ", i-500000);
				else
					printf("%d\n", i-500000);	//最后一个数要换行单独处理
				
				--m;	//因为要输出m个数，所以每输出一次，m依次自减1
			}
			
			
		}
		
	}
	
	return 0;
}

 今天不讲题目，直接给大家介绍一个听起来就很高大上的算法：哈希排序。

 哈希排序是一种排序算法，方法是运用一个数组来记录需要排序的数中某个数是否出现过，也就是将该组数和数组的下标进行对应，从而实现排序。

听起来很麻烦是不是？话不多说，我们直接上代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000001;
int a[MAXN];        //数组a用来记录某个数是否出现过 
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){//输入n个数，输出从大到小的m个数(有多组数)
        memset(a,0,sizeof(a));  //数组充置为0 
        for(int i=0;i<n;i++){
            int t;
            scanf("%d",&t);  
            a[t]=1;        //某个数出现过就把相应的数标记为1 
        }
        for(int i=MAXN;m>0;i--){    //查找最大的m个数，从后往前找 
            if(a[i]){    //代表i这个数出现过 
                if(m>1)                 
                    {printf("%d",i);}
                else      //m=1时换行，要输出下一组 
                    {printf("%d\n",i);}
                m--;
            }
        }
    }
    return 0;

}

（使用语言：c++）

 通过上述代码，我们就可以实现将输入的数变为从大到小的多组数并输出了。

代码编写：刘泽溪

原理解释：孔浙凭

排版：徐庆尧