选择排序

选择排序是一种使用选择排序的算法。
最坏、中等和最好情况复杂度： O(n²)
https://en.wikipedia.org/wiki/Selection_sort

extern crate sort_algorithms;

use sort_algorithms::selection_sort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    selection_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

冒泡排序

冒泡排序是一种使用比较值的排序算法。
最坏和中等情况复杂度： O(n²)
最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Bubble_sort

extern crate sort_algorithms;

use sort_algorithms::bubble_sort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    bubble_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

快速排序

快速排序是一种使用分治策略的算法。
最坏情况复杂度： O(n²)
中等情况复杂度： O(n)
最好情况复杂度： O(n log n)
https://en.wikipedia.org/wiki/Quicksort

extern crate sort_algorithms;

use sort_algorithms::quick_sort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    quick_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

堆排序

堆排序是一种使用选择排序策略的通用算法。
最坏情况复杂度： O(n log n)
中等情况复杂度： O(n log n)
最好情况复杂度： O(n log n)
https://en.wikipedia.org/wiki/Heapsort

extern crate sort_algorithms;

use sort_algorithms::heapsort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    heapsort(&mut arr);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

归并排序

归并排序是一种使用比较和分治策略的算法。
最坏情况复杂度： O(n log n)
中等情况复杂度： O(n log n)
最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Merge_sort

extern crate sort_algorithms;

use sort_algorithms::merge_sort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    merge_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

基数排序

基数排序是一种使用非比较策略的算法。
最坏情况复杂度： O(n)
中等情况复杂度： O(n)
最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Radix_sort

只能用于排序正整数列表作为键

extern crate sort_algorithms;

use sort_algorithms::radix_sort;

fn main() {
    let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    radix_sort(&mut arr, |&a| a);
    println!("{:?}", &arr);
    assert_eq!(arr, [ 0, 1, 2, 3, 4, 5, 6, 7]);
}

插入排序

插入排序是一种使用策略，即捕获一个元素并将其与其他元素进行比较。
最坏和中等情况复杂度： O(n²)
最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Insertion_sort

extern crate sort_algorithms;

use sort_algorithms::insertion_sort;

fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    insertion_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

鸡尾酒搅拌排序

鸡尾酒搅拌排序是冒泡排序的一种变体。
最坏和中等情况复杂度： O(n²)
最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Cocktail_shaker_sort

extern crate sort_algorithms;

use sort_algorithms::cocktail_shaker_sort;


fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    cocktail_shaker_sort(&mut arr, |a, b| a < b);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}

重力排序/珠排序

重力排序是一种使用自然排序策略的算法。
最坏、中等和最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Bead_sort

只能用于排序正整数列表作为键

extern crate sort_algorithms;

use sort_algorithms::gravity_sort;


fn main() {
    let mut arr = vec![9, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    gravity_sort(&mut arr, |&a| a);
    println!("{:?}", &arr);
    assert_eq!(arr, [ 0, 1, 2, 3, 4, 5, 6, 9]);
}

计数排序

计数排序是一种使用键值作为数组索引的排序策略的算法，并且比较排序的下界 Ω(n log n) 不会适用。
最坏、中等和最好情况复杂度： O(n)
https://en.wikipedia.org/wiki/Counting_sort

只能用于排序正整数列表作为键

extern crate sort_algorithms;

use sort_algorithms::counting_sort;

fn main() {
    let mut arr = vec![7, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    counting_sort(&mut arr, |&a| a);
    println!("{:?}", &arr);
    assert_eq!(arr, [0, 1, 2, 3, 4, 5, 6, 7]);
}

闪光排序

闪光排序是一种可以使用元素的值直接计算最终位置的算法，无需比较。
最坏、中等和最好情况复杂度： O(n) http://www.neubert.net/Flapaper/9802n.htm

extern crate sort_algorithms;

use sort_algorithms::flash_sort;
fn main() {
    let mut arr = vec![-1, 6, 5, 2, 4, 3, 1, 0];
    println!("{:?}", &arr);
    flash_sort(&mut arr, |&a| a);
    println!("{:?}", &arr);
    assert_eq!(arr, [-1, 0, 1, 2, 3, 4, 5, 6]);
}