[算法设计与分析-从入门到入土] 基础算法
个人导航
知乎：https://www.zhihu.com/people/byzh_rc
CSDN：https://blog.csdn.net/qq_54636039
注：本文仅对所述内容做了框架性引导，具体细节可查询其余相关资料or源码
参考文章：各方资料
文章目录
- [算法设计与分析-从入门到入土] 基础算法
- 个人导航
- 二分查找(binary search)
- 合并算法(merge two sorted lists)
- 选择排序(selection sort)
- 插入排序(insertion sort)
- 自底向上的合并(bottom-up merge sort)
- 基数排序radix sort
- 快速排序quicksort
- 算法总结
二分查找(binary search)
- 若数组长度为 2n（偶数）：取第 n 个元素为中间值，左侧n − 1 n-1n−1个元素，右侧 n 个元素
- 若数组长度为2 n + 1 2n+12n+1（奇数）：取第 n 个元素为中间值，左右两侧各 n 个元素
合并算法(merge two sorted lists)
场景: 数组区间[ p , q ] [p,q][p,q]和[ q + 1 , r ] [q+1,r][q+1,r]已分别有序，需合并为[ p , r ] [p,r][p,r]的有序数组
思路: 双指针法 + 额外开辟长度为 n 的辅助空间，排序后赋值回原数组
- 元素赋值次数：2n 次
- 比较次数：min ( n 1 , n 2 ) ∼ ( n − 1 ) \min(n_1,n_2) \sim (n-1)min(n1,n2)∼(n−1)次（n 1 , n 2 n_1,n_2n1,n2为两个子数组长度）
选择排序(selection sort)
序列: [已排序序列, 未排序序列]
思路: 每一轮从未排序子序列中选择最小值，放入已排序子序列的末尾
- 比较次数：固定为n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1)次
- 元素赋值次数：0 ∼ 3 ( n − 1 ) 0 \sim 3(n-1)0∼3(n−1)次（最优情况无需交换，最差情况需n − 1 n-1n−1次交换）
插入排序(insertion sort)
序列: [已排序序列, 未排序序列]
思路: 已排序序列的初始长度为 1，逐个将未排序元素插入已排序部分的合适位置
重点: 执行移动操作而非交换操作
- 比较次数：n − 1 ∼ n ( n − 1 ) 2 n-1 \sim \frac{n(n-1)}{2}n−1∼2n(n−1)次（最优为数组已有序，最差为数组逆序）
- 元素赋值次数：2 ( n − 1 ) ∼ 2 ( n − 1 ) + ∑ k = 1 n − 1 k 2(n-1) \sim 2(n-1)+\sum_{k=1}^{n-1}k2(n−1)∼2(n−1)+∑k=1n−1k次
自底向上的合并(bottom-up merge sort)
设A是一个包含n个元素的数组
- 首先，分成⌊ n / 2 ⌋ \lfloor n/2 \rfloor⌊n/2⌋个长度为 2 的已排序序列
(若存在 1 个剩余元素，则将其传递到下一轮迭代) - 其次，合并⌊ n / 4 ⌋ \lfloor n/4 \rfloor⌊n/4⌋个连续的 “长度为 2 的序列” 对，得到⌊ n / 4 ⌋ \lfloor n/4 \rfloor⌊n/4⌋个长度为 4 的已排序序列
(若剩余 3 个元素，则将其中 2 个元素与 1 个元素合并) - 重复此过程
若当前的合并步长为2 j − 1 2^{j-1}2j−1, 待合并的剩余元素为 k 个:
- 若1 ≤ k ≤ 2 j − 1 1 \le k \le 2^{j-1}1≤k≤2j−1：剩余元素传递至下一轮合并
- 若2 j − 1 < k < 2 j 2^{j-1} < k < 2^j2j−1<k<2j：剩余元素需要在当前轮完成合并
| 轮次指标 | 比较次数C j C_jCj | 赋值次数A j A_jAj |
|---|---|---|
| 单轮计算 | n 2 j ( 2 j − 1 ∼ 2 j − 1 ) \frac{n}{2^j}(2^{j-1} \sim 2^j-1)2jn(2j−1∼2j−1) | n 2 j × 2 j + 1 = 2 n \frac{n}{2^j} \times 2^{j+1}=2n2jn×2j+1=2n |
| 总复杂度 | n log n 2 ≤ C ≤ n log n − n + 1 \frac{n\log n}{2} \le C \le n\log n -n +12nlogn≤C≤nlogn−n+1 | A = 2 n log n A=2n\log nA=2nlogn |
第一轮(j=1)是合并长度为1的子数组
-> k=1 ->7传递到下一轮第二轮(j=2)是合并长度为2的子数组
-> k=3 ->12和7合并第三轮(j=3)是合并长度为4的子数组
-> k=3 ->127传到下一轮第四轮(j=4)是合并长度为8的子数组
-> k=3 -> 合并all
基数排序radix sort
基数排序是一种基于“位”的排序算法，适用于所有元素均由固定位数（k位）数字组成的列表
设待排序列表 $ L = {a_1, a_2, …, a_n} $，其中：
- n 为列表中元素的个数
- 每个元素 $ a_i $ 恰好由 k 位数字组成，形式为 $ d_kd_{k-1}…d_1 $
（$ d_j $ 表示第 j 位数字，取值范围 0~9）
采用“从低位到高位”的排序顺序，依次对每一位数字进行排序：
- 首先对所有元素的最低位 $ d_1 $ 进行排序，得到初步有序的列表
- 基于上一步的结果，对第 2 位 $ d_2 $ 进行排序
- 重复上述过程，直到对最高位 $ d_k $ 完成排序，最终得到完全有序的列表
时间复杂度:Θ ( n ) \Theta(n)Θ(n)
空间复杂度:Θ ( n ) \Theta(n)Θ(n)
例题: A[1…5] = 7467 3275 6792 9134 1239
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| d1 | 6792 | 9134 | 3275 | 7467 | 1239 | ||||
| d2 | 9134, 1239 | 7467 | 3275 | 6792 | |||||
| d3 | 9134 | 1239, 3275 | 7467 | 6792 | |||||
| d4 | 1239 | 3275 | 6792 | 7467 | 9134 |
前一轮已排好的相对顺序不变:
如( d 2 , 3 ) (d_2,3)(d2,3)的
9134, 1239, 根据d 1 d_1d1的结果, 9134应该在1239前面
快速排序quicksort
快速排序采用分治思想，核心操作是分割：
- 从数组
A[low...high]中选取一个元素作为枢轴，通常选取A[low] - 对数组进行重排，使得：
- 所有小于等于枢轴的元素移到枢轴左侧
- 所有大于枢轴的元素移到枢轴右侧
- 重排后，枢轴会被放置在最终的正确位置
A[w]（low ≤ w ≤ high） - 递归地对枢轴左侧和右侧的子数组重复上述操作，直到整个数组有序
| 变量 | 含义 |
|---|---|
i | 指向小于等于枢轴的元素区域的末尾 |
j | 指向当前正在遍历的元素 |
分割的时间复杂度：Θ ( n ) \Theta(n)Θ(n)（遍历数组一次）
-> 时间复杂度:Θ ( n l o g n ) \Theta(nlogn)Θ(nlogn)
-> 空间复杂度：Θ ( 1 ) \Theta(1)Θ(1)（原地操作，无需额外空间）
例子: 5 3 9 2 7 1 8
| low | high | |||||
|---|---|---|---|---|---|---|
| 5(i) | 3 | 9 | 2 | 7 | 1 | 8 |
| 5 | 3(i)(j) | 9 | 2 | 7 | 1 | 8 |
| 5 | 3(i) | 9(j) | 2 | 7 | 1 | 8 |
| 5 | 3 | 9(i) | 2(j) | 7 | 1 | 8 |
| 5 | 3 | 2(i) | 9(j) | 7 | 1 | 8 |
| 5 | 3 | 2(i) | 9 | 7(j) | 1 | 8 |
| 5 | 3 | 2 | 9(i) | 7 | 1(j) | 8 |
| 5 | 3 | 2 | 1(i) | 7 | 9(j) | 8 |
| 5 | 3 | 2 | 1(i) | 7 | 9 | 8(j) |
| 1 | 3 | 2 | 5 | 7 | 9 | 8 |
往后把1, 3, 2看做一组, 把7, 9, 8看做一组
再去分别做
例子: 4 6 3 1 8 7 2 5
| low | high | ||||||
|---|---|---|---|---|---|---|---|
| 4(i) | 6 | 3 | 1 | 8 | 7 | 2 | 5 |
| 4(i) | 6(j) | 3 | 1 | 8 | 7 | 2 | 5 |
| 4 | 6(i) | 3(j) | 1 | 8 | 7 | 2 | 5 |
| 4 | 3(i) | 6(j) | 1 | 8 | 7 | 2 | 5 |
| 4 | 3 | 6(i) | 1(j) | 8 | 7 | 2 | 5 |
| 4 | 3 | 1(i) | 6(j) | 8 | 7 | 2 | 5 |
| 4 | 3 | 1(i) | 6 | 8(j) | 7 | 2 | 5 |
| 4 | 3 | 1(i) | 6 | 8 | 7(j) | 2 | 5 |
| 4 | 3 | 1 | 6(i) | 8 | 7 | 2(j) | 5 |
| 4 | 3 | 1 | 2(i) | 8 | 7 | 6(j) | 5 |
| 4 | 3 | 1 | 2(i) | 8 | 7 | 6 | 5(j) |
| 2 | 3 | 1 | 4 | 8 | 7 | 6 | 5 |
往后把2, 3, 1看做一组, 把8, 7, 6, 5看做一组
再去分别做
算法总结
| C | A | O OO | Ω \OmegaΩ | Θ \ThetaΘ | |
|---|---|---|---|---|---|
| 选择排序Selection | n ( n − 1 ) 2 \frac{n(n-1)}{2}2n(n−1) | 0 ∼ 3 ( n − 1 ) 0\sim 3(n-1)0∼3(n−1) | n 2 n^2n2 | n 2 n^2n2 | n 2 n^2n2 |
| 插入排序Insertion | n − 1 ∼ n ( n − 1 ) 2 n-1 \sim \frac{n(n-1)}{2}n−1∼2n(n−1) | C + ( n − 1 ) C+(n-1)C+(n−1) | n 2 n^2n2 | n nn | n 2 n^2n2 |
| 自底向上Bottom Up Merge | n log n 2 ∼ n log n − n + 1 \frac{n\log n}{2}\sim n\log n-n+12nlogn∼nlogn−n+1 | 2 n log n 2n\log n2nlogn | n log n n\log nnlogn | n log n n\log nnlogn | n log n n\log nnlogn |
插入排序的Θ ( n 2 ) \Theta(n^2)Θ(n2)计算来自: 平均分析
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| selection sort | Θ ( n 2 ) \Theta(n^2)Θ(n2) | Θ ( 1 ) \Theta(1)Θ(1)（原地排序） |
| insertion sort | Θ ( n 2 ) \Theta(n^2)Θ(n2)(最优Θ ( n ) \Theta(n)Θ(n)) | Θ ( 1 ) \Theta(1)Θ(1)（原地排序） |
| bottom-up merge | Θ ( n log n ) \Theta(n\log n)Θ(nlogn) | Θ ( n ) \Theta(n)Θ(n)（辅助数组） |
| radix sort | Θ ( n ) \Theta(n)Θ(n) | Θ ( n ) \Theta(n)Θ(n)（辅助数组） |
| quick sort | Θ ( n log n ) \Theta(n\log n)Θ(nlogn)(最坏Θ ( n 2 ) \Theta(n^2)Θ(n2)) | Θ ( 1 ) \Theta(1)Θ(1)（原地排序） |
