計數排序 Rust實現
計數排序
計數排序假設n
個輸入元素都是0
到k
區間的一個整數(k
為某整數)
當k
為O(n)
時,排序的時間為O(n)
計數排序基本思想是:對於每個輸入元素x
, 確定小於x
的元素個數
先新建一個可變陣列c, 初始化為0
let mut c: Vec<usize> = Vec::with_capacity(k); for i in 0..k+1 { c.push(0); }
c記錄a中每個元素出現的個數
for i in 0..a.len() { c[a[i]] = c[a[i]] + 1; }
然後計算對於i
從0..k
, 有多少個元素是小於等於i
for i in 1..k+1 { c[i] = c[i] + c[i-1]; }
最後把元素a[i]放入陣列b的正確位置上
for i in (0..a.len()).rev() { b[c[a[i]]-1] = a[i]; c[a[i]] = c[a[i]] - 1; }
-
計數排序的時間代價為
O(k+n)
, 當k=O(n)
時, 一般會採用計數排序 - 該排序不是比較排序, 而是根據元素的值來確定元素的位置
- 計數排序是穩定的
全部程式碼如下:
fn count_sort(a: &mut [usize], b: &mut [usize], k: usize) { let mut c: Vec<usize> = Vec::with_capacity(k+1); for _ in 0..k+1 { c.push(0); } for i in 0..a.len() { c[a[i]] = c[a[i]] + 1; } for i in 1..k+1 { c[i] = c[i] + c[i-1]; } for i in (0..a.len()).rev() { b[c[a[i]]-1] = a[i]; c[a[i]] = c[a[i]] - 1; } } fn main() { let mut a: [usize; 8] = [2,5,3,0,2,3,0,3]; let mut b = [0usize; 8]; count_sort(&mut a, &mut b, 5); println!("{:?}", b); }