采用基数排序,用10个桶(vector),每一个桶用队列表示(queue),分别代表0-9,然后依次从低位到高位开始将要排序的数倒入桶中,然后再顺序取出来,直到排序完成。
若有5个数,12,4,5,130,28
第一次(个位):
0: 130
1
2: 12
3
4: 4
5: 5
6
7
8 :28
9
然后顺序取出来,130, 12, 4, 5, 28
第二次(十位),没有十位视作0
0: 4 5
1: 12
2: 28
3: 130
4
5
6
7
8
9
然后顺序取出来,4 5 12 28 130
第三次(百位),没有百位视作0
0: 4 5 12 28
1: 130
2
3
4
5
6
7
8
9
然后顺序取出来,4 5 12 28 130
第四次(千位),都为0,退出
扩展:若内存限制1M,数字无重复,怎么处理
由于每一个数小于10^7,若用位图,扫描一遍所有数,然后根据位图输出即可,位图所用内存不超过1M,可以两次位图,先0-499999,再50000-1000000。
在内存有限制的情况下,如果采用位图来解决实际问题,而若全部放入位图,可能导致内存使用量比较大。这个时候,我们可以分块来解决,最后再合并起来,得到最终的结果。