algorithms_fourth 0.1.10

//!  第二章：排序算法

use std::fmt::{Debug, Display};
pub mod priority_queue;
const DEBUG: bool = false;
pub fn heap_sort<T>(data: &mut [T])
where
    T: PartialOrd + Clone + Copy + Debug,
{
    let mut aux = Vec::with_capacity(data.len() + 1);
    let count = data.len();
    aux.push(data[0]);
    for item in data.iter().take(count) {
        aux.push(*item);
    }
    let n = count / 2;
    for n in (1..=n).rev() {
        sink(&mut aux, n, count);
    }
    if DEBUG {
        println!("heap:{:?}", aux);
    }
    for n in (2..=count).rev() {
        aux.swap(n, 1);
        sink(&mut aux, 1, n - 1);
    }
    data[..count].copy_from_slice(&aux[1..(count + 1)]);
}
fn sink<T: PartialOrd>(data: &mut [T], k: usize, len: usize) {
    let mut i = k;
    while i <= len / 2 {
        let mut j = i * 2;
        if j < len && data[j] < data[j + 1] {
            j += 1;
        };
        if data[i] < data[j] {
            data.swap(j, i);
            i = j;
        } else {
            break;
        }
    }
}
/// 归并排序
pub fn merge_sort<T: PartialOrd + Clone + Copy + Debug>(data: &mut [T]) {
    let len = data.len();
    let mut aux: Vec<T> = Vec::with_capacity(len);
    let mut s = 1;
    for item in data.iter().take(len) {
        aux.push(*item);
    }
    let mut is_orgin = true;
    while s < len {
        let mut i = 0;
        is_orgin = !is_orgin;
        while i < len {
            if is_orgin {
                merge(data, &aux, i, i + s - 1, len.min(i + s + s) - 1);
            } else {
                merge(&mut aux, data, i, i + s - 1, len.min(i + s + s) - 1);
            }
            i += s + s;
        }
        if DEBUG {
            println!("{:?}", data);
        }
        s += s;
    }
    if !is_orgin {
        data[..len].copy_from_slice(&aux[..len]);
    }
}

fn merge<T: PartialOrd + Clone + Copy + Debug>(
    data: &mut [T],
    aux: &[T],
    lo: usize,
    m: usize,
    hi: usize,
) {
    if DEBUG {
        println!("{},{},{}", lo, m, hi);
    }
    if lo >= hi {
        return;
    }
    let mut i = lo;
    let mut j = m + 1;
    for item in data.iter_mut().take(hi + 1).skip(lo) {
        if j > hi {
            *item = aux[i];
            i += 1;
        } else if i > m || aux[j] < aux[i] {
            *item = aux[j];
            j += 1;
        } else {
            *item = aux[i];
            i += 1;
        }
    }
}
/// 冒泡排序
pub fn bubble_sort(data: &mut [i32]) {
    let mut i = 0;
    while i < data.len() {
        let mut j = i + 1;
        let mut v = data[i];
        let mut pos = i;
        while j < data.len() {
            if data[j] < v {
                pos = j;
                v = data[j];
            }
            j += 1;
        }
        data.swap(i, pos);
        i += 1;
    }
}

/// 插入排序（效率竟然不如冒泡排序）
pub fn insert_sort<T>(data: &mut [T])where T :PartialOrd {
    let mut count = 0;
    for i in 1..data.len() {
        for j in (1..=i).rev() {
            if data[j] < data[j - 1] {
                data.swap(j, j - 1);
                count += 1;
            } else {
                break;
            }
        }
    }
    println!("count:{}", count);
}
/// 三向快速排序，这里没有随机话，所以为了效率，使用者需要自己随机化数据
pub fn quick_sort_for_three_direction<T>(data: &mut [T], lo: usize, hi: usize)
where
    T: PartialOrd + Clone + Copy + Debug + Display,
{
    if lo >= hi {
        return;
    }
    let mut i = lo + 1;
    let mut gt = hi;
    let mut le = lo;
    let v = data[lo];
    while i <= gt {
        if data[i] == v {
            i += 1;
        } else if data[i] < v {
            data.swap(le, i);
            le += 1;
            i += 1;
        } else {
            data.swap(i, gt);
            gt -= 1;
        }
    }
    if le > lo {
        quick_sort_for_three_direction(data, lo, le - 1);
    }
    quick_sort_for_three_direction(data, i, hi);
}
/// 快速排序，这里没有随机话，所以为了效率，使用者需要自己随机化数据
pub fn quick_sort<T>(data: &mut [T], lo: usize, hi: usize)
where
    T: PartialOrd + Clone + Copy + Debug + Display,
{
    if lo >= hi {
        return;
    }
    if DEBUG {
        println!("lo:{},hi:{}", lo, hi);
    }
    let mut i = lo + 1;
    let mut j = hi;
    let v: T = data[lo];
    loop {
        loop {
            if i < hi && data[i] < v {
                i += 1;
            } else {
                break;
            }
        }
        loop {
            if j > lo && data[j] > v {
                j -= 1;
            } else {
                break;
            }
        }
        if i >= j {
            break;
        }
        if DEBUG {
            println!("swap:{},{}", data[i], data[j]);
            println!("swap id:{},{}", i, j);
        }
        data.swap(i, j);
        i += 1;
        j -= 1;
    }
    if DEBUG {
        println!("swap out:{},{}", data[lo], data[j]);
    }
    data.swap(lo, j);
    if j > 0 {
        quick_sort(data, lo, j - 1);
    }
    quick_sort(data, j + 1, hi);
}

/// 希尔排序（交换次数比插入排序少，但远未达到高效）
pub fn shell_sort(data: &mut [i32]) {
    let mut h = 1;
    while h < data.len() / 3 {
        h = h * 3 + 1;
    }
    if DEBUG {
        println!("h:{}", h);
    }
    let mut count = 0;
    let mut s = h;
    while s >= 1 {
        if DEBUG {
            println!("s:{}", s);
        }
        for i in RangeStep::new(s, data.len(), s) {
            for j in RangeStep::new(i, s - 1, s) {
                if data[j] < data[j - s] {
                    data.swap(j, j - s);
                    count += 1;
                } else {
                    break;
                }
            }
        }
        s /= 3;
    }
    if DEBUG {
        println!("count:{}", count);
    }
}

/// 用于指定步长的迭代usize元素
///
/// 从0开始，元素间相差2，不包含4
/// ```
/// use algorithms_fourth::sort::*;
/// let range = RangeStep::new(0,4,2);
/// ```
///
/// 从4开始，元素间相差2，不包含0
/// ```
/// use algorithms_fourth::sort::*;
/// let range = RangeStep::new(4,0,2);
/// ```
pub struct RangeStep<T> {
    start: T,
    end: T,
    step: T,
    forward: bool,
}
impl RangeStep<usize> {
    pub fn new(start: usize, end: usize, step: usize) -> RangeStep<usize> {
        let forward = start < end;
        if step == 0 {
            panic!("no range: {},{},{}", start, end, step)
        }
        RangeStep {
            start,
            end,
            step,
            forward,
        }
    }
}
impl Iterator for RangeStep<usize> {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        let ans = self.start;
        if self.forward && ans >= self.end || !self.forward && ans <= self.end {
            return None;
        }
        if self.forward {
            self.start += self.step;
        } else {
            self.start -= self.step;
        }
        Some(ans)
    }
}