| 1 | // radix_sort.rs |
| 2 | |
| 3 | fn radix_sort(nums: &mut [usize]) { |
| 4 | if nums.len() < 2 { return; } |
| 5 | |
| 6 | // 找到最大的数，它的位最多 |
| 7 | let max_num = match nums.iter().max() { |
| 8 | Some(&x) => x, |
| 9 | None => return, |
| 10 | }; |
| 11 | |
| 12 | // 找最接近且 >= nums 长度的 2 的次幂值作为桶大小，如: |
| 13 | // 最接近且 >= 10 的 2 的次幂值是 2^4 = 16 |
| 14 | // 最接近且 >= 17 的 2 的次幂值是 2^5 = 32 |
| 15 | let radix = nums.len().next_power_of_two(); |
| 16 | |
| 17 | // digit 代表小于某个位对应桶的所有数 |
| 18 | // 个、十、百、千分别在 1、2、3、4 位 |
| 19 | // 起始从个位开始，所以是 1 |
| 20 | let mut digit = 1; |
| 21 | while digit <= max_num { |
| 22 | // 闭包函数：计算数据在桶中的位置 |
| 23 | let index_of = |x| x / digit % radix; |
| 24 | |
| 25 | // 计数器 |
| 26 | let mut counter = vec![0; radix]; |
| 27 | for &x in nums.iter() { |
| 28 | counter[index_of(x)] += 1; |
| 29 | } |
| 30 | for i in 1..radix { |
| 31 | counter[i] += counter[i-1]; |
| 32 | } |
| 33 | |
| 34 | // 排序 |
| 35 | for &x in nums.to_owned().iter().rev() { |
| 36 | counter[index_of(x)] -= 1; |
| 37 | nums[counter[index_of(x)]] = x; |
| 38 | } |
| 39 | |
| 40 | // 跨越桶 |
| 41 | digit *= radix; |
| 42 | } |
| 43 | } |
| 44 | |
| 45 | fn main() { |
| 46 | let mut nums = [54,32,99,18,75,31,43,56,21,22]; |