Rust语言编程实例100题-045

题目：在第39题和42题已经练习过选择排序，插入排序，冒泡排序。今天再来练习新的排序算法——希尔排序。希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。希尔排序又称缩小增量排序，因 DL.Shell 于 1959 年提出而得名。它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

要求：请将下面的数组使用冒泡排序算法排序。

[5, 3, 7, 9, 1, 4, 2, 0, 6, 8]

程序分析：先写出插入排序，插入排序的间隔是1，而希尔排序每次的间隔则不一样。

输出格式：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

知识点：插入排序 希尔排序

fn main() {
   let mut a = [5, 3, 7, 9, 1, 4, 2, 0, 6, 8];

    let mut gap = a.len() / 2;
    while gap > 0 {
        // 插入排序
        for i in gap..a.len() {
            let mut j = i;
            while j > 0 && j >= gap {
                // 交换
                if a[j - gap] > a[j] {
                    a[j - gap] = a[j - gap] ^ a[j];
                    a[j] = a[j - gap] ^ a[j];
                    a[j - gap] = a[j - gap] ^ a[j];
                }
                j -= gap;
            }
        }
        gap /= 2;
    }

    println!("{:?}", a);
}

程序执行结果：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]