algorithms_rs/sort/
select_sort.rs

1use super::Sort;
2
3/// select sort
4#[derive(Debug)]
5pub struct SelectSort<T> {
6    arr: Vec<T>,
7}
8
9impl<T> From<Vec<T>> for SelectSort<T> {
10    fn from(arr: Vec<T>) -> Self {
11        Self { arr }
12    }
13}
14
15impl<T: core::clone::Clone> From<&[T]> for SelectSort<T> {
16    fn from(arr: &[T]) -> Self {
17        Self { arr: arr.into() }
18    }
19}
20
21impl<T> SelectSort<T> {
22    pub fn select_sort<F>(&mut self, f: F)
23    where
24        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
25    {
26        for i in 0..self.arr.len() {
27            // 将a[i]和a[i+1..len]最小的元素交换
28            let mut min = i; // 最小元素的索引
29            for j in (i + 1)..self.arr.len() {
30                if f(&self.arr[j], &self.arr[min]) {
31                    min = j;
32                }
33            }
34            self.arr.swap(i, min);
35        }
36    }
37
38    pub fn select_sort_by_find_smallest<F>(&mut self, f: F) -> Vec<T>
39    where
40        F: FnOnce(Option<&T>, Option<&T>) -> bool + core::marker::Copy,
41    {
42        let mut result = vec![];
43        for _ in 0..self.arr.len() {
44            let smallest = self.find_smallest(f);
45            result.push(self.arr.swap_remove(smallest));
46        }
47        result
48    }
49
50    pub fn find_smallest<F>(&self, f: F) -> usize
51    where
52        F: FnOnce(Option<&T>, Option<&T>) -> bool + core::marker::Copy,
53    {
54        let mut smallest = self.arr.get(0);
55        let mut smallest_index = 0usize;
56        for i in 1..self.arr.len() {
57            if f(self.arr.get(i), smallest) {
58                smallest = self.arr.get(i);
59                smallest_index = i;
60            }
61        }
62        smallest_index
63    }
64}
65
66impl<T: core::cmp::PartialOrd + Clone> Sort<T> for SelectSort<T> {
67    fn inner(&self) -> Vec<T> {
68        self.arr.clone()
69    }
70
71    fn sort_by<F>(&mut self, f: F)
72    where
73        F: FnOnce(&T, &T) -> bool + core::marker::Copy,
74    {
75        self.select_sort(f)
76    }
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_select_sort_ok() {
85        let mut select = SelectSort::from(vec![10, 9, 8, 6, 5, 4, 3, 2, 1]);
86        select.sort();
87        assert!(select.is_sort());
88    }
89
90    #[test]
91    fn test_select_sort_a_empty_arr() {
92        let mut select = SelectSort::from(Vec::<i32>::new());
93        select.sort();
94        assert!(select.is_sort());
95    }
96
97    #[test]
98    fn test_select_sort_by_find_smallest() {
99        let mut select = SelectSort::from(vec![10, 9, 8, 6, 5, 4, 3, 2, 1]);
100        let result = select.select_sort_by_find_smallest(|v1, v2| v1 < v2);
101        assert_eq!(result, vec![1, 2, 3, 4, 5, 6, 8, 9, 10]);
102    }
103}
algorithms_rs/sort/select_sort.rs

algorithms_rs/sort/
select_sort.rs
