algorithms_fourth/
sort.rs

1//!  第二章：排序算法
2
3use std::fmt::{Debug, Display};
4pub mod priority_queue;
5const DEBUG: bool = false;
6pub fn heap_sort<T>(data: &mut [T])
7where
8    T: PartialOrd + Clone + Copy + Debug,
9{
10    let mut aux = Vec::with_capacity(data.len() + 1);
11    let count = data.len();
12    aux.push(data[0]);
13    for item in data.iter().take(count) {
14        aux.push(*item);
15    }
16    let n = count / 2;
17    for n in (1..=n).rev() {
18        sink(&mut aux, n, count);
19    }
20    if DEBUG {
21        println!("heap:{:?}", aux);
22    }
23    for n in (2..=count).rev() {
24        aux.swap(n, 1);
25        sink(&mut aux, 1, n - 1);
26    }
27    data[..count].copy_from_slice(&aux[1..(count + 1)]);
28}
29fn sink<T: PartialOrd>(data: &mut [T], k: usize, len: usize) {
30    let mut i = k;
31    while i <= len / 2 {
32        let mut j = i * 2;
33        if j < len && data[j] < data[j + 1] {
34            j += 1;
35        };
36        if data[i] < data[j] {
37            data.swap(j, i);
38            i = j;
39        } else {
40            break;
41        }
42    }
43}
44/// 归并排序
45pub fn merge_sort<T: PartialOrd + Clone + Copy + Debug>(data: &mut [T]) {
46    let len = data.len();
47    let mut aux: Vec<T> = Vec::with_capacity(len);
48    let mut s = 1;
49    for item in data.iter().take(len) {
50        aux.push(*item);
51    }
52    let mut is_orgin = true;
53    while s < len {
54        let mut i = 0;
55        is_orgin = !is_orgin;
56        while i < len {
57            if is_orgin {
58                merge(data, &aux, i, i + s - 1, len.min(i + s + s) - 1);
59            } else {
60                merge(&mut aux, data, i, i + s - 1, len.min(i + s + s) - 1);
61            }
62            i += s + s;
63        }
64        if DEBUG {
65            println!("{:?}", data);
66        }
67        s += s;
68    }
69    if !is_orgin {
70        data[..len].copy_from_slice(&aux[..len]);
71    }
72}
73
74fn merge<T: PartialOrd + Clone + Copy + Debug>(
75    data: &mut [T],
76    aux: &[T],
77    lo: usize,
78    m: usize,
79    hi: usize,
80) {
81    if DEBUG {
82        println!("{},{},{}", lo, m, hi);
83    }
84    if lo >= hi {
85        return;
86    }
87    let mut i = lo;
88    let mut j = m + 1;
89    for item in data.iter_mut().take(hi + 1).skip(lo) {
90        if j > hi {
91            *item = aux[i];
92            i += 1;
93        } else if i > m || aux[j] < aux[i] {
94            *item = aux[j];
95            j += 1;
96        } else {
97            *item = aux[i];
98            i += 1;
99        }
100    }
101}
102/// 冒泡排序
103pub fn bubble_sort(data: &mut [i32]) {
104    let mut i = 0;
105    while i < data.len() {
106        let mut j = i + 1;
107        let mut v = data[i];
108        let mut pos = i;
109        while j < data.len() {
110            if data[j] < v {
111                pos = j;
112                v = data[j];
113            }
114            j += 1;
115        }
116        data.swap(i, pos);
117        i += 1;
118    }
119}
120
121/// 插入排序（效率竟然不如冒泡排序）
122pub fn insert_sort<T>(data: &mut [T])where T :PartialOrd {
123    let mut count = 0;
124    for i in 1..data.len() {
125        for j in (1..=i).rev() {
126            if data[j] < data[j - 1] {
127                data.swap(j, j - 1);
128                count += 1;
129            } else {
130                break;
131            }
132        }
133    }
134    println!("count:{}", count);
135}
136/// 三向快速排序，这里没有随机话，所以为了效率，使用者需要自己随机化数据
137pub fn quick_sort_for_three_direction<T>(data: &mut [T], lo: usize, hi: usize)
138where
139    T: PartialOrd + Clone + Copy + Debug + Display,
140{
141    if lo >= hi {
142        return;
143    }
144    let mut i = lo + 1;
145    let mut gt = hi;
146    let mut le = lo;
147    let v = data[lo];
148    while i <= gt {
149        if data[i] == v {
150            i += 1;
151        } else if data[i] < v {
152            data.swap(le, i);
153            le += 1;
154            i += 1;
155        } else {
156            data.swap(i, gt);
157            gt -= 1;
158        }
159    }
160    if le > lo {
161        quick_sort_for_three_direction(data, lo, le - 1);
162    }
163    quick_sort_for_three_direction(data, i, hi);
164}
165/// 快速排序，这里没有随机话，所以为了效率，使用者需要自己随机化数据
166pub fn quick_sort<T>(data: &mut [T], lo: usize, hi: usize)
167where
168    T: PartialOrd + Clone + Copy + Debug + Display,
169{
170    if lo >= hi {
171        return;
172    }
173    if DEBUG {
174        println!("lo:{},hi:{}", lo, hi);
175    }
176    let mut i = lo + 1;
177    let mut j = hi;
178    let v: T = data[lo];
179    loop {
180        loop {
181            if i < hi && data[i] < v {
182                i += 1;
183            } else {
184                break;
185            }
186        }
187        loop {
188            if j > lo && data[j] > v {
189                j -= 1;
190            } else {
191                break;
192            }
193        }
194        if i >= j {
195            break;
196        }
197        if DEBUG {
198            println!("swap:{},{}", data[i], data[j]);
199            println!("swap id:{},{}", i, j);
200        }
201        data.swap(i, j);
202        i += 1;
203        j -= 1;
204    }
205    if DEBUG {
206        println!("swap out:{},{}", data[lo], data[j]);
207    }
208    data.swap(lo, j);
209    if j > 0 {
210        quick_sort(data, lo, j - 1);
211    }
212    quick_sort(data, j + 1, hi);
213}
214
215/// 希尔排序（交换次数比插入排序少，但远未达到高效）
216pub fn shell_sort(data: &mut [i32]) {
217    let mut h = 1;
218    while h < data.len() / 3 {
219        h = h * 3 + 1;
220    }
221    if DEBUG {
222        println!("h:{}", h);
223    }
224    let mut count = 0;
225    let mut s = h;
226    while s >= 1 {
227        if DEBUG {
228            println!("s:{}", s);
229        }
230        for i in RangeStep::new(s, data.len(), s) {
231            for j in RangeStep::new(i, s - 1, s) {
232                if data[j] < data[j - s] {
233                    data.swap(j, j - s);
234                    count += 1;
235                } else {
236                    break;
237                }
238            }
239        }
240        s /= 3;
241    }
242    if DEBUG {
243        println!("count:{}", count);
244    }
245}
246
247/// 用于指定步长的迭代usize元素
248///
249/// 从0开始，元素间相差2，不包含4
250/// ```
251/// use algorithms_fourth::sort::*;
252/// let range = RangeStep::new(0,4,2);
253/// ```
254///
255/// 从4开始，元素间相差2，不包含0
256/// ```
257/// use algorithms_fourth::sort::*;
258/// let range = RangeStep::new(4,0,2);
259/// ```
260pub struct RangeStep<T> {
261    start: T,
262    end: T,
263    step: T,
264    forward: bool,
265}
266impl RangeStep<usize> {
267    pub fn new(start: usize, end: usize, step: usize) -> RangeStep<usize> {
268        let forward = start < end;
269        if step == 0 {
270            panic!("no range: {},{},{}", start, end, step)
271        }
272        RangeStep {
273            start,
274            end,
275            step,
276            forward,
277        }
278    }
279}
280impl Iterator for RangeStep<usize> {
281    type Item = usize;
282
283    fn next(&mut self) -> Option<Self::Item> {
284        let ans = self.start;
285        if self.forward && ans >= self.end || !self.forward && ans <= self.end {
286            return None;
287        }
288        if self.forward {
289            self.start += self.step;
290        } else {
291            self.start -= self.step;
292        }
293        Some(ans)
294    }
295}
algorithms_fourth/sort.rs

algorithms_fourth/
sort.rs
