lt-wei / rust-learning

1.基础要求：固定类型（比如i32）的数组排序

2.提高部分：能够使用范型和PartialOrd实现对任意类型的排序

知识点补充

1. 泛型（Generics）：泛型是一种在编写代码时不指定具体类型，而在使用时再确定类型的方式。在Rust中，你可以用泛型来编写函数或结构体，使它们能够处理多种数据类型。例如，Vec是一个可以存储任意类型T的向量。

2. 特征（Traits）：特征类似于其他语言中的接口，它定义了类型应该实现的方法。PartialOrd是Rust标准库中的一个特征，它为可以部分排序的类型提供功能。如果一个类型实现了PartialOrd，它就可以使用<、>、<=和>=等比较操作符。

3. 切片（Slices）：切片是对数组的引用，允许你访问数组的一部分而不是整个数组。在函数中使用切片参数可以使函数更加灵活，能够处理任意长度的数组。例如，&[i32]是一个指向i32数组某一部分的切片。

4. 可变引用（Mutable References）：在Rust中，你可以通过可变引用来修改数据。使用&mut关键字可以创建一个可变引用，允许你改变引用所指向的值。

5. 冒泡排序的基本**：冒泡排序是一种简单直观的排序算法。它重复地遍历待排序的列表，比较每一对相邻元素的值，如果它们的顺序错误就把它们交换过来。遍历列表的工作会重复进行，直到没有再需要交换的元素，这意味着列表已经排序完成。由于这个算法会在最坏的情况下，对每对相邻元素都进行比较，因此它被称为“冒泡”排序，因为较大的元素会慢慢“浮”到列表的顶端（假设排序是升序排序）。

编写冒泡排序算法

基于以上知识点，我们来一步步实现冒泡排序算法。

步骤1：定义泛型函数

我们的冒泡排序函数将是一个泛型函数，这意味着它可以接受任意类型的数组进行排序，只要这些类型支持比较操作。

fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
    // 函数体将在后续步骤中实现
}

这里，T: PartialOrd表明这个函数接受任何实现了PartialOrd特征的类型T。&mut [T]表示函数接受一个T类型的可变切片作为参数。

步骤2：实现排序逻辑

排序逻辑详解

1. 初始化状态：设置一个布尔变量swapped，用来标记在一次遍历中是否进行了元素的交换。如果在一次遍历结束时swapped仍为false，说明序列已经排序完成，可以结束排序过程。

2. 遍历和比较：从序列的开始遍历到结束，依次比较相邻的元素。如果一对元素是逆序的（即前一个元素大于后一个元素），则交换它们的位置，并将swapped标记为true。

3. 优化遍历范围：每完成一次完整的遍历，序列的最后一个元素必然是当前序列中最大的元素，因此下一次遍历时可以不考虑它。通过逐渐减小遍历的范围来优化算法的性能。

排序逻辑的详细实现

我们将使用一个布尔变量swapped来跟踪是否发生了交换。如果在一次完整的遍历中没有任何交换，那么列表已经是有序的，我们可以停止排序过程。

1. 初始化：首先，我们设置swapped为true，以确保能够进入排序循环。同时，我们获取列表的长度n，以便知道需要遍历的范围。

   let mut n = arr.len();
   let mut swapped = true;

2. 遍历列表：使用while循环来重复遍历列表。循环的条件是swapped为true。在每次循环的开始，我们将swapped设置为false，因为我们还没有执行任何交换操作。

   swapped {
     swapped = false;

3. 比较并交换元素：在while循环内部，我们使用一个for循环来遍历列表中的元素。因为我们需要比较每对相邻的元素，所以循环的范围是1到n（不包括n，因为我们会比较i和i-1的元素）。

   for i in 1..n {
   if arr[i - 1] > arr[i] {
       arr.swap(i - 1, i);
       swapped = true;
       }
   }

在这个循环中，我们检查每一对相邻元素（arr[i - 1]和arr[i]）。如果它们的顺序是错误的（即arr[i - 1]比arr[i]大），我们就使用swap方法交换这两个元素的位置，并将swapped设置为true，表示发生了交换。

4. 减少遍历的范围：在完成一次完整的遍历后，我们知道列表的最后一个元素一定是当前遍历中的最大值，因此在下一次遍历时，我们可以不再考虑它。所以，我们将n减1，缩小下一次遍历的范围。

   n -= 1;
   }

Rust实现

下面是使用Rust语言实现冒泡排序的示例代码，该实现利用了泛型和PartialOrd特征来支持对任意可排序类型的排序：

fn bubble_sort<T: PartialOrd>(arr: &mut [T]) {
    let mut n = arr.len();
    let mut swapped = true;

    while swapped {
        swapped = false;
        for i in 1..n {
            if arr[i - 1] > arr[i] {
                arr.swap(i - 1, i);
                swapped = true;
            }
        }
        n -= 1;
    }
}

步骤3：测试函数

为了测试我们的冒泡排序函数，我们可以在main函数中创建几个不同类型的数组，并对它们进行排序。

fn main() {
    let mut numbers = [5, 3, 8, 4, 2];
    bubble_sort(&mut numbers);
    println!("{:?}", numbers);

    let mut words = ["banana", "apple", "orange", "pear"];
    bubble_sort(&mut words);
    println!("{:?}", words);
}

这样，你就完成了一个能够对任意支持部分排序的类型进行排序的冒泡排序算法的实现。通过这个例子，你可以看到泛型和特征是如何使Rust代码更加灵活和强大的。