c++时间复杂度为O(n)的排序。

只适用与小数据量的排序，因为需要分配待排序数组中最大值与最小值之差大小的空间。

#include “stdio.h”
/*
以char数组做为例子，对数组元素对应的ascii码（0-255）来排序，分配空间256，
*/
void pigeonhole(char* arr, int len)
{
/*数组元素全部初始化为0*/
int hole[256]={0};
int index=0;
/*将数组中元素对应ascii值为基数的hole数组中的值自加*/
for(int i=0; i<len; i++)
{
hole[(int)arr[i]]++;
}

for(int j=0; j<256; j++)
{
/*下面for循环可以处理数组中的重复元素，比如待排序数组有3个值为a元素，那么hole[97]=3*/
for(int k=0; k<hole[j]; k++)
{
arr[index++]=(char)j;
}
}

}