山东高端网站建设服务商,易湃智能营销平台,网站制作费多少,建设银行官网网站首页2.3-1 归并示意图
问题#xff1a;使用图2-4作为模型#xff0c;说明归并排序再数组 A ( 3 , 41 , 52 , 26 , 38 , 57 , 9 , 49 ) A(3,41,52,26,38,57,9,49) A(3,41,52,26,38,57,9,49)上的操作。图示#xff1a;
tips:#xff1a;有不少在线算法可视化工具#xff08;软…2.3-1 归并示意图
问题使用图2-4作为模型说明归并排序再数组 A ( 3 , 41 , 52 , 26 , 38 , 57 , 9 , 49 ) A(3,41,52,26,38,57,9,49) A(3,41,52,26,38,57,9,49)上的操作。图示
tips:有不少在线算法可视化工具软件但是没有演示上述归并过程的想要完成自定义的效果需要找一个可编程的算法可视化参考链接3。前端使用react框架没事研究下争取做出如上图说是归并过程的可视化效果。
2.3-2 不使用哨兵重写MERGE
重写过程MERGE使之不使用哨兵而是一旦数组L或者R的所有元素均被复制回A就立刻停止然后把另外一个数组的剩余部分复制回A。
伪代码如下 $$
$$
MERGE(A,p,q,r)
1 n1q-r1
2 n2r-q
3 let L[1...n1] and R[1...n2] be new arrays
4 for i 1 to n1
5 L[i] A[pi-1]
6 for j 1 to n2
7 R[j] A[qj]
8 for k p to r
9 if i n1 or j n2
10 break
11 if L[i] R[j]
12 A[k] l[i]
13 i i 1
14 else A[k] R[j]
15 j j 1
16 if i n1 and k r
17 while i n1
18 A[k] L[i]
19 i i 1
20 k k 1
21 if j n2 and k r
22 while j n2
23 A[k] R[j]
24 j j 1
25 k k 1tipsjava代码实现参考链接2
2.3-3 数学归纳法证明归并排序的运行时间
使用数学归纳法证明当n刚好是2的幂时以下递归式的解是 T ( n ) n lg n T(n)n\lg n T(n)nlgn, T ( n ) { 2 若 n 2 2 T ( n 2 ) n , 若 n 2 k , k 1 T(n)\begin{cases} 2\quad 若n2\\ 2T(\frac{n}{2})n,若n2^k,k\gt1 \end{cases} T(n){2若n22T(2n)n,若n2k,k1 证明 当 n 2 1 时 T ( n ) 2 lg 2 2 假设当 n 2 k 时 T ( n ) n lg n k 2 K 成立 当 n 2 k 1 时 , T ( n ) 2 T ( 2 k ) 2 k 1 2 k 2 k 2 k 1 2 k 1 ( k 1 ) n lg n ∴ 当 n 是 2 的幂时 T ( n ) n lg n 是上述递归式的解。 证明\\ 当n2^1时T(n)2\lg 22\\ 假设当n2^k时T(n)n\lg n k2^K 成立\\ 当n2^{k1}时,\\ T(n)2T(2^k)2^{k1}2k2^k2^{k1}\\ 2^{k1}(k1)n\lg n\\ \therefore 当n是2的幂时T(n)n\lg n是上述递归式的解。 证明当n21时T(n)2lg22假设当n2k时T(n)nlgnk2K成立当n2k1时,T(n)2T(2k)2k12k2k2k12k1(k1)nlgn∴当n是2的幂时T(n)nlgn是上述递归式的解。
2.3-4 插入排序的递归版本
我们可以把插入排序表示为如下的一个递归过程。为例排序 A [ 1 ⋯ n ] A[1\cdots n] A[1⋯n]我们递归地排序 A [ 1 ⋯ n − 1 ] , A[1\cdots n-1], A[1⋯n−1],然后把 A [ n ] A[n] A[n]插入已排序的数组 A [ 1 ⋯ n − 1 ] A[1\cdots n-1] A[1⋯n−1]。为了插入排序的这个递归版本的最坏情况运行时间写一个递归式。
插入排序递归版本最坏情况就是数据排列顺序和需求的排序相反。把 A [ n ] A[n] A[n]插入已排序的数组 A [ 1 ⋯ n − 1 ] A[1\cdots n-1] A[1⋯n−1]运行时间为O(n),终止条件是n1此时数组以有序运行时间为O(1),递归式如下 T ( n ) { O ( 1 ) , n 1 T ( n − 1 ) O ( n ) , n 1 T(n)\begin{cases} O(1),n1\\ T(n-1)O(n),n\gt 1 \end{cases} T(n){O(1),n1T(n−1)O(n),n1 T(n)的最坏情况下的运行时间为O(n^2)性能不高这里不做实现。
2.3-5 二分查找算法运行时间
回顾查找问题参见练习2.1-3注意到如果序列A已排好序就可以将排序列中点与v进行比较。根据比较的结果原序列中有一半就可以不用再做进一步的考虑了。二分查找算法重复这个过程每次都讲序列剩余部分规模减半。为二分查找算法写出迭代或递归的伪代码。证明二分查找的最坏情况运行时间为 O ( lg n ) O(\lg n) O(lgn)
分析首先序列已排序二分查找的最坏情况就是要查找的数不在序列中。计算序列中点与目标值比较如果小于大于目标值继续在左半边序列查找否则在右半边序列查找。直至序列长度为2中点必为其中一个此时序列中该元素依然不等于目标值终止。
循环递归式如下 T ( n ) { O ( 1 ) , n 1 T ( n 2 ) O ( 1 ) , n 1 T(n)\begin{cases} O(1),n1\\ T(\frac{n}{2})O(1),n\gt 1 \end{cases} T(n){O(1),n1T(2n)O(1),n1 二分查找运行时间 T ( n ) lg n T(n)\lg n T(n)lgn,实现相对比较简单自行搜索这里不在详述。非递归实现参考下面链接5或者去下面列出的仓库地址中查找。
2.3-6 二分查找能改进插入排序吗
注意到2.1节中的过程INSERTION_SORT的第5~7行的while循环采用一种线性查询来反向扫描已排好序的子数组 A [ 1 ⋯ j − 1 ] A[1\cdots j-1] A[1⋯j−1].我们可以使用二分查找参见练习2.3-5来把插入排序的最坏情况运行时间改进到 O ( n lg n ) O(n\lg n) O(nlgn)吗
**解答**不能。因为在第5~7步包含查找和移动元素查找A[j]合适位置使用二分查找运行时间为 O ( lg j ) O(\lg j) O(lgj)把该元素之后全部向后移动一位运行时间为 O ( j ) O(j) O(j)所以运行时间为 O ( j ) O(j) O(j)那么总的运行时间还是 O ( n 2 ) O(n^2) O(n2)
二、思考题
2-1 在归并排序中对小数组采用插入排序
虽然归并排序的最坏情况运行时间是 O ( n lg n ) O(n\lg n) O(nlgn),而插入排序的最坏情况运行时间是 O ( n 2 ) O(n^2) O(n2)但是插入插入排序中的常量因子可能使得它在n较小时在许多机器上实际运行的更快。因此在归并排序中当子问题变得足够小时采用插入排序来使递归的叶变粗是有意义的。考虑对归并排序的一种修改其中使用插入排序来排序长度为k的 n k \frac{n}{k} kn个子表然后使用标准的合并机制来合并这些子表这里k是一个待定的值。
a. 证明插入排序最坏情况下可以在 O ( n k ) O(nk) O(nk)时间内排序每个长度为k的 n k \frac{n}{k} kn歌子表。
b. 表名在最坏情况下如何在 O [ n lg ( n k ) ] O[n\lg(\frac{n}{k})] O[nlg(kn)]时间内合并这些子表。
c. 假定修改后的算法的最坏情况运行时间为 O [ n k n lg ( n k ) ] O[nkn\lg(\frac{n}{k})] O[nknlg(kn)],要使修改后的算法与标准的归并排序具有相同的运行时间作为n的一个函数记住O记号k的最大值是什么
d. 在实践中我们应该如何选择k a . 插入排序长度为 k 的在最坏情况下运行时间为 O ( k 2 ) ∴ n k 个子表花费时间为 O ( k 2 ⋅ n k ) O ( n k ) b . 合并长度为 k 的 n k 的子表每次合并 2 个子表 需要合并的层数为 lg ( n k ) 1 , 每层需要比较 n 次 ∴ 最坏情况下运行时间为 n lg ( n k ) c . 修改后的算法与标准的归并排序有想听的运行时间即 O ( n k n lg ( n k ) ) O ( n lg n ) 令 k O ( lg n ) , 有 O ( n k n lg ( n k ) ) O ( n k n lg n − n lg k ) O ( 2 n lg n − n lg lg n ) O ( n lg n ) d . 实践中 k 取插入排序比归并排序的最大值。 a. 插入排序长度为k的在最坏情况下运行时间为O(k^2)\\ \therefore \frac{n}{k}个子表 花费时间为O(k^2\cdot \frac{n}{k})O(nk)\\ b. 合并长度为k的\frac{n}{k}的子表每次合并2个子表\\ 需要合并的层数为\lg(\frac{n}{k})1,每层需要比较n次\\ \therefore 最坏情况下运行时间为n\lg(\frac{n}{k})\\ c. 修改后的算法与标准的归并排序有想听的运行时间即\\ O(nkn\lg(\frac{n}{k}))O(n\lg n)\\ 令kO(\lg n),有\\ O(nkn\lg(\frac{n}{k}))O(nkn\lg n-n\lg k)\\ O(2n\lg n-n\lg\lg n) O(n\lg n)\\ d.实践中k取插入排序比归并排序的最大值。 a.插入排序长度为k的在最坏情况下运行时间为O(k2)∴kn个子表花费时间为O(k2⋅kn)O(nk)b.合并长度为k的kn的子表每次合并2个子表需要合并的层数为lg(kn)1,每层需要比较n次∴最坏情况下运行时间为nlg(kn)c.修改后的算法与标准的归并排序有想听的运行时间即O(nknlg(kn))O(nlgn)令kO(lgn),有O(nknlg(kn))O(nknlgn−nlgk)O(2nlgn−nlglgn)O(nlgn)d.实践中k取插入排序比归并排序的最大值。 Java算法实现参考edu.princeton.cs.algs4.MergeX
2-2 冒泡排序的正确性
冒泡排序是一种流行但低效的排序算法它的作用是反复交换相邻的未按次序排序的元素。
BUBBLESORT(A)
1 for i 1 to A.length -1
2 for j A.length downto i1
3 if A[j] A[j-1]
4 exchange A[j] wiht A[j-1]a. 假设 A ′ A^{} A′表示BUBBLESORT(A)的输出。为了证明BUBBLESORT正确我们必须证明它将终止并且有 A ′ [ 1 ] ≤ A ′ [ 2 ] ≤ ⋯ ≤ A ′ [ n ] A^{}[1]\le A^{}[2]\le \cdots\le A^{}[n] A′[1]≤A′[2]≤⋯≤A′[n]
其中 n A . l e n g t h nA.length nA.length。为了证明BUBBLESORT确实完成了排序我们还需要证明什么下面两部分讲证明上述不等式。
b. 为第2~4行的for循环精确地说明一个循环不变式并证明该循环不变式成立。你的证明应该使用本章中给出的循环不变式证明的结果。
c. 使用(b)部分证明的循环不变式的终止条件为第1~4行的for循环说明一个循环不变式该不变式将使你证明不等式。你的证明应该使用本章中给出的循环不变式证明的结构。
d. 冒泡排序的最坏情况下运行时间是多少与插入排序的运行时间相比其性能如何 $$ a.\ 我们需要证明A^{}的元素都来自A且以排序。\ b. \ 循环不变式: 2~4行迭代开始A[j\cdots n]元素为原A[j\cdots n]的元素可能顺序不同\ 且A[j]为其中最小的元素.\ 初始初始子数组元素只有A[n],为当前数组最小元素。\ 维持每次迭代我们比较A[j]与A[j-1]的大小确保A[j-1]为其中的最小值。迭代完成后子数组元素加1且第一个元素为其中最小值。\ 终止终止条件为ji。此时A[i]是子数组A[i\cdots n]中最小元素,其中A[i\cdots n]元素是原数组中A[i\cdots n]。\
c.\ 循环不变式1-4行循环起始子数组A[1\cdots i -1]为A[1\cdots n]中最小的i-1个元素且以排序A[i\cdots n]为A[1\cdots n]中剩余n-i1个元素。\ 初始子数组A[1\cdots i-1]为空。\ 维持根据(b)有执行完内循环之后A[i]为子数组A[i\cdots n]中的最小值。在外循环的起始A[1\cdots i-1]元素比A[i\cdots n]中元素小且以排序。\那么每次外循环执行完成后A[1\cdots i]为比数组A[i1\cdots n]中的元素小且以排序。\ 终止当in.length 时循环终止。此时A[1\cdots n]以全部完成排序。\ d.\ 冒泡排序在最坏情况下运行时间为O(n^2),和插入排序一样。 $$
2-3 霍纳规则的正确性
给定系数 a 0 , a 1 , ⋯ , a n 和 x a_0,a_1,\cdots,a_n和x a0,a1,⋯,an和x的值代码片段
1 y0
2 for in downto 0
3 y a_ixy实现了用于求值多项式 P ( x ) ∑ k 0 n a k x k a 0 x ( a 1 x ( a 2 ⋯ x ( a n − 1 x a n ) ⋯ ) ) P(x)\sum_{k0}^na_kx^ka_0x(a_1x(a_2\cdots x(a_n-1 xa_n)\cdots)) P(x)k0∑nakxka0x(a1x(a2⋯x(an−1xan)⋯)) 的霍纳规则。
a. 借助O记号实现霍纳规则的以上代码片段的运行时间是多少
b. 编写伪代码来实现朴素的多项式求值算法该算法从头开始计算多项式的每个项。该算法的运行时间是多少与霍纳规则相比其性能如果
c. 考虑以下循环不变式
在第2~3for循环每次迭代的开始有 y ∑ k 0 n − ( i 1 ) a k i 1 x k y\sum_{k0}^{n-(i1)}a_{ki1}x^k yk0∑n−(i1)aki1xk 把没有项的合式解释为等于0.遵照本章中给出的循环不变式证明的结构使用该循环不变式来证明终止时有 P ( x ) ∑ k 0 n a k x k P(x)\sum_{k0}^na_kx^k P(x)∑k0nakxk
d. 最后证明上面给出的代码片段将正确地求由系数 a 0 , a 1 , ⋯ , a n a_0,a_1,\cdots,a_n a0,a1,⋯,an刻画的多项式的值。 a 运行时间为 O ( n ) a\\ 运行时间为O(n)\\ a运行时间为O(n)
b. \\
NAIVE-HORNER()y 0for k 0 to ntemp 1for i 1 to ktemp temp * xy y a[k] * temp
运行时间为 O ( n 2 ) O(n^2) O(n2)比霍纳规则慢。 c . 初始 y 0 维持 y a i x ∑ k 0 n − ( i 1 ) a k i 1 x k a i x 0 ∑ k 0 n − ( i 1 ) a k i 1 x k 1 a i x 0 ∑ k 0 n − i a k i x k ∑ k 0 n − i a k i x k 终止此时 i − 1 y ∑ k 0 n a k x k d . 循环的不变量是与给定系数的多项式相等的和。 c. \\ 初始y0\\ 维持ya_ix\sum_{k0}^{n-(i1)}a_{ki1}x^k\\ a_ix^0\sum_{k0}^{n-(i1)}a_{ki1}x^{k1}\\ a_ix^0\sum_{k0}^{n-i}a_{ki}x^k\\ \sum_{k0}^{n-i}a_{ki}x^k\\ 终止此时i-1\\ y\sum_{k0}^na_kx^k\\ d. \\ 循环的不变量是与给定系数的多项式相等的和。 c.初始y0维持yaixk0∑n−(i1)aki1xkaix0k0∑n−(i1)aki1xk1aix0k0∑n−iakixkk0∑n−iakixk终止此时i−1yk0∑nakxkd.循环的不变量是与给定系数的多项式相等的和。
2-4 逆序对
假设 A [ 1 ⋯ n ] A[1\cdots n] A[1⋯n]是一个有n个不同数的数组。若 i j 且 A [ i ] A [ j ] i\lt j且A[i]\gt A[j] ij且A[i]A[j]则对偶 ( i , j ) (i,j) (i,j)称为A的一个逆序对(inversion)。
a. 列出数组(2,3,8,6,1)的5个逆序对。
b. 由集合 [ 1 , 2 , ⋯ , n ] [1,2,\cdots,n] [1,2,⋯,n]中的元素构成的什么数组具有最多的逆序对它有多少逆序对
c. 插入排序的运行时间与输入数组中逆序对的数量之间是什么关系证明你的回答。
d. 给出一个确定在n个元素的任何排列中逆序对数量的算法最坏情况下需要 O ( n k n lg ( n k ) ) O(nk n\lg(\frac{n}{k}) ) O(nknlg(kn))的时间。提示修改归并排序 a . ( 2 , 1 ) , ( 3 , 1 ) , ( 8 , 6 ) , ( 8 , 1 ) , ( 6 , 1 ) b . 数组 [ n , n − 1 , ⋯ , 1 ] 具有对多的逆序对逆序对数为 ( n − 1 ) n 2 c . 插入排序的运行时间是逆序对数的常量倍数。 d a. \\ (2,1),(3,1),(8,6),(8,1),(6,1)\\ b. \\ 数组[n,n-1,\cdots,1]具有对多的逆序对逆序对数为\frac{(n-1)n}{2}\\ c. \\ 插入排序的运行时间是逆序对数的常量倍数。\\ d a.(2,1),(3,1),(8,6),(8,1),(6,1)b.数组[n,n−1,⋯,1]具有对多的逆序对逆序对数为2(n−1)nc.插入排序的运行时间是逆序对数的常量倍数。d 结合2-1,Java代码实现如下所示
package com.gaogzhen.introductiontoalgorithms3.foundation;import edu.princeton.cs.algs4.MergeX;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;import java.util.Comparator;/*** 求解逆序对的数量* 1 逆序对于n个不同的元素先规定各演示之间有一个标准次序例如n个不同的自然数可规定由小到大为标准次序与是在这n个元素的任一排序中当某一对元素的先后次序与标准次序不同时* 就说它构成1个逆序。* 2 逆序数一个排列中所有逆序的总数叫做这个排列的逆序数。* 逆序对数交换次数** author gaogzhen* since 2024/4/7 21:46*/
public class Inversion {private static final int CUTOFF 7; // cutoff to insertion sort// This class should not be instantiated.private Inversion() { }/*** 归并统计交换次数* param src 源子数组* param dst 目的子数组* param lo 起始索引* param mid 中间索引* param hi 结束索引* return*/private static int merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) {// precondition: src[lo .. mid] and src[mid1 .. hi] are sorted subarrays// assert isSorted(src, lo, mid);// assert isSorted(src, mid1, hi);int i lo, j mid1;// 交换次数int inversions 0;for (int k lo; k hi; k) {if (i mid) {// 低位归并完成需要计数dst[k] src[j];} else if (j hi) {// 高位归并完成不需要计数dst[k] src[i];} else if (less(src[j], src[i])) {// 交换次数mid - lo 1 - i 1inversions mid - lo 1 - i 1;dst[k] src[j]; // to ensure stability} else {// 归并低位需要计数dst[k] src[i];}}// postcondition: dst[lo .. hi] is sorted subarray// assert isSorted(dst, lo, hi);return inversions;}/*** 统计逆序对数* param src 源子数组* param dst 目的交换子数组* param lo 低位起始索引* param hi 高位终止索引* return*/private static int sort(Comparable[] src, Comparable[] dst, int lo, int hi) {// if (hi lo) return;if (hi lo CUTOFF) {// 小数组使用插入排序统计逆序对数return insertionSort(dst, lo, hi);}int mid lo (hi - lo) / 2;// 统计左子树组逆序对数int left sort(dst, src, lo, mid);// 统计左子树组逆序对数int right sort(dst, src, mid1, hi);// if (!less(src[mid1], src[mid])) {// for (int i lo; i hi; i) dst[i] src[i];// return;// }// using System.arraycopy() is a bit faster than the above loopif (!less(src[mid1], src[mid])) {// 左子树组和右子树组完成排序好且左侧最大元素小于右侧最小元素无需交换System.arraycopy(src, lo, dst, lo, hi - lo 1);return left right;}// 统计归并左右子数组逆序对数int inversions merge(src, dst, lo, mid, hi);return inversions left right;}/*** 统计数组a的逆序对数* param a 目标数组*/public static int sort(Comparable[] a) {Comparable[] aux a.clone();int inversions sort(aux, a, 0, a.length-1);// assert isSorted(a);return inversions;}/*** 插入排序统计逆序对数* param a 目标数组* param lo 低位起始索引* param hi 高位终止索引* return*/private static int insertionSort(Comparable[] a, int lo, int hi) {int inversions 0;for (int i lo; i hi; i) {for (int j i; j lo less(a[j], a[j-1]); j--) {exch(a, j, j-1);// 交换一次逆序数1inversions;}}return inversions;}/******************************************************************** Utility methods.*******************************************************************//*** 交换元素* param a 目标数组* param i 交换元素索引* param j 另一个交换式索引*/private static void exch(Object[] a, int i, int j) {Object swap a[i];a[i] a[j];a[j] swap;}/*** 第一个元素是否小于第二个元素* param a 第一个元素* param b 第二个元素* return {true} a 小于b ;else {false}*/private static boolean less(Comparable a, Comparable b) {return a.compareTo(b) 0;}/*** 使用比较器比较a是否小于b* param a 元素a* param b 元素吧* param comparator 比较器* return*/private static boolean less(Object a, Object b, Comparator comparator) {return comparator.compare(a, b) 0;}/******************************************************************** Version that takes Comparator as argument.*******************************************************************//*** Rearranges the array in ascending order, using the provided order.** param a the array to be sorted* param comparator the comparator that defines the total order*/public static void sort(Object[] a, Comparator comparator) {Object[] aux a.clone();sort(aux, a, 0, a.length-1, comparator);// assert isSorted(a, comparator);}private static void merge(Object[] src, Object[] dst, int lo, int mid, int hi, Comparator comparator) {// precondition: src[lo .. mid] and src[mid1 .. hi] are sorted subarrays// assert isSorted(src, lo, mid, comparator);// assert isSorted(src, mid1, hi, comparator);int i lo, j mid1;for (int k lo; k hi; k) {if (i mid) dst[k] src[j];else if (j hi) dst[k] src[i];else if (less(src[j], src[i], comparator)) dst[k] src[j];else dst[k] src[i];}// postcondition: dst[lo .. hi] is sorted subarray// assert isSorted(dst, lo, hi, comparator);}private static void sort(Object[] src, Object[] dst, int lo, int hi, Comparator comparator) {// if (hi lo) return;if (hi lo CUTOFF) {insertionSort(dst, lo, hi, comparator);return;}int mid lo (hi - lo) / 2;sort(dst, src, lo, mid, comparator);sort(dst, src, mid1, hi, comparator);// using System.arraycopy() is a bit faster than the above loopif (!less(src[mid1], src[mid], comparator)) {System.arraycopy(src, lo, dst, lo, hi - lo 1);return;}merge(src, dst, lo, mid, hi, comparator);}// sort from a[lo] to a[hi] using insertion sortprivate static int insertionSort(Object[] a, int lo, int hi, Comparator comparator) {int inversions 0;for (int i lo; i hi; i) {for (int j i; j lo less(a[j], a[j-1], comparator); j--) {exch(a, j, j-1);inversions;}}return inversions;}/**************************************************************************** Check if array is sorted - useful for debugging.***************************************************************************/private static boolean isSorted(Comparable[] a) {return isSorted(a, 0, a.length - 1);}private static boolean isSorted(Comparable[] a, int lo, int hi) {for (int i lo 1; i hi; i) {if (less(a[i], a[i-1])) {return false;}}return true;}private static boolean isSorted(Object[] a, Comparator comparator) {return isSorted(a, 0, a.length - 1, comparator);}private static boolean isSorted(Object[] a, int lo, int hi, Comparator comparator) {for (int i lo 1; i hi; i) {if (less(a[i], a[i-1], comparator)) {return false;}}return true;}/*** 输出a数组* param a 数组*/private static void show(Object[] a) {for (int i 0; i a.length; i) {StdOut.println(a[i]);}}/*** 测试*/public static void main(String[] args) {String[] a StdIn.readAllStrings();int inversions Inversion.sort(a);show(a);StdOut.print(逆序对数 inversions);}
}
结语
欢迎小伙伴一起学习交流需要啥工具或者有啥问题随时联系我。 ❓QQ:806797785 ⭐️源代码地址https://gitee.com/gaogzhen/algorithm [1]算法导论(原书第三版)/(美)科尔曼(Cormen, T.H.)等著;殷建平等译 [M].北京:机械工业出版社,2013.1(2021.1重印).p22-24
[2]归并排序-排序-算法第四版[CP/OL]
[3]CLRS Solutions[CP/OL]
[4]Algorithm Visualizer[CP/OL]
[4]入门-基础-算法第4版[CP/OL]
