Rust 学习 - 归并排序 - 算法 | UniStart = UniStart's Blog = 心在哪里，家在哪里

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

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

实现步骤

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

# 归并排序并返回新数组

归并排序

	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 方法来获取到元素的值拷贝。

Rust 算法

# 归并排序并返回新数组

# 在原数组上进行归并排序

WebGL学习（附录）

通过Github Action跨仓库部署Hexo