UniStart's Blog心在哪里，家在哪里

Rust学习-归并排序

分类标签

分而治之（Divide and Conquer）：将一个复杂的问题，分解成若干个规模相同或类似的子问题，然后再对这些子问题再进一步细分，直到最后的子问题变得很简单，很容易就能被求解出来，这样这个复杂的问题就求解出来了。

归并排序中就运用到了分而治之的思想。

实现步骤

  1. 对数组进行拆分，后面具体实现中是对数组进行左右两等分（二路归并）
  2. 分别对拆分后的左右数组进行排序
  3. 当待排序数组只有一个元素时直接返回该数组
  4. 将左右排序好的数组合并成一个数组，并返回

归并排序并返回新数组

pub mod merge_not_inplace {
    use std::fmt::Debug;

    pub fn merge_sort<T>(origin_arr: Vec<T>) -> Vec<T>
        where
            T: Debug + Eq + Ord + Clone,
    {
        if origin_arr.is_empty() {
            panic!("This array is empty!");
        }

        // 如果分解到只剩一个数，返回该数
        if origin_arr.len() == 1 {
            return origin_arr;
        }

        // 将待排序数组分解成两半
        let mid = origin_arr.len() / 2;
        let mut left_arr = origin_arr[0..mid].to_vec();
        let mut right_arr = origin_arr[mid..].to_vec();

        // 嵌套调用，对两半分别进行排序
        left_arr = merge_sort(left_arr);
        right_arr = merge_sort(right_arr);

        // 合并排序后的两半
        let merged = merge(left_arr, right_arr);

        return merged;
    }

    fn merge<T>(left_arr: Vec<T>, right_arr: Vec<T>) -> Vec<T>
        where
            T: Debug + Eq + Ord + Clone,
    {
        if left_arr.is_empty() {
            panic!("left array is empty!")
        }
        if right_arr.is_empty() {
            panic!("right array is empty!")
        }

        let mut li = 0usize;
        let mut ri = 0usize;
        let mut result = Vec::<T>::with_capacity(left_arr.len() + right_arr.len());

        // 轮流从两个数组中取出较小的值，放入合并后的数组中
        while li < left_arr.len() && ri < right_arr.len() {
            if left_arr[li] <= right_arr[ri] {
                result.push(left_arr.get(li).unwrap().clone());
                li += 1;
            } else {
                result.push(right_arr.get(ri).unwrap().clone());
                ri += 1;
            }
        }

        // 如果两个数组有一个先结束了，就将另一个数组的元素直接依次放入进来
        if li < left_arr.len() {
            for i in li..left_arr.len() {
                result.push(left_arr.get(i).unwrap().clone());
            }
        } else {
            for i in ri..right_arr.len() {
                result.push(right_arr.get(i).unwrap().clone());
            }
        }

        result
    }
}

在原数组上进行归并排序

pub mod merge_inplace {
    pub fn merge_sort<T: Clone + Eq + Ord>(arr: &mut [T]) {
        let len = arr.len();
        if len < 2 {
            return;
        }
        let mid = len / 2;
        merge_sort(&mut arr[..mid]);
        merge_sort(&mut arr[mid..]);
        merge(arr, mid);
    }

    fn merge<T: Clone + Eq + Ord>(arr: &mut [T], mid: usize) {
        let mut left = arr[..mid].to_vec();
        let mut right = arr[mid..].to_vec();
        let mut i = 0;
        let mut j = 0;
        let mut k = 0;
        while i < left.len() && j < right.len() {
            if left[i] <= right[j] {
                arr[k] = left[i].clone();
                i += 1;
            } else {
                arr[k] = right[j].clone();
                j += 1;
            }
            k += 1;
        }
        while i < left.len() {
            arr[k] = left[i].clone();
            i += 1;
            k += 1;
        }
        while j < right.len() {
            arr[k] = right[j].clone();
            j += 1;
            k += 1;
        }
    }
}

Rust中的数组包括定长数组和可变数组，前者的类型为[T; Sized]，后者类型为Vec<T>，注意从数组中获取值时，通常获得的是值的一个引用（或者说是一个借用），这是由于Rust所有权机制导致的。如果想要在合并数组时，取得待合并元素本身而不是其引用，就需要泛型T实现Clone Trait约束，这样才可以通过clone方法来获取到元素的值拷贝。