Rust语言编程例子 第045题:希尔排序

Rust语言编程题目:在第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]

下一章:Rust语言编程例子 第046题:匹配练习

Rust语言编程题目:在编写程序的时候,常常因为疏忽或者懒惰没有处理函数调用的返回值,给代码的稳定性增添了隐患。如果是Rust编程,你不用有这样的顾虑。学习Rust中Result的用法。要求:编写 ...