- 排序算法
- 选择、冒泡、插入、归并、快速、堆
本文涉及算法的rust源码
对数器
- 对于想测试的算法a
- 找到暴力解法b
- 随机样本生成器c
- 对比a,b生成的结果
-
随机数
use rand::distributions::Uniform; use rand::prelude::*; fn rand_nums(num: usize) -> Vec<i32> { let mut rng = thread_rng(); let distri = Uniform::new_inclusive(0, 10); (&mut rng).sample_iter(distri).take(num).collect() } // 单个数 let mut rng = thread_rng(); let num = rng.sample(Uniform::new(0, 8));
-
cargo.toml
[dependencies] rand = "0.8.5"
-
选择排序
- 算法流程
- 在[0, n-1]找到最小值a[i]
- swap(a, 0, i)
- 在[1, n-1]找最小值a[i]
- swap(a, 1, i)
- 总结
- idx: [0, len-1]
- a[idx] 和 (a[idx+1..len])min
- 让idx上的数是[idx,n)上最小的数
- idx: [0, len-1]
-
代码实现
fn choice_sort(arr: &mut Vec<i32>) { for idx in 0..arr.len() - 1 { let mut min = idx; for compare in idx + 1..arr.len() { min = if arr[min] > arr[compare] { compare } else { min }; } swap(arr, idx, min); } }
冒泡排序
- 算法
- [0, N-1]
- 比较a[i], a[i+1],谁大谁往右移
- 一轮之后a[N-1]是最大值
- [0, N-2]
- 得到a[N-2]是最大值
- [0, N-1]
- 思想
- 每一轮的刷新,都让大数后移
- 每一轮[0, dix)的两两比较,都让大的数后移
-
代码实现
fn bubble_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> { if arr.len() < 2 {return arr;} for sorted_idx in (0..arr.len()).rev() { for i in 0..sorted_idx { if arr[i] > arr[i + 1] { swap(arr, i, i + 1); } } } arr }
异或的性质
- 交换律、结合律
a^b = b^a
- 无进位相加
1 + 1 = 0
1 + 0 = 1
0 ^ x = 0, x^x = 0
a ^ b = b ^ a, a ^ b ^ c = a ^ (b ^ c)
(...A...) ^ B = (...a1...) ^ B ^ (...a2...)
两个数的交换
a = a ^ b; b = a ^ b; a = a ^ b
令 a = 甲,b = 乙
a = a ^ b
:a = 甲 ^ 乙, b = 乙
b = a ^ b
:a = 甲, b = 甲 ^ 乙 ^ 乙 = 甲 ^ 0 = 甲
a = a ^ b
:a = 甲 ^ 乙 ^ 甲 = 0 ^ 乙 = 乙 = b
a, b必须是不同的2块内存,否则
a ^ b = 0
为什么异同满足交换律
- 假设
a = 0b0100, b = 0b1001, c = 0b1111
- 其中某位是否为1,与这1位出现1的奇偶次数有关,与1出现的前后无关
- 所以某位是否为1 = 0 + 1 + 1 = 0
题目
- 在数组中,只有一种数出现奇数次,其他数出现偶数次,如何找到此数
let mut eor: i32 = 0; for cur in arr.iter() { eor ^= cur; } eor
- 在数组中,只有两种数出现奇数次,其他数出现偶数次,如何找到此数
- 算法
a[0]^a[1]^...^a[n]
=x ^ y
- 假设
x^y = 0b010101
,则第1位为1的数不是x就是y - 设
eor = x^y, 且 x != y
,则eor上某一位必不为0 - 设eor的bit[8]=1,说明x,y在bit[8]上一定有一个为1,一个为0
- 那么bit[8]=1可以把arr中的数分成两个部分,一个部分只包含x,一个部分只包含y
- 那么
eor' = a_xory[0] ^ a_xory[1] ^ ... ^ a_xory[i] = xory
- 则
eor ^ eor' = x(或者y)
-
代码实现
pub fn find2num(arr: &Vec<i32>) -> (i32, i32) { let mut eor = 0; // eor = a ^ b let mut eor2 = 0; // eor2 = a or b for cur in arr.iter() { eor ^= cur; } let right_one = eor & (!eor + 1); // 取出最右位的1 for cur in arr.iter() { if cur & right_one != 0 { eor2 ^= cur; } } let a = eor ^ eor2; let b = eor ^ a; (a, b) }
插入排序
arr = [3, 2, 5, 4, 2, 3, 3]
- 算法
- 先实现[0, 0]范围内有序 (ok)
- 实现[0, 1]范围有序, i = 1
- 向左看
-
如果i比左边小,就交换
arr = [2, 3, ...]
-
- 再向左看,越界,退出
- 此时[0, 1]有序 (ok)
- 向左看
- 实现[0, 2]有序, i = 2
-
向左看,此时a[2] > a[1],有序,退出
arr = [2, 3, 5, ...]
-
- 实现[0, 3]有序, i = 3
- 向左看
- a[3] < a[2],swap(a, 2, 3), i = 2
- 向左看
- a[2] > a[1], 有序(ok)
- 向左看
- 思想
- 每轮通过两两交换,把a[idx]插入到a[0:idx-1]中它最大的位置
-
代码实现
fn insert_sort(arr: &mut Vec<i32>) -> &mut Vec<i32> { if arr.len() < 2 { return arr; } for i in 0..arr.len() { for j in (1..=i).rev() { if arr[j] < arr[j - 1] { swap(arr, j, j - 1); } } } arr }
二分法
- 2分法是建立一个排他的规则,每次删除一半,答案在另一半
- 一个问题优化的方向
- 优化数据状况:无序变有序
- 问题标准:可应用2分法
- 比如:
- arr无序,相邻数不相等,求局部最小值
- 局部最小
- 最左侧:
a[0] < a[1]
:a[0]是局部最小 - 最右侧:
a[N-1] > a[N]
:a[N]局部最小 - 中间:
a[i-1] > a[i] < a[i+1]
,a[i]局部最小
- 最左侧:
- 局部最小
- arr无序,相邻数不相等,求局部最小值
-
二分法找arr中的最大值代码实现
fn bin_searchmax(arr: &Vec<i32>, l: usize, r: usize) -> i32 { if l == r { return arr[l]; }; let mid = l + ((r - l) >> 1); let left_max = bin_searchmax(arr, l, mid); let right_max = bin_searchmax(arr, mid + 1, r); return cmp::max(left_max, right_max); }
- 划分过程
arr = [3, 2, 5, 6, 7, 4]
递归的master公式
$T(N) = a \times T(\dfrac{N}{b}) + O(N^d)$
- $log_b{a} > d$: 复杂度为 $O(N^{log_b{a}})$
- $log_b{a} = d$:复杂度为$O(N^d \times log_2{N})$
- $log_b{a} < d$:复杂度为$O(N^d)$
归并排序
- 算法流程
- 找到中心
- 左边排序
- 右边排序
- 合并
-
算法实现
fn merge_arr(left_arr: Vec<i32>, right_arr: Vec<i32>) -> Vec<i32> { let mut i = 0usize; let mut j = 0usize; let capacity = left_arr.len() + right_arr.len(); let mut res: Vec<i32> = Vec::with_capacity(capacity); while i < left_arr.len() && j < right_arr.len() { if left_arr[i] <= right_arr[j] { res.push(left_arr[i]); i += 1; } else { res.push(right_arr[j]); j += 1; } } res.extend_from_slice(&left_arr[i..]); res.extend_from_slice(&right_arr[j..]); res } fn merge_sort(arr: Vec<i32>) -> Vec<i32> { if arr.len() < 2 { return arr; } let mid_plus = (arr.len() + 1) / 2; let mut left_arr = arr; let right_arr = left_arr.split_off(mid_plus); let left_arr = merge_sort(left_arr); let right_arr = merge_sort(right_arr); return merge_arr(left_arr, right_arr); }
- 为什么归并排序可以缩短时间 O(N^2) -> O(N·logN)
- 因为O(N^2)浪费了大量比较行为才搞定一个数
- 选择排序比较了N次,得到一个最小值放到a[0]
- 对于a[1]又要比较N-1次
- 归并排序没有浪费比较行为
- 合并过程是左侧与右侧比较
- 比较信息都留下了,变成一个整体有序的部分
- 所以有序信息是向下传递的
- 每部分都保留了有序信息
- 合成整体时就缩短了时间
- 因为O(N^2)浪费了大量比较行为才搞定一个数
小和问题
小和:每个数左边比当前数小的数之和
arr = [1, 3, 4, 2, 5]
- 1: 左无
- 3: 左有 1
- 4:左有 1+3 = 4
- 2:左有 1
- 5:左有 1+3+4+2 = 10
- 小和为 16
- 求左边比它小,等价于右边有多少个数比它大,它就要被加多少次(产生出多少个小和)
- 1:右边4个数大于它,产生4个1
- 3:右边2个数,生产2个3
- 4:右边1个数,生产1个4
- 2:右边1个数,生产1个2
- 5:右边无
-
代码实现
fn smallsum_merge(left_arr: Vec<i32>, right_arr: Vec<i32>) -> (i32, Vec<i32>) { let mut ss = 0; let mut i = 0; let mut j = 0; let mut merge: Vec<i32> = Vec::new(); while i < left_arr.len() && j < right_arr.len() { if left_arr[i] < right_arr[j] { ss += left_arr[i] * (right_arr.len() - j) as i32; merge.push(left_arr[i]); i += 1; } else { merge.push(right_arr[j]); j += 1; } } merge.extend_from_slice(&left_arr[i..]); merge.extend_from_slice(&right_arr[j..]); (ss, merge) } fn smallsum_process(arr: Vec<i32>) -> (i32, Vec<i32>) { if arr.len() == 1 { return (0, arr); } let mid_plus: usize = (arr.len() + 1) / 2; let mut left_arr = arr; let right_arr = left_arr.split_off(mid_plus); let (ss_left, left_arr) = smallsum_process(left_arr); let (ss_right, right_arr) = smallsum_process(right_arr); let (ss_merge, merge) = smallsum_merge(left_arr, right_arr); return (ss_left + ss_right + ss_merge, merge); }
-
归并的本质
- 递归
- 合并
- 一个有序数组中的元素与另一个有序数组中的元素一一比较
- 但当A组中的元素小于B组中某位置的元素时
- 不再需要与B组中后面的元素再比较了
- 因为B是有序的数组
- 最终也等效于A、B两个数组中的所有元素都一一做了比较
- 所以当要对一个数组中的元素进行一一比较时,就可以用归并排序的思路
- 先递归(调度)
- 是以数组的中间位置为调度分层
- 再合并(比较)
- 先递归(调度)
荷兰国旗
- 点分数组:给定一个数组arr和一个数num,把<=num的书放到左边,>num的数放右边,不用排序
- 算法
- 给定两个变量,把数组划分成三个部分
- edge变量,是 <= 区域的边界
- i变量,是待判定的元素
- [edge, i)是 > 区域
- if arr[i] <= num: swap(arr, edge++, i++);
- else: i++
- 给定两个变量,把数组划分成三个部分
- 思路
- 两个指针
- edge表示它左侧的数是
<= num
的,它是第1个> num
的数 - p表示要检查的数
- 当
a[p] <= num
时,它应该和a[edge]
交换
- edge表示它左侧的数是
- 两个指针
-
具体实现
fn split2part(arr: &mut Vec<i32>, num: i32) { let mut edge: usize = 0; let mut i = 0usize; while i < arr.len() { if arr[i] <= num { arr.swap(i, edge); edge += 1; } i += 1; } } fn split2part(arr: &[i32], num: i32) -> (usize, Vec<i32>) { let mut v: Vec<i32> = arr.into(); let mut i: usize = 0; let mut nle: usize = 0; // <= 的next下一个 while i < arr.len() { if arr[i] <= num { v.swap(i, nle); nle += 1; } i += 1; } (nle, v) }
- 算法
- 给定arr和num,把数据分成<, =, >三个部分
- 算法
- 给定三个变量,把数组分成四个部分
- small:
small-
(small的左边,不包括small) 部分是<num
的区域 - big:
big
部分是>num
的区域 - i:
i+
是待定区域 - [small, big-1]是
==
区域
- small:
- if arr[i] < num, swap(arr, i++, small++);
- if arr[i] > num, swap(arr, i, –big)
- if arr[i] == num, i++
- 给定三个变量,把数组分成四个部分
- 思想
- 用三个指针把arr分成了
<, =, 待定, >
四个区域[.., lt), [lt, i), [i, gt], (gt, ..)
- 对于待定值
arr[i]
情况有三种<: arr.swap(i, lt); lt++
,a.swap(i, lt)
相当于把a[i]
这个小的数放到原来<
区域的旁边1格lt++
:这个区域向右扩大1位,包住交换过来的a[i]
a.swap(i, lt)
还把a[lt]
这个=
区域的数放到刚刚判定a[i]
的位置,相当于=
区域向右平移了一格<
区域是向右扩充的一格,=
区域是向右平移了一格(是长度,区域中数据的顺序是变了的,a[lt]这个头变成了尾)
>: a.swp(i, gt); gt--
a.swap(i, gt)
把考察的数a[i]放到>
区域的左边一格gt--
把这个a[i]包进>
区域a.swap(i, gt)
交换过来[i]位置的a[gt]没有被考察过,所以要在考察<, =, >
的情况
=: i++
:因为a[lt, i)
是=
区域,所以直接向右扩充=
区域
i
从左向右,推着<,=,>
区域运动,当i==gt时,说明待考察a[i]已经落在>
区域中,不用再考察了
- 用三个指针把arr分成了
-
具体实现
fn split3part(arr: &mut Vec<i32>, num: i32) { let mut small = 0usize; // small-1才是<num的区域 let mut big = arr.len(); // big 是>num的区域 let mut i = 0usize; while i < big { if arr[i] < num { arr.swap(i, small); small += 1; i += 1; } else if arr[i] > num { big -= 1; arr.swap(i, big); } else { i += 1; } } } fn split3part(arr: &[i32], num: i32) -> (usize, Vec<i32>) { let mut v: Vec<i32> = arr.into(); let mut i: usize = 0; let mut nlt: usize = 0; let mut gt: usize = arr.len(); // 当前数大于num while i < gt { match v[i].cmp(&num) { Ordering::Less => { v.swap(i, nlt); nlt += 1; i += 1; } Ordering::Greater => { gt -= 1; v.swap(i, gt); } _ => i += 1, } } (gt, v) }
- 算法
快速排序
- 快排算法是荷兰国旗问题的推广
- 算法v1.0
- 确定最后一个数所在的位置
- 用最后一个数做num
- 把数组划分成:[…<= num…], [..>num..], [num] 三个区域
- 把num和[>num]区域的第1个数交换,得到[…<=num…],[num], […>num..]区域
- 同时,这个交换的num所在的位置就是它在排好序数组中应该在的位置
- 把这个数左右两边递归快排
- 确定最后一个数所在的位置
- 算法v2.0
- 确定最后一个数及其相等的数所在的位置
- 用最后一个数做num
- 把数组划分成:[…< num…], [..=num..], [..>num..], [num] 四个区域
- 把num和[>num]区域的第1个数交换,得到[.<num..], [..=num..], [..>num..]三个区域
- 同时,这个交换的num所在的位置就是它在排好序数组中应该在的位置
- 在左右两边递归
- 确定最后一个数及其相等的数所在的位置
- 算法v3.0
- 确定随机指定的数及等数所在的位置
- 随机待定一个数和最后一个数交换
- 划分数组:[..<num..], [..=num..], [..>num..], [num]
- 其中small, big所在的位置是[=num]的两侧
- [..<num..], [small..=num..big], [..>num..]
- a[small] == num, a[small-1] < num
- a[big] == num, a[big+1] > num
- 交换num和[>num]的第1个数
- 递归
- 确定随机指定的数及等数所在的位置
- 算法v1.0
-
算法v1.0
fn quick_sort1(mut arr: Vec<i32>) -> Vec<i32> { if arr.len() <= 1 { return arr; } let last_idx = arr.len() - 1; let num = arr[last_idx]; let mut small = 0usize; let mut i = 0usize; while i < last_idx { if arr[i] <= num { swap(&mut arr, i, small); small += 1; } i += 1; } swap(&mut arr, small, last_idx); let right_arr = arr.drain(small + 1..).collect(); let left_arr = arr.drain(0..small).collect(); let left_sorted = quick_sort1(left_arr); let right_sorted = quick_sort1(right_arr); [left_sorted, right_sorted].join(&num) } fn quick_sort1(arr: &[i32]) -> Vec<i32> { if arr.len() <= 1 { return arr.into(); } let privot = arr.len() - 1; let n = arr[privot]; let (nidx, mut v) = split2part(&arr[..privot], n); v.push(n); v.swap(privot, nidx); let lv = quick_sort1(&v[0..nidx]); let rv = quick_sort1(&v[nidx + 1..]); [lv, rv].join(&n) }
-
算法v2.0
fn quick_sort2(mut arr: Vec<i32>) -> Vec<i32> { if arr.len() <= 1 { return arr; } let mut outline = false; let mut i = 0usize; let last = arr.len() - 1; let mut small = 0usize; // [0, small-1]是<num的区域 let mut big = last - 1; // [big+1, end]是>num的区域 let num = arr[last]; while i <= big { if arr[i] < num { arr.swap(i, small); small += 1; i += 1; } else if arr[i] > num { arr.swap(i, big); //rust的usize>= 0 if big == 0 { outline = true; break; } else { big -= 1; } } else { i += 1; } } if outline { // >num区的第1个数在0位置时,要单独处理 arr.swap(i, last); big = 0; } else { // 把最后一个数和>num区的第1个数交换 arr.swap(big + 1, last); // >num边界同时向右移 big += 1; // 保证big_plus是>num的区域 [big+1, end] } // arr => [small_arr, equal_arr, big_arr] let big_arr = arr.drain(big + 1..).collect(); let small_arr = arr.drain(0..small).collect(); let big_sorted = quick_sort2(big_arr); let small_sorted = quick_sort2(small_arr); [small_sorted, big_sorted].join(&arr[..]) } fn split3part(arr: &[i32], num: i32) -> (usize, Vec<i32>) { let mut v: Vec<i32> = arr.into(); let mut i: usize = 0; let mut nlt: usize = 0; let mut gt: usize = arr.len(); while i < gt { match v[i].cmp(&num) { Ordering::Less => { v.swap(i, nlt); nlt += 1; i += 1; } Ordering::Greater => { gt -= 1; v.swap(i, gt); } _ => i += 1, } } (gt, v) } fn quick_sort2(arr: &[i32]) -> Vec<i32> { if arr.len() <= 1 { return arr.into(); } let privot = arr.len() - 1; let n = arr[privot]; let (nidx, mut v) = split3part(&arr[..privot], n); v.push(n); v.swap(privot, nidx); let lv = quick_sort2(&v[0..nidx]); let rv = quick_sort2(&v[nidx + 1..]); [lv, rv].join(&n) }
-
算法3.0
-
随机选择一个数作为privot
extern crate rand; use rand::prelude::*; fn random_num(range: std::ops::Range<i32>) -> i32 { let mut rng = thread_rng(); rng.gen_range(range) } fn quick_sort3(arr: &[i32]) -> Vec<i32> { let mut v: Vec<i32> = arr.into(); if arr.len() <= 1 { return v; } let lidx = arr.len() - 1; let privot = random_num(0..arr.len() as i32) as usize; let n = arr[privot]; v.swap(privot, lidx); let (nidx, mut v) = split3part(&v[..lidx], n); v.push(n); v.swap(lidx, nidx); let lv = quick_sort2(&v[0..nidx]); let rv = quick_sort2(&v[nidx + 1..]); [lv, rv].join(&n) }
-
-
堆排序
堆
- 堆是用数组实现的完全二叉树结构
- 最大堆(大根堆)
- 每棵子树的最大值在顶端
- 最小堆(小根堆)
- 每棵子树的最小值在顶端
- 完全二叉树
- 满二叉树
- 每层都满的二叉树
- 从左到右依次变满的二叉树
- 满二叉树
- 最大堆(大根堆)
- 用数组表示
- [i]的左子: [2*i + 1]
- [i]的右子: [2*i + 2]
- [i]的父: [(i-1)/2]
heap insert 过程
- 最大堆的建构过程
- 算法
- heapsz = 0
- heap_insert(5)
- a[heapsz++] = 5
- heapsz = 1
- a = [5]
- heap_insert(3)
- a[heap_size++] = 3
- heapsz = 2
- a = [5, 3]
- heap_insert(6)
- a[heapsz++] = 6
- a = [5, 3, 6]
- a[2] = 6 > a[(2-1)/2]=a[0]=5
- swap(a, 2, 0)
- a = [6, 3, 5]
- heapsz = 3
- heap_insert(7)
- a[heapsz++] = 7
- a = [6, 3, 5, 7]
- a[3] = 7 > a[1] = 5
- swap(a, 3, 1)
- a = [6, 7, 5, 3]
- a[1] = 7 > a[0] = 6
- swap(a, 1, 0)
- a = [7, 6, 5, 3]
- heapsz = 4
- heap_insert(7)
- a[heapsz++] = 7
- a = [7, 6, 5, 3, 7]
- a[4] = 7 > a[1] = 6
- swap(a, 4, 1)
- a = [7, 7, 5, 3, 6]
- 思想
- 将新num放到堆数组最后一位
- 从最后一位和它的父节点比较,大于父节点就交换
- 直到不大于或到root
-
代码实现
fn heap_insert(arr: &mut Vec<i32>, num: i32) { arr.push(num); let mut i = arr.len() - 1; if i == 0 { return; } while i > 0 && arr[i] > arr[(i - 1) / 2] { arr.swap(i, (i - 1) / 2); i = (i - 1) / 2; } } #[derive(Debug)] struct Heap { heap: Vec<i32>, } impl Heap { fn new() -> Self { Self { heap: Vec::new() } } fn insert(&mut self, num: i32) { self.heap.push(num); let mut nidx = self.heap.len() - 1; while nidx > 0 { let parent = (nidx - 1) / 2; if self.heap[parent] < self.heap[nidx] { self.heap.swap(parent, nidx); nidx = parent; } } } }
- 算法
- 堆化 heapify
- 从堆中取出最大值后,堆仍保持最大堆
- 算法
- 取出a[0]
- 令a[0] = a[- -heapsz]
- i = 0
- 取 max_id = max(a[2i+1], a[2i+2])
- if a[0] < a[max_id]:
- swap(a, 0, max_idx)
- i = max_idx
- 直到 i 越界
- 思想
- 读取root
- 让h[0] = heap的最后一位
- 不断的把子节点中大的那个顶上来
-
代码实现
fn heapify(arr: &mut Vec<i32>, idx: usize, heapsize: usize) { let mut i = idx; let mut left = 2 * i + 1; while left < heapsize { let right = left + 1; let max_idx = if right < heapsize && arr[left] < arr[right] { right } else { left }; let max_idx = if arr[i] < arr[max_idx] { max_idx } else { i }; if max_idx == i { break; } arr.swap(i, max_idx); i = max_idx; left = 2 * i + 1; } } fn pop(&mut self) -> Option<i32> { if self.heap.len() <= 1 { return self.heap.pop(); } let root = self.heap.swap_remove(0); let last = self.heap.len() - 1; let mut parent: usize = 0; let mut lchd: usize = 2 * parent + 1; while lchd < last { let rchd: usize = lchd + 1; let max_idx = if rchd < last && self.heap[lchd] > self.heap[rchd] { lchd } else { rchd }; if self.heap[parent] >= self.heap[max_idx] { break; } self.heap.swap(parent, max_idx); parent = max_idx; lchd = 2 * parent + 1; } Some(root) }
堆排序
- 算法
- 把数组通过heap_insert变成最大堆
- 把a[0]和最后一个数交换,同时减少heapsize
- swap(arr, 0, - -heapsize);
- 直到所有元素都排好序
- 思想
- heap[0..end]
- 1
- heap.swap(0, end)
- heap = heap[0..end-1]
- heapify(heap)
- 2
- heap.swap(0, end-1)
- heapify(heap)
- heap = heap[0..end-2]
- 1
- 把最大堆的第一个数放到最后
- 把最后这个最大数从最大堆中除名
- 堆长度-1
- heap[0..end]
-
代码实现
fn heap_sort(arr: Vec<i32>) -> Vec<i32> { let mut res: Vec<i32> = Vec::new(); for num in arr { heap_insert(&mut res, num); } let mut heapsize = res.len(); while heapsize > 0 { res.swap(0, heapsize - 1); heapsize -= 1; heapify(&mut res, 0, heapsize); } res } fn sort(&mut self, arr: &[i32]) -> Vec<i32> { for num in arr { self.insert(*num); } let mut v: Vec<i32> = vec![]; while let Some(num) = self.pop() { v.push(num); } v.into_iter().rev().collect() }
题目
- 已知一个几乎有序的数组(数组要排好序,每个元素移动的距离 < k, k较小)。选择合适的算法排序
- 算法
- 先把k个数字放到最小堆中
- 堆顶一定是k个数字中最小的元素(数组几乎有序)
- 把a[0]弹出
- 再a[7]放到a[0],进行堆化,得到a[1:7]的最小值
- 把a[1]弹出,重复进行,直到最后
- 思想
- 最小堆就是总是可以确定一堆数中的最小值
-
代码实现
use std::cmp::Reverse; use std::collections::BinaryHeap; fn sortarr_distancek(arr: &mut Vec<i32>, k: usize) -> Vec<i32> { let mut min_heap = BinaryHeap::new(); let mut res: Vec<i32> = vec![]; for i in 0..k { min_heap.push(Reverse(arr[i])); } for i in k..arr.len() { if let Some(Reverse(min_val)) = min_heap.pop() { res.push(min_val); } min_heap.push(Reverse(arr[i])); } while let Some(Reverse(min_val)) = min_heap.pop() { res.push(min_val); } res }
- 算法
比较器的作用
- 比较器返回负数时
- 第1个参数在前面
- 升序排列
- 比较器返回正数时
- 第2个参数在前面
- 逆序排列
桶排序
- 不基于比较的排序,一定是根据数据的特定状况定制的方法
- 记数排序
- 员工年龄
- 申请age_freq[200]
- 遍历所有年龄,统计年龄词频
- age_freq[age[i]]++
- 得到age_freq = [7, 3, 4, ….]
- 恢复成
- age = [7个0, 3个1, 4个2, ….]
- 缺点
- 数据跨度大[-10^20, 10^20]
- 要申请大容量的数组
- 员工年龄
- 基数排序
- 排序[17, 13, 25, 100, 72]
- 算法
- 补成相同位数 [017, 013, 025, 100, 072]
- 准备10个桶b[0], b[1], … b[9]
- 按个位数依次进桶
- b[0] = [100]
- b[2] = [072]
- b[3] = [013]
- 从左到右依次出桶
- a = [100, 072, 013, …]
- 按十位数进桶、再出桶
- 按百位数进桶、再出桶
- a = [013, 017, 025, 072, 100]
- 说明
- 根据基数排序
- 百位最后排序,它优先级最高,所以百位可以到数组最右边
- 越晚排
- 越靠近想要的结果
- 先排年龄
- 再排班级
- 最后就是按班级排序
- 相同班级按年龄排序
- 根据基数排序
- 思想
- 基数相当于某些特征t1,t2,t3
- 将数据放到t1特征取值的桶里,再依次从桶里取出放到arr中,相当于arr中的数据对t1特征进行了排序
- 再将arr的数据放到t2的各种桶里,相当于arr中的数据在保留了t1顺序的情况下,以t2特征值的顺序进行了排序;这时arr中的数据严格拥有t2的特征值顺序,在相同的特征值桶里,数据有着t1特征值顺序
-
基数桶排序代码实现1
```rust fn radix_sort(arr: Vec<i32>, ndigit: usize) -> Vec<i32> { let mut arr = arr; let mut buckets: Vec<Vec<i32>> = vec![vec![]; 10]; for d in 0..ndigit { for i in 0..arr.len() { let dnum = get_digit(arr[i], d); buckets[dnum].push(arr[i]); } let mut i = 0usize; for bucket in buckets.iter_mut() { for &num in bucket.iter() { arr[i] = num; i += 1; } bucket.clear(); } } arr } ``` - 用前缀和实现基数桶排序实现2 ```rust fn radix_sort2(arr: Vec<i32>, ndigit: usize) -> Vec<i32> { let mut arr = arr; let mut help = vec![0; arr.len()]; for digit in 0..ndigit { // 词频 let mut count: Vec<usize> = vec![0; 10]; for &num in arr.iter() { count[get_digit(num, digit)] += 1; } // 前缀和 for i in 1..count.len() { count[i] += count[i - 1]; } // 排序 for i in (0..arr.len()).rev() { let idx = get_digit(arr[i], digit); help[count[idx] - 1] = arr[i]; count[idx] -= 1; } for i in 0..help.len() { arr[i] = help[i]; } } arr } ```
排序算法的总结
稳定性
- 定义
- 排序过程不会改变相同数据的先后顺序
- 稳定
- 冒泡排序
- 插入排序
- 归并排序
- 不稳定
- 选择排序
- 快速排序
- 堆排序
性能
排序 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
选择排序 | $O(N^2)$ | $O(1)$ | × |
冒泡排序 | $O(N^2)$ | $O(1)$ | ✓ |
插入排序 | $O(N^2)$ | $O(1)$ | ✓ |
归并排序 | $O(N \times log_2{N})$ | $O(N)$ | ✓ |
快速排序 | $O(N \times log_2{N})$ | $O(log_2{N})$ | × |
堆排序 | $O(N \times log_2{N})$ | $O(1)$ | × |
在大量的实践中,快速排序表现好于归并排序
问题
- 把奇数在左、偶数在右,
- 算法:快速排序中的partition
fn split_oddeven_quick(arr: &mut Vec<i32>) { let mut odd = 0usize; let mut i = 0usize; while i < arr.len() { if arr[i] % 2 == 0 { arr.swap(i, odd); odd += 1; } i += 1; } }
- 要求相对原始次序不变
- 算法:归并排序
fn merge_oddeven_arr( left: Vec<i32>, edgel: usize, right: Vec<i32>, edger: usize, ) -> (usize, Vec<i32>) { let mut res = vec![]; res.extend_from_slice(&left[..edgel]); res.extend_from_slice(&right[..edger]); res.extend_from_slice(&left[edgel..]); res.extend_from_slice(&right[edger..]); (edgel + edger, res) } fn merge_oddeven(arr: Vec<i32>) -> (usize, Vec<i32>) { if arr.len() == 1 { let edge = if arr[0] % 2 != 0 { 0 } else { 1 }; return (edge, arr); } let mid_plus = (arr.len() + 1) / 2; let mut left = arr; let right = left.split_off(mid_plus); let (edge_l, left) = merge_oddeven(left); let (edge_r, right) = merge_oddeven(right); merge_oddeven_arr(left, edge_l, right, edge_r) }
哈希表和有序表
- 哈希表
- 只有key的是HashSet
- 有key:val的是HashMap
- HashMap的增、删、改、查是O(1),只是常数时间大
- 有序表 TreeSet和TreeMap
- 时间复杂度:O(logN)级别
- 红黑树、AVL树、SB树