1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

//! 《算法 第四版》书中大部分算法的rust实现  

pub mod search;
pub mod sort;
pub use sort::*;
pub mod digraph;
pub mod graph;
pub use digraph::bellman_for_sp;
pub use search::boyer_moore;
pub use search::kmp;
pub use search::rabin_karp;
pub use search::red_black_search;
pub use string::nfa;

#[macro_export]
macro_rules! fill_vec_with {
    // $(...),+ 包围起来，就可以匹配一个或多个用逗号隔开的表达式
    ($vec:expr,$x:expr, $count:expr) => {
        for _ in 0..$count {
            $vec.push($x);
        }
    };
}
/// 生成Vec，用特定数目的默认值填充
#[macro_export]
macro_rules! generate_vec_with {
    ($x:expr, $count:expr) => {{
        let mut vec = Vec::with_capacity($count);
        $crate::fill_vec_with!(vec, $x, $count);
        vec
    }};
}
#[cfg(test)]
mod tests {
    // use super::*;
    use rand::{self, seq::SliceRandom};

    use crate::sort;
    #[test]
    fn heap_sort() {
        let mut data = set_up();
        // data = vec![4, 2, 1, 3];
        sort::heap_sort(&mut data);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "merge sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn merge_sort() {
        let mut data = set_up();
        // data = vec![4,2,1];
        sort::merge_sort(&mut data);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "merge sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn quick_sort_for_three_direction() {
        let mut data = set_up();
        // data = vec![4,2,1];
        let len = data.len() - 1;
        sort::quick_sort_for_three_direction(&mut data, 0, len);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "quick sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn quick_sort() {
        let mut data = set_up();
        // data = vec![4,2,1];
        let len = data.len() - 1;
        sort::quick_sort(&mut data, 0, len);
        // println!("{:?}", data);
        assert!(is_sorted(&data), "quick sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn shell_sort() {
        let mut data = set_up();
        sort::shell_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "shell sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn insert_sort() {
        let mut data = set_up();
        sort::insert_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "insert sort failed");
        // assert!([1,2].is_sorted());
    }
    #[test]
    fn bubble_sort() {
        let mut data = set_up();
        sort::bubble_sort(&mut data);
        // println!("{:?}",data);
        assert!(is_sorted(&data), "bubble sort failed");
        // assert!([1,2].is_sorted());
    }

    fn set_up() -> Vec<i32> {
        let mut data: Vec<i32> = (1..10000).collect();
        let mut rng = rand::thread_rng();
        data.shuffle(&mut rng);
        // data.reverse();
        data
    }
    fn is_sorted(data: &[i32]) -> bool {
        let mut ans = true;
        let sential = data.len() - 1;
        for i in 0..sential {
            // print!("{} ",i);
            if data[i + 1] < data[i] {
                ans = false;
                break;
            }
        }
        ans
    }
}