lib_algorithms/
sort.rs

1// Сортировка
2
3/// Полиморфная быстрая сортирока (QuickSort)
4pub fn qsort<T>(v: &mut Vec<T>)
5where
6    T: Ord + Copy,
7{
8    if v.len() < 2 {
9        return;
10    }
11    let mut vmin = &mut Vec::new();
12    let mut vmax = &mut Vec::new();
13    for i in &v[1..] {
14        if *i > v[0] {
15            vmax.push(*i)
16        } else {
17            vmin.push(*i)
18        }
19    }
20    qsort(&mut vmin);
21    qsort(&mut vmax);
22    vmin.push(v[0]);
23    vmin.extend(vmax.clone());
24    for (num, i) in vmin.iter().enumerate() {
25        v[num] = *i
26    }
27}
28
29/// Полиморфная сортировка Шелла
30pub fn ssort<T>(v: &mut Vec<T>)
31where
32    T: Ord + Copy,
33{
34    let len = v.len();
35    if len < 2 {
36        return;
37    }
38    let mut h = 1;
39    while h < len / 3 {
40        h = h * 3 + 1
41    }
42    while h > 0 {
43        for i in h..len {
44            let x = v[i];
45            let mut j = i;
46            while j > h - 1 && v[j - h] > x {
47                v[j] = v[j - h];
48                j -= h
49            }
50            v[j] = x
51        }
52        h = (h - 1) / 3
53    }
54}
lib_algorithms/sort.rs

lib_algorithms/
sort.rs
