rust-algorithms:14-希尔排序

godme 的个人博客 / 0 / 0 / 创建于 2年前

pub fn shell_sort<T: Ord + Copy>(values: &mut Vec<T>) {
    fn insertion_with_gap<T: Ord + Copy>(arr: &mut [T], start: usize, gap: usize) {
        // 带间隙的插入排序
        for index in ((start + gap)..arr.len()).step_by(gap) {
            let current_value = arr[index];
            let mut current_index = index;
            // 存储当前的数值，顺序挪动数字，减少swap交换的重复移位
            while current_index >= gap && arr[current_index - gap] > current_value {
                arr[current_index] = arr[current_index - gap];
                current_index -= gap;
            } 
            // 找到属于自己的位置，回填值
            arr[current_index] = current_value;
        }
    } 
    let mut gap = values.len() / 2;
    // 修改间隙
    while gap > 0 {
        for start in 0..gap {
            insertion_with_gap(values, start, gap);
        }
        gap /= 2;
    }
}