Rust排序算法：选择排序、冒泡排序、插入排序、归并排序 _算法

文章插图

选择排序

pub fn selection_sort<T:Ord>(arr:&mut [T]) {let len = arr.len();for left in 0..len {let mut smallest = left;for right in (left+1)..len {if arr[right] < arr[smallest] {smallest = right;}}arr.swap(smallest, left);}}#[cfg(test)]mod tests {use super::*;#[test]fn basic() {let mut res = vec!["f","d","e","a","c","b"];selection_sort(&mut res);assert_eq!(res, vec!["a","b","c","d","e","f"]);}#[test]fn empty() {let mut res = Vec::<u8>::new();selection_sort(&mut res);assert_eq!(res, vec![]);}#[test]fn one_element() {let mut res = vec!["a"];selection_sort(&mut res);assert_eq!(res, vec!["a"]);}#[test]fn pre_sorted() {let mut res = vec!["a","b","c","d"];selection_sort(&mut res);assert_eq!(res, vec!["a","b","c","d"]);}}

冒泡排序

pub fn bubble_sort<T:Ord>(arr:&mut [T]) {if arr.is_empty() {return;}let mut sorted = false;let mut n = arr.len();while!sorted {sorted = true;for i in 0..n-1{if arr[i] > arr[i+1] {arr.swap(i,i+1);sorted = false;}}n -= 1;}}#[cfg(test)]mod tests {use super::super::is_sorted;use super::*;#[test]fn descending() {let mut vec1 = vec![6,5,4,3,2,1];bubble_sort(&mut vec1);assert!(is_sorted(&vec1))}#[test]fn ascending() {let mut vec2 = vec![1,2,3,4,5];bubble_sort(&mut vec2);assert!(is_sorted(&vec2))}#[test]fn empty() {let mut vec3:Vec<usize> = vec![];bubble_sort(&mut vec3);assert!(is_sorted(&vec3))}}

插入排序

pub fn insertion_sort<T>(arr:&mut [T])whereT: PartialOrd+Copy{for i in 1..arr.len() {let cur = arr[i];let mut j = i - 1;while arr[j] > cur {arr[j+1] = arr[j];if j == 0 {break;}j -= 1;}// exit the loop from that break statementif j == 0 && arr[0] > cur {arr[0] = cur;}else {// `arr[j]>cur` is not satisfied ,exit from condition judgementarr[j+1] =cur;}}}#[cfg(test)]mod tests {use super::super::is_sorted;use super::*;#[test]fn empty() {let mut arr:[u8;0] = [];insertion_sort(&mut arr);assert!(is_sorted(&arr));}#[test]fn one_element() {let mut arr:[char;1] = ['a'];insertion_sort(&mut arr);assert!(is_sorted(&arr));}#[test]fn already_sorted() {let mut arr:[&str;3] = ["a","b","c"];insertion_sort(&mut arr);assert!(is_sorted(&arr));}#[test]fn basic() {let mut arr:[&str;4] = ["d","a","c","b"];insertion_sort(&mut arr);assert!(is_sorted(&arr));}#[test]fn repeated_elements() {let mut arr: Vec<usize> = vec![542,542,542,542];insertion_sort(&mut arr);assert!(is_sorted(&arr));}}

归并排序

fn merge<T:Ord+Copy>(arr:&mut [T],mid:usize) {// Create temporary vectors to support the mergelet left_half = arr[..mid].to_vec();let right_half = arr[mid..].to_vec();let mut l:usize = 0;let mut r:usize = 0;for v in arr {if r == right_half.len() || (l < left_half.len() && left_half[l] < right_half[r]) {*v = left_half[l];l += 1;}else {*v = right_half[r];r += 1;}}}pub fn top_down_merge_sort<T: Ord+Copy>(arr:&mut [T]) {if arr.len() > 1 {let mid:usize = arr.len() / 2;// Sort the left half recursivelytop_down_merge_sort(&mut arr[..mid]);// Sort the right half recursivelytop_down_merge_sort(&mut arr[mid..]);// Combine the two halvesmerge(arr,mid)}}#[cfg(test)]mod tests {#[cfg(test)]mod top_down_merge_sort {use super::super::*;#[test]fn basic() {let mut res = vec![10,3,8,2,7,6,1,4,5,9];top_down_merge_sort(&mut res);assert_eq!(res, vec![1,2,3,4,5,6,7,8,9,10])}#[test]fn basic_string() {let mut res = vec!["a","bb","d","cc"];top_down_merge_sort(&mut res);assert_eq!(res,vec!("a","bb","cc","d"))}#[test]fn empty() {let mut res = Vec::<u8>::new();top_down_merge_sort(&mut res);assert_eq!(res, vec![])}#[test]fn one_element() {let mut res = vec![1];top_down_merge_sort(&mut res);assert_eq!(res, vec![1])}#[test]fn pre_sorted() {let mut res = vec![1,2,3,4,5,6,7];top_down_merge_sort(&mut res);assert_eq!(res, vec![1,2,3,4,5,6,7])}}}

【Rust排序算法：选择排序、冒泡排序、插入排序、归并排序】