遞回版
fn main() {
let mut a = [8, 7, 6, 5, 4, 3, 2, 1, 0];
mergesort(&mut a);
println!("{:?}", a);
}
use std::cmp::Ordering;
fn mergesort(array: &mut [u32]) {
let mid = array.len() / 2;
if mid == 0 {
return; //base case: array.len() == 1
}
mergesort(&mut array[..mid]);
mergesort(&mut array[mid..]);
merge(array, mid);
}
fn merge(array: &mut [u32], mid: usize) {
let mut new_array = vec![]; //use vec to keep sorted value
let mut j = 0;
let mut k = mid;
for i in 0..array.len() {
if k == array.len() || j == mid {
//if left or right are all selected
break;
}
if array[j] < array[k] {
new_array.push(array[j]);
j += 1;
} else {
new_array.push(array[k]);
k += 1;
}
}
match (j.cmp(&mid), k.cmp(&array.len())) {
(Ordering::Equal, Ordering::Equal) => (),
(Ordering::Less, Ordering::Equal) => {
for i in j..mid {
new_array.push(array[i]);
}
}
(Ordering::Equal, Ordering::Less) => {
for i in k..array.len() {
new_array.push(array[i]);
}
}
_ => (),
}
for i in 0..array.len() {
array[i] = new_array[i];
}
}
迭代佇列版
自底向上的歸并排序可以輕松的轉換為遞回表示，在由待排序的陣列構成的佇列中，不斷取出前兩個元素，合并成一個元組，放入佇列后端，直至佇列長度為1
以下是我齪劣的代碼，，，實作思路是使用std的deque，其元素仍為deque，不斷合并隊首的兩個佇列
use std::collections::VecDeque;
fn main() {
let mut array = [3, 7, 1, 8, 3, 6, 2, 8, 4, 0];
iterative_merge_sort(&mut array);
println!("{:?}", array);
}
fn iterative_merge_sort(array: &mut [u32]) {
if array.len() == 0 || array.len() == 1 {
return;
}
let mut deque = VecDeque::new();
for i in 0..array.len() {
//建立初始佇列 ，元素為只有單個元素的佇列
deque.push_back(VecDeque::from(vec![array[i]]));
}
while deque.len() > 1 {
let left = &mut deque.pop_front().unwrap();
let right = &mut deque.pop_front().unwrap(); //當佇列長度大于1時，merge隊首兩個元素合并并置入隊尾
deque.push_back(merge(left, right));
}
for i in 0..array.len() {
array[i] = deque[0][i];
}
至于merge函式則試著使用遞回（參考演算法概論的）偽代碼：
function merge(x[0..k], y[0..l])
if k = 0 return y[0..l]
if l = 0 return x[0..k]
if x[0] <= y[0]
return x[0] + merge(x[1..k], y[0..l])
else
return y[0] + merge(x[0..k], y[1..l])
＋號代表著連接操作
自己實作的merge:
fn merge(left: &mut VecDeque<u32>, right: &mut VecDeque<u32>) -> VecDeque<u32> {
if left.len() == 0 {
return right.clone();
}
if right.len() == 0 {
return left.clone();
}
if left[0] < right[0] {
//遞回合并
let value = https://www.cnblogs.com/opadc/p/left.pop_front().unwrap();
let mut deq = merge(left, right);
deq.push_front(value);
deq
} else {
let value = right.pop_front().unwrap();
let mut deq = merge(left, right);
deq.push_front(value);
deq
}
}
代碼風格詭異，比較是菜鳥，以后學點再改吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/652.html
標籤：其他