C++中如何实现计数排序(C++,编程语言)

计数排序

计数排序是一种非比较的排序算法

优势：

计数排序在对于一定范围内的整数排序时，时间复杂度为O(N+K) （K为整数在范围）快于任何比较排序算法，因为基于比较的排序时间复杂度在理论上的上下限是O(N*log(N))。

缺点：

计数排序是一种牺牲空间换取时间的做法，并且当K足够大时O（K）>O(N*log(N)),效率反而不如比较的排序算法。并且只能用于对无符号整形排序。

时间复杂度：

O（N） K足够大时为O（K）

空间复杂度：

O（最大数-最小数）

性能：

计数排序是一种稳定排序

代码实现：

#include<iostream>#include<Windows.h>#include<assert.h>usingnamespacestd;//计数排序，适用于无符号整形voidCountSort(int*a,size_tsize){assert(a);size_tmax=a[0];size_tmin=a[0];for(size_ti=0;i<size;++i){if(a[i]>max){max=a[i];}if(a[i]<min){min=a[i];}}size_trange=max-min+1;//要开辟的数组范围size_t*count=newsize_t[range];memset(count,0,sizeof(size_t)*range);//初始化为0//统计每个数出现的次数for(size_ti=0;i<size;++i)//从原数组中取数，原数组个数为size{count[a[i]-min]++;}//写回到原数组size_tindex=0;for(size_ti=0;i<range;++i)//从开辟的数组中读取，开辟的数组大小为range{while(count[i]--){a[index++]=i+min;}}delete[]count;}voidPrint(int*a,size_tsize){for(size_ti=0;i<size;++i){cout<<a[i]<<"";}cout<<endl;}

#include"CountSort.h"voidTestCountSort(){intarr[]={1,2,3,4,5,6,6,6,6,6,6,6,6,6,2,2,2,4,5,8,9,5,11,11,22,12,12};size_tsize=sizeof(arr)/sizeof(arr[0]);CountSort(arr,size);Print(arr,size);}intmain(){TestCountSort();system("pause");return0;}