一个时间复杂度O(n)，空间复杂度为O(1)的排序算法

lexingsen

发布于 2022-02-24 10:43:50

1.3K00

代码可运行

文章被收录于专栏：乐行僧的博客乐行僧的博客

运行总次数：0

代码可运行

其实就是利用Hash的思想，开辟一个固定长度的hash数组用于标记待排序数组的数据元素是否出现过。由于固定长度的hash数组，所以空间复杂度与待排序数组数据规模n没有关系，也就是说空间复杂度为O(1)。

#include <iostream>
using namespace std;
//排序能力，[0,65535]区间的数字，你也可以试试更大的
const int MAXN = 65535;
bool hash[MAXN];

template<typename T>
void Sort(T arr[],int n){
	fill(hash,hash+MAXN,false);
	//时间复杂度为O(n)
	for(int i=0;i<n;++i){
		hash[arr[i]] = true;//标记arr[i]出现过
	}
	//时间复杂度为O(MAXN)
	int k=0;
	for(int i=0;i<MAXN;++i){
		if(hash[i] == true){
			arr[k++] = i;
		}
	}
	总的时间复杂度为O(n+MAXN),即O(n)
}

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

int main(){
	int arr [] = {5,6,9,2,3,7,4,1,8};
	int n = sizeof(arr)/sizeof(arr[0]);
	show(arr,n);
	return 0;
}