插入排序

fn insert<T: Ord + Copy>(a: &mut [T]) {
    for i in 1..a.len() {
        let tmp = a[i];
        let mut j = i;
        while j > 0 && tmp < a[j - 1] {
            a[j] = a[j - 1];
            j -= 1;
        }
        a[j] = tmp;
    }
}

希尔排序

fn shell<T: Ord + Copy>(a: &mut [T]) {
    let n = a.len();
    let mut h = 1;
    while h < n / 3 {
        h = h * 3 + 1;
    }
    while h >= 1 {
        for i in h..n {
            let tmp = a[i];
            let mut j = i;

            while tmp < a[j - h] {
                a[j] = a[j - h];
                j -= h;
                if let None = j.checked_sub(h) {
                    break;
                }
            }
            a[j] = tmp;
        }
        h /= 3;
    }
}

归并排序

//原地归并
fn merge_help<T: Ord + Copy>(a: &mut [T], lo: usize, mid: usize, hi: usize) {
    if a[mid] <= a[mid + 1] {
        return;
    }
    let mut tmp = a.to_owned();
    //tmp.copy_from_slice(a);
    let mut i = lo;
    let mut j = mid + 1;
    for k in lo..=hi {
        if i > mid {
            a[k] = tmp[j];
            j += 1;
        } else if j > hi {
            a[k] = tmp[i];
            i += 1;
        } else if tmp[j] < tmp[i] {
            a[k] = tmp[j];
            j += 1;
        } else {
            a[k] = tmp[i];
            i += 1;
        }
    }
}

//自顶向下的归并排序
fn merge_sort<T: Ord + Copy>(a: &mut [T], lo: usize, hi: usize) {
    if hi <= lo {
        return;
    }
    //数组较小时用插入排序更快
    if hi - lo < 15 {
        insert(&mut a[lo..=hi])
    }
    let mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);
    merge_help(a, lo, mid, hi);
}

fn merge<T: Ord + Copy>(a: &mut [T]) {
    merge_sort(a, 0, a.len() - 1);
}

//自底向上的归并
fn merge_sort_bu<T: Ord + Copy>(a: &mut [T], lo: usize, hi: usize) {
    let n = a.len();
    let mut sz = 1;
    while sz < n {
        let mut lo = 0;
        while lo < n - sz {
            merge_help(a, lo, lo + sz - 1, std::cmp::min(lo + sz + sz - 1, n - 1));
            lo += 2 * sz;
        }
        sz *= 2;
    }
}

堆排序

#[derive(Debug)]
struct MaxPQ<T: Ord + Copy> {
    pq: Vec<T>,
}

impl<T: Ord + Copy + std::fmt::Debug> MaxPQ<T> {
    fn new(zero: T) -> Self {
        let pq = vec![zero];
        Self { pq }
    }
    fn is_empty(&self) -> bool {
        self.pq.len() <= 1
    }
    fn insert(&mut self, v: T) {
        self.pq.push(v);
        let n = self.pq.len() - 1;
        self.swim(n);
    }
    fn swim(&mut self, mut k: usize) {
        while k > 1 && self.pq[k] > self.pq[k / 2] {
            self.pq.swap(k / 2, k);
            k /= 2;
        }
    }
    fn sink(&mut self, mut k: usize, N: usize) {
        let tmp = self.pq[k];
        while k * 2 <= N {
            let mut j = k * 2;
            if j < N && self.pq[j] < self.pq[j + 1] {
                j += 1;
            }
            if self.pq[k] >= self.pq[j] {
                break;
            }
            self.pq[k] = self.pq[j];
            k = j;
        }
        self.pq[k] = tmp;
    }
    fn sort(a: &mut [T]) -> Vec<T> {
        let mut n = a.len();
        let mut pq = MaxPQ::new(a[0]);
        pq.pq.append(&mut a.to_vec());

        for k in (1..=(n / 2)).rev() {
            MaxPQ::sink(&mut pq, k, n);
        }

        while n > 1 {
            pq.pq.swap(1, n);
            n -= 1;
            MaxPQ::sink(&mut pq, 1, n);
        }
        pq.pq.remove(0);
        pq.pq
    }
}