rust写排序算法

排序算法有内部排序、外部排序；其中内部排序有

• 复杂度为O(n^2)的算法，包括插入排序、冒泡排序；
• 复杂度为O(nlog(n))的算法，包括快速排序
• 复杂度为O(n)的算法，包括桶排序

用rust写个排序算法也是个比较好的训练

冒泡排序

pub fn bubble_sort<T: Ord>(arr: &mut [T]) {
    for i in 0..arr.len() {
        for j in 0..arr.len() - 1 - i {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }

}



#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn descending() {
        //descending
        let mut ve1 = vec![6, 5, 4, 3, 2, 1];
        bubble_sort(&mut ve1);
        for i in 0..ve1.len() - 1 {
            assert!(ve1[i] <= ve1[i + 1]);
        }
    }

    #[test]
    fn ascending() {
        //pre-sorted
        let mut ve2 = vec![1, 2, 3, 4, 5, 6];
        bubble_sort(&mut ve2);
        for i in 0..ve2.len() - 1 {
            assert!(ve2[i] <= ve2[i + 1]);
        }
    }
}

插入排序

use std::cmp;
pub fn insertion_sort<T>(arr: &mut [T])
where
    T: cmp::PartialOrd + Copy,
{
    for i in 1..arr.len() {
        let cur = arr[i];
        let mut j = i - 1;

        while arr[j] > cur {
            arr.swap(j + 1, j);
            if j == 0 {
                break;
            }
            j -= 1;
        }
    }
}

归并排序

fn _merge<T: Ord + Copy>(arr: &mut [T], lo: usize, mid: usize, hi: usize) {
    // create temporary arrays to support merge
    let mut left_half = Vec::new();
    let mut right_half = Vec::new();
    for v in arr.iter().take(mid + 1).skip(lo) {
        left_half.push(*v);
    }
    for v in arr.iter().take(hi + 1).skip(mid + 1) {
        right_half.push(*v);
    }

    let lsize = left_half.len();
    let rsize = right_half.len();

    // pointers to track the positions while merging
    let mut l = 0;
    let mut r = 0;
    let mut a = lo;

    // pick smaller element one by one from either left or right half
    while l < lsize && r < rsize {
        if left_half[l] < right_half[r] {
            arr[a] = left_half[l];
            l += 1;
        } else {
            arr[a] = right_half[r];
            r += 1;
        }
        a += 1;
    }

    // put all the remaining ones
    while l < lsize {
        arr[a] = left_half[l];
        l += 1;
        a += 1;
    }

    while r < rsize {
        arr[a] = right_half[r];
        r += 1;
        a += 1;
    }
}

fn _merge_sort<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) {
    if lo < hi {
        let mid = lo + (hi - lo) / 2;
        _merge_sort(arr, lo, mid);
        _merge_sort(arr, mid + 1, hi);
        _merge(arr, lo, mid, hi);
    }
}

pub fn merge_sort<T: Ord + Copy>(arr: &mut [T]) {
    let len = arr.len();
    if len > 1 {
        _merge_sort(arr, 0, len - 1);
    }
}

快速排序

use std::cmp::PartialOrd;

pub fn partition<T: PartialOrd>(arr: &mut [T], lo: isize, hi: isize) -> isize {
    let pivot = hi as usize;
    let mut i = lo - 1;
    let mut j = hi;

    loop {
        i += 1;
        while arr[i as usize] < arr[pivot] {
            i += 1;
        }
        j -= 1;
        while j >= 0 && arr[j as usize] > arr[pivot] {
            j -= 1;
        }
        if i >= j {
            break;
        } else {
            arr.swap(i as usize, j as usize);
        }
    }
    arr.swap(i as usize, pivot as usize);
    i
}
fn _quick_sort<T: Ord>(arr: &mut [T], lo: isize, hi: isize) {
    if lo < hi {
        let p = partition(arr, lo, hi);
        _quick_sort(arr, lo, p - 1);
        _quick_sort(arr, p + 1, hi);
    }
}
pub fn quick_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    _quick_sort(arr, 0, (len - 1) as isize);
}

rust知识

写这个模块，用到的知识点有Rust的代码组织、单元测试。
Rust的代码组织参见文章https://www.jianshu.com/p/7cd2b0aed2bd，Rust代码组织有

• Package 其中Package管理一个或者多个Crate
• Crate Crate 是 Rust 的最小编译单元，即 Rust 编译器是以 Crate 为最小单元进行编译的。Crate 在一个范围内将相关的功能组合在一起，并最终通过编译生成一个二进制或库文件。
• Module Crate 是 Rust 的最小编译单元，即 Rust 编译器是以 Crate 为最小单元进行编译的。Crate 在一个范围内将相关的功能组合在一起，并最终通过编译生成一个二进制或库文件。

Rust中的代码通过Pub改变可见性，Rust 中模块内部的代码，结构体，函数等类型默认是私有的，但是可以通过 pub 关键字来改变它们的可见性。通过选择性的对外可见来隐藏模块内部的实现细节。pub有三种写法

• pub：成员对模块可见
• pub（self）：成员对模块内的子模块可见
• pub（crate）：成员对整个 crate 可见

单元测试参见 https://blog.csdn.net/u013412391/article/details/110150451，和python，go语言的基础设施一样，rust也有单元测试的基础设施。

小结

rust的语法还是只能孰能生巧，算法写起来和C语言比较接近，但是不用像C语言一样管理内存。