现在的位置: 首页 > 综合 > 正文

排序N个比N^7小的数,要求的算法是O(n)

2014年02月13日 ⁄ 综合 ⁄ 共 459字 ⁄ 字号 评论关闭

采用基数排序,用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。

在内存有限制的情况下,如果采用位图来解决实际问题,而若全部放入位图,可能导致内存使用量比较大。这个时候,我们可以分块来解决,最后再合并起来,得到最终的结果。

抱歉!评论已关闭.