algorithms_fourth/
lib.rs

1//! 《算法 第四版》书中大部分算法的rust实现  
2
3pub mod search;
4pub mod sort;
5pub use sort::*;
6pub mod digraph;
7pub mod graph;
8pub use digraph::bellman_for_sp;
9pub use search::boyer_moore;
10pub use search::kmp;
11pub use search::rabin_karp;
12pub use search::red_black_search;
13pub use string::nfa;
14pub mod io;
15pub mod string;
16#[macro_export]
17macro_rules! fill_vec_with {
18    // $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
19    ($vec:expr,$x:expr, $count:expr) => {
20        for _ in 0..$count {
21            $vec.push($x);
22        }
23    };
24}
25/// 生成Vec，用特定数目的默认值填充
26#[macro_export]
27macro_rules! generate_vec_with {
28    ($x:expr, $count:expr) => {{
29        let mut vec = Vec::with_capacity($count);
30        $crate::fill_vec_with!(vec, $x, $count);
31        vec
32    }};
33}
34#[cfg(test)]
35mod tests {
36    // use super::*;
37    use rand::{self, seq::SliceRandom};
38
39    use crate::sort;
40    #[test]
41    fn heap_sort() {
42        let mut data = set_up();
43        // data = vec![4, 2, 1, 3];
44        sort::heap_sort(&mut data);
45        // println!("{:?}", data);
46        assert!(is_sorted(&data), "merge sort failed");
47        // assert!([1,2].is_sorted());
48    }
49    #[test]
50    fn merge_sort() {
51        let mut data = set_up();
52        // data = vec![4,2,1];
53        sort::merge_sort(&mut data);
54        // println!("{:?}", data);
55        assert!(is_sorted(&data), "merge sort failed");
56        // assert!([1,2].is_sorted());
57    }
58    #[test]
59    fn quick_sort_for_three_direction() {
60        let mut data = set_up();
61        // data = vec![4,2,1];
62        let len = data.len() - 1;
63        sort::quick_sort_for_three_direction(&mut data, 0, len);
64        // println!("{:?}", data);
65        assert!(is_sorted(&data), "quick sort failed");
66        // assert!([1,2].is_sorted());
67    }
68    #[test]
69    fn quick_sort() {
70        let mut data = set_up();
71        // data = vec![4,2,1];
72        let len = data.len() - 1;
73        sort::quick_sort(&mut data, 0, len);
74        // println!("{:?}", data);
75        assert!(is_sorted(&data), "quick sort failed");
76        // assert!([1,2].is_sorted());
77    }
78    #[test]
79    fn shell_sort() {
80        let mut data = set_up();
81        sort::shell_sort(&mut data);
82        // println!("{:?}",data);
83        assert!(is_sorted(&data), "shell sort failed");
84        // assert!([1,2].is_sorted());
85    }
86    #[test]
87    fn insert_sort() {
88        let mut data = set_up();
89        sort::insert_sort(&mut data);
90        // println!("{:?}",data);
91        assert!(is_sorted(&data), "insert sort failed");
92        // assert!([1,2].is_sorted());
93    }
94    #[test]
95    fn bubble_sort() {
96        let mut data = set_up();
97        sort::bubble_sort(&mut data);
98        // println!("{:?}",data);
99        assert!(is_sorted(&data), "bubble sort failed");
100        // assert!([1,2].is_sorted());
101    }
102
103    fn set_up() -> Vec<i32> {
104        let mut data: Vec<i32> = (1..10000).collect();
105        let mut rng = rand::thread_rng();
106        data.shuffle(&mut rng);
107        // data.reverse();
108        data
109    }
110    fn is_sorted(data: &[i32]) -> bool {
111        let mut ans = true;
112        let sential = data.len() - 1;
113        for i in 0..sential {
114            // print!("{} ",i);
115            if data[i + 1] < data[i] {
116                ans = false;
117                break;
118            }
119        }
120        ans
121    }
122}
algorithms_fourth/lib.rs

algorithms_fourth/
lib.rs
