这里运用了一种方法,使用一个计数数组来存储这个数字出现了多少次。
举个例子:0,2,3,5,0,2,4
可以看出这组数字的大小范围是0到5。
那个申请一个数组的大小就为6。
下标为0的位置存储0出现了次数,以此类推。
这个数组称为A数组。
那么这个计数数组的存储就是:
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
2 | 0 | 2 | 1 | 1 | 1 |
这个称为C数组
做一个累加,就变成了
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
2 | 2 | 4 | 5 | 6 | 7 |
小于等于0的数有2个,小于等于1的数2个,小于等于2的数有4个,以此类推。
申请一个临时数组R和临时数组长度相同。
A数组从后往前扫描。最后一个是4,找到数组C下标4,发现小于等于4的数字有6个,那么将4放在R数组的下标(6-1=5)位置。并且将6减去1。
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
4 |
倒数第二个数是2,找到数组C下标2, 发现小于等于2的数字有4个,那么将2放在R数组的下标(4-1=3)位置,并且将3减去1。
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
2 | 4 |
倒数第3个数是0,找到数组C下标0, 发现小于等于0的数字有2个,那么将2放在R数组的下标(2-1=1)位置,并且将2减去1。
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
0 | 2 | 4 |
倒数第4个数是5,找到数组C下标5, 发现小于等于5的数字有7个,那么将2放在R数组的下标(7-1=6)位置,并且将6减去1。
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
0 | 2 | 4 | 5 |
以此类推,就能把数字放好在R数组了。然后再将R数组拷贝回A数组。