rust-algorithms:14-希尔排序

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;
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!