选择排序

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])
where
    T: 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 statement
        if j == 0 && arr[0] > cur {
            arr[0] = cur;
        }else {
            // `arr[j]>cur` is not satisfied ,exit from condition judgement
            arr[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 merge
    let 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 recursively
        top_down_merge_sort(&mut arr[..mid]);
        // Sort the right half recursively
        top_down_merge_sort(&mut arr[mid..]);
        // Combine the two halves
        merge(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])
        }
    }
}