时间复杂度替O(N),空间复杂度为O(1)的排序算法

时间复杂度为O(N),空间复杂度为O(1)的排序算法

#include "stdafx.h"
#include "iostream"
using namespace std;
/*
//hashSort排序算法的时间复杂度为O(N),空间复杂度为O(1)
//在数字范围有限制的情况下，是有一个这样的算法的，只需要用一个数组记录每个数字出现次数就可以了。
//假定你的数字范围在0到65535范围之内，定义一个数组count[65536]（这个空间是常量，和n无关，所以是O(1))，初值全部为0。
*/
void hashSort(int a[],int n)
{
	int max = a[0];
	int min = a[0];
	for (int i = 0; i < n; i ++)//找出最大值与最小值//
	{
		if(max <= a[i])
			max = a[i];
		if(min >= a[i])
			min = a[i];
	}

	int * hash = new int[max - min + 1];//创建数组//
	for (int i = 0; i < max-min+1; i ++)
		*(hash + i) = 0;

	for (int i = 0; i < n; i ++)//记录每个数出现的次数//
		(*(hash+a[i] - min))++;
	int j = 0;
	for (int i = 0; i < max - min +1; i ++)
	{
		while ((*(hash + i)) --)//出现k次，重复k次//
			a[j++] = i+min;
	}
	delete [] hash;
}

void print(int a[], int n)
{
	for (int i = 0; i < n; i ++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int a[] = {1,4,3,2,1,1,5,2,3,4,5};
	int len = sizeof(a)/sizeof(a[0]);
	hashSort(a,len);
	print(a,len);
	return 0;
}