插入排序
主问题重现
我们在下面用形式化语言1 给出主问题的一个重现:
输入
个数的数组
输出
输入数组的升序排列 , 满足
主问题思考
这个主问题是我们本章将要讨论的基点. 是一个非常经典的排序问题. 在这里我们引入一个相对简单的排序: 插入排序(Insert Sort).
来看下面实现:
INSERT-SORT
#![allow(unused)]
fn main() {
pub fn insert_sort<T: Ord>(arr: &mut [T]) {
for i in 1..arr.len() {
let mut j = i;
while j > 0 && arr[j] < arr[j - 1] {
arr.swap(j, j - 1);
j -= 1;
}
}
}
}可以发现: 插入排序的核心逻辑是通过逐步比较和移动元素来维护一个有序的子序列. 具体地:
- 有序部分逐步扩张: 将数组分为已排序部分(初始仅含第一个元素)和未排序部分, 每次从未排序部分取出第一个元素, 将其插入到已排序部分的正确位置, 直到所有元素有序.
- 原地插入: 插入操作通过依次向后移动元素实现, 无需额外空间.
Note
这里我们采用了泛型, 使得任何实现了
Ord trait的数组(切片)均可进行插入排序.
另一种方法不通过swap交换, 而是将操作值保存, 直到最后再进行赋值, 像接下来的实现:
#![allow(unused)]
fn main() {
pub fn insert_sort_of_copy<T: Ord + Copy>(arr: &mut [T]) {
for i in 1..arr.len() {
// 保存当前元素的值
let key = arr[i];
// 找到合适的插入位置
let mut j = i;
while j > 0 && key < arr[j - 1] {
// 向后移动元素而不是交换
arr[j] = arr[j - 1];
j -= 1;
}
// 将保存的值插入到正确位置
arr[j] = key;
}
}
}Note
需要
Copy
同理, 也可以使用Clone:
#![allow(unused)]
fn main() {
pub fn insert_sort_of_clone<T: Ord + Clone>(arr: &mut [T]) {
for i in 1..arr.len() {
// 保存当前元素的值
let key = arr[i].clone();
// 找到合适的插入位置
let mut j = i;
while j > 0 && key < arr[j - 1] {
// 向后移动元素而不是交换
arr[j] = arr[j - 1].clone();
j -= 1;
}
// 将保存的值插入到正确位置
arr[j] = key;
}
}
}练习与回答
- 尝试将INSERT-SORT改为降序排列(满足 ).
#![allow(unused)]
fn main() {
pub fn insert_sort_in_reverse<T: Ord>(arr: &mut [T]) {
for i in 0..arr.len() - 1 {
let mut j = i;
while j > 0 && arr[j] > arr[j - 1] {
arr.swap(j, j - 1);
j -= 1;
}
}
}
}Note
可以发现: 在插入排序中, 只需修改比较条件即可改变排序方向
所以我们也有下面这种设置排序规则的:
#![allow(unused)]
fn main() {
// 实现以`compare`来控制排序规则的插入排序
pub fn insert_sort_by<T, F>(arr: &mut [T], compare: F)
where
F: Fn(&T, &T) -> bool,
{
for i in 1..arr.len() {
let mut j = i;
while j > 0 && compare(&arr[j], &arr[j - 1]) {
arr.swap(j, j - 1);
j -= 1;
}
}
}
}上面这种比较, 对于基础较好的读者来说, 应该不成问题. 这个比较很显然的允许我们操作一些更特殊的类型, 比如说结构体:
#[derive(Debug)]
struct Person {
name: String,
age: u32,
}
pub fn insert_sort_by<T, F>(arr: &mut [T], compare: F)
where
F: Fn(&T, &T) -> bool,
{
for i in 1..arr.len() {
let mut j = i;
while j > 0 && compare(&arr[j], &arr[j - 1]) {
arr.swap(j, j - 1);
j -= 1;
}
}
}
fn main() {
// 创建可变的结构体数组
let mut people = vec![
Person { name: "Alice".to_string(), age: 30 },
Person { name: "Bob".to_string(), age: 25 },
Person { name: "Charlie".to_string(), age: 35 },
];
// 按年龄升序排序
insert_sort_by(&mut people, |a, b| a.age < b.age);
println!("按年龄排序: {:?}", people);
// 按名字字典序排序
insert_sort_by(&mut people, |a, b| a.name < b.name);
println!("按名字排序: {:?}", people);
}我们再来看别的例题, 继续深化学习:
- 考虑以下查找问题:
输入: 个数的数组 和一个值
输出: 下标使得, 或者当不在出现时, 返回特殊值2
尝试给出一个线性查找3的例子.
观察来看, 这道题目适合
Option可以用Option::None来解决NIL.
LINEAR-SEARCH
#![allow(unused)]
fn main() {
pub fn linear_search<T: PartialEq>(arr: &[T], v: T) -> Option<usize> {
for i in 0..arr.len() {
if v == arr[i] {
return Some(i);
}
}
None
}
}