8.1 排序的基本概念

排序的基本概念.pdf

排序：重新排列表中的元素，使表中元素满足按关键字有序的过程（关键字可以相同）
排序算法的评价指标
- 时间复杂度、空间复杂度；
- 稳定性：关键字相同的元素在排序之后相对位置不变，称为稳定的；（选择题考查）
  
  Q：稳定的排序算法一定比不稳定的好？
  
  A：不一定，要看实际需求；

排序算法的分类

内部排序：数据都在内存——关注如何使时间、空间复杂度更低；
外部排序：数据太多，无法全部放入内存——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少；

各类排序演示

补充：对任意 $n$ 个关键字进行基于比较的排序，至少需要进行 $⌈ lo g_{2} (n!) ⌉$ 次关键字之间的两两比较考前记一记

8.1.2 本节习题精选

选择题：题目、答案

8.2 插入排序

算法思想：每次将一个待排序的记录按其关键字大小，插入（依次对比、移动）到前面已经排好序的子序列中，直到全部记录插入完成

插入排序.pdf

8.2.1 直接插入排序

插入排序演示

不带“哨兵”

//个人理解：如果A[i]比A[i-1]小，则从A[i-1]开始，从后往前遍历，凡是比A[i]小的，后移一位，从而找到A[i]应该在的位置，再插入A[i]
 
void InsertSort(int A[], int n){	//A中共n个数据元素
	int i, j, temp;
	for(i=1; i<n; i++){//A[0]不需要排
		if(A[i] < A[i-1]){		//A[i]关键字小于前驱
			temp = A[i];
			for(j=i-1; j>=0 && A[j]>temp; --j)	//检查前面所有已经排好序的元素
				A[j+1] = A[j];		//所有大于temp的元素都向后挪
			A[j+1] = temp;		//复制到插入位置
			//上一步中，因为A[j]<temp或者，所以跳出循环，所以这里是j+1
		}
	}
}

带“哨兵” ，优点：不用每轮循环都判断 $j ⩾ 0$

//个人理解：带哨兵方式把此轮要排序的值A[i]赋给A[0]，所以即便A[i]是目前最小的元素，它最多前移到第一位，不会出现越界
 
void InsertSort(int A[], int n){	//A中从1开始存储，0放哨兵
	int i, j;
	for(i=2; i<n; i++){		//依次将A[2]~A[n]插入到前面已排序序列
		//A[i]小于前面的数
		if(A[i] < A[i-1]){
			A[0] = A[i];	//复制为哨兵
			for(j=i-1; A[0]<A[j]; --j)	//从后往前，把大的往后放
				A[j+1] = A[j];
			A[j+1] = A[0];	//复制到插入位置
		}//if
	}//for
}

空间复杂度： $O (1)$
时间复杂度：主要来自于对比关键字、移动关键字，若有 $n$ 个元素，则需要 $n - 1$ 次处理
- 最好情况：原本为有序—— $O (n)$
- 最差情况：原本为逆序—— $O (n^{2})$
- 平均情况： $O (n^{2})$
算法稳定性：稳定

对链表进行插入排序

移动元素的次数变少了，因为只需要修改指针，不需要依次右移；
但是关键字对比的次数依然是 $O (n^{2})$ 数量级，因此整体看来时间复杂度仍然是 $O (n^{2})$

8.2.2 折半插入排序

思路：先用折半查找找到应该插入的位置，再移动元素；

当查找到和插入元素关键字一样的元素时，为了保证稳定性，应该继续在这个元素的右半部分继续查找以确认位置；即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置
当 low > high 时，折半查找停止，应将 $[l o w, i - 1]$ 内的元素全部右移，并将A[0]复制到low所指的位置

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,0) (55){$55$};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\def\myNum{$20$,$30$,$40$,$50$,$60_{1}$,$70$,$80$,$55$,$60_{2}$,$90$,$10$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\Large, draw=none, red] at(8,-1.5)(i){i};
		\draw[-latex, red] (i) -- (8);
		\node[font=\Large, draw=none] at(5,-1.5)(low){low};
		\draw[-latex] (low) -- (5);
		\node[font=\Large, draw=none] at(4,-1.5)(high){high};
		\draw[-latex] (high) -- (4);
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-5)(val-6)(val-7), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

//个人理解：利用折半查找找到应该插入的位置，再统一移动元素
//与直接相比，简化的只是查找过程
 
//折半插入排序（带哨兵）
void InsertSort(int A[], int n){
	int i, j, low, high, mid;
	for(i=2; i<=n ;i++){
		A[0] = A[i];			//将A[i]暂存到A[0]
		low = 1; high = i-1;	//折半查找的范围
		while(low <= high){		//折半查找（默认递增）
			mid = (low + high)/2;	//取中间点（向下取整）
			if(A[mid]>A[0])		//查找左半子表
				high = mid - 1;
			else				//查找右半子表【注意】
				low = mid + 1;
		}
		for(j=i-1; j>low; --j)
			A[j+1] = A[j];	//（前面的元素是有序的）统一后移元素，空出插入位置
		A[high+1] = A[0]
	}
}

与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变，时间复杂度仍然是 $O (n^{2})$

8.2.3 希尔排序

基本有序的前提下，直接插入排序有很好的效率

希尔排序：先追求表中元素部分有序，再逐渐逼近全局有序

希尔排序演示

希尔排序.pdf

希尔排序(Shell Sort)思路：先追求表中元素的部分有序，再逐渐逼近全局有序

现将待排序表分割成若干形如 $L [i, i + d, i + 2 d, \dots, i + k d]$ 的特殊子表，对各个子表分别进行直接插入排序。缩小增量 $d$ ，（建议每次增量缩小一半）重复上述过程，直到 $d = 1$ 为止
更适用于基本有序的排序表和数据量不大的排序表，仅适用于线性表为顺序存储的情况

例：下面进行第1轮排序， $d = 4$ ，待排序表分为4个子表

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1,2,3,4}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$49_{1}$,$38$,$65$,$97$,$76$,$13$,$27$,$49_{2}$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 4)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
   \end{tikzpicture}
\end{document}

再对各个子表进行排序，如下所示：

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1,2,3,4}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$49_{1}$,$13$,$27$,$49_{2}$,$76$,$38$,$65$,$97$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 4)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
 
   \end{tikzpicture}
\end{document}

第2轮排序中， $d = 2$ ，待排序表分为两个子表

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1,2}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$49_{1}$,$13$,$27$,$49_{2}$,$76$,$38$,$65$,$97$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 2)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
 
   \end{tikzpicture}
\end{document}

再对各个子表进行排序，如下所示：

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1,2}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$27$,$13$,$49_{1}$,$38$,$65$,$49_{2}$,$76$,$97$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 2)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
 
   \end{tikzpicture}
\end{document}

第3轮中， $d = 1$ ，相当于对所有元素进行插入排序

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$27$,$13$,$49_{1}$,$38$,$65$,$49_{2}$,$76$,$97$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 1)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
 
   \end{tikzpicture}
\end{document}

排序后如下所示

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=gray!20] at (0,0) (val-0){};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\foreach \i in{1}{
			\node[draw=none, fill=gray!10, minimum width=50em, minimum height=3.5em] at(4,-\i){};
		}
		\def\myNum{$13$,$27$,$38$,$49_{1}$,$49_{2}$,$65$,$76$,$97$}
		\foreach \num [count=\idx] in \myNum {
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
			\pgfmathtruncatemacro{\j}{Mod(\idx-1, 1)};
			\node[fill=gray!20] at (\idx,-\j-1) (valchild-\idx){\num};
		}
 
   \end{tikzpicture}
\end{document}

//希尔排序
//个人理解：每次处理一个元素，对该元素在子表内进行插入排序。也就是说，实际上轮流处理各个子表的第i/d个元素
void ShellSort(ElemType A[], int n){
	int d, i, j;
	//A[0]为暂存单元，当j<=0时，说明插入位置已到
	for(d=n/2; d>=1; d=d/2){		//步长递减（看题目要求，一般是1/2）
		for(i=d+1; i<=n; ++i){	//i=d+1，按照直接插入排序，从子表的第二个元素开始
			//++i，每次处理一个元素，而不是一个子表
			if(A[i] < A[i-d]){
				A[0]=A[i];
				for(j=i-d; j>0&&A[0]<A[j]; j-=d)
					A[j+d] = A[j];//（前面的元素是有序的）后移元素，查找插入的位置
				A[j+d] = A[0];	//插入
			}//if
		}//for
	}//for
}

算法效率分析

空间效率：空间复杂度 $= O (1)$
时间效率：最坏情况下时间复杂度 $= O (n^{2})$ ，当 $n$ 在某个范围内时，时间复杂度可达到 $O (n^{1.3})$
稳定性：希尔排序是一种不稳定的排序方法（如： $65, 4 9_{1}, 4 9_{2}$ ，令 $d = 2$ ，排序后得到： $4 9_{2}, 4 9_{1}, 65$ ）

8.2.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

8.3 交换排序

基于“交换”的排序：根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置；

8.3.1 冒泡排序

冒泡排序演示

冒泡排序.pdf

算法思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），交换它们，直到序列比较完毕，称这样过程为一趟冒泡排序（前面已经确定最终位置的元素不需再对比）
第一趟排序使关键字值最小的一个元素“冒”到最前面（其最终位置）—— 每趟冒泡的结果是把序列中最小元素放到序列的最终位置，这样最多做 $n - 1$ 趟冒泡就能把所有元素排好序；
为保证稳定性，关键字相同的元素不交换；
若某一趟排序没有发生交换，则说明此时已经整体有序，算法可提前结束
冒泡排序可以用于链表、顺序表

//个人理解：从最后一个元素往前依次进行对比，如果比这个元素大就交换，直到序列中最小元素交换到了最前面
 
//交换
void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
 
//冒泡排序
void BubbleSort(int A[], int n){	//从0开始存放
	for(int i=0; i<n-1; i++){	//前i个是已经排好的序列
		bool flag = false;		// 表示本趟冒泡是否发生交换的标志
		for(int j=n-1; j>i; j--)	//一趟冒泡过程
			if(A[j-1]>A[j]){		//若为逆序
				swap(A[j-1], A[j]);	//交换
				flag=true;
			}
		if(flag == false)
			return;       //本趟遍历后没有发生交换，说明表已经有序，可以结束算法
	}
}

算法效率分析

空间复杂度： $O (1)$
时间复杂度
- 最好情况（有序）：只需要一趟排序，比较次数 $= n - 1$ ，交换次数 $= 0$ ，最好时间复杂度 $= O (n)$
- 最坏情况（逆序）：比较次数 $= (n - 1) + (n - 2) + \dots + 1 = \frac{n ( n - 1 )}{2} =$ 交换次数，最坏时间复杂度 $= O (n^{2})$
- 平均情况： $O (n^{2})$
稳定性：冒泡排序是一种稳定的算法

8.3.2 快速排序

快速排序使所有内部排序算法中平均性能最优的排序算法；

快速排序演示

快速排序.pdf

算法思想：在待排序表 L[1...n] 中任取一个元素 pivot 作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为独立的两个部分 L[1...k-1] 和 L[k+1...n] ，使得两个部分的元素分别小于等于 pivot 和大于等于 pivot ，则 pivot 放在其最终位置 L(k) 上，这个过程称为一次划分。

然后分别递归地对两个子表重复上述过程，直至每个部分内只有一个元素为止，即所有元素放在其最终位置上
每一趟排序都可使一个中间元素确定其最终位置

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\def\myNum{$49_{1}$,$38$,$65$,$97$,$76$,$13$,$27$,$49_{2}$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\Large, draw=none] at(0,-1.5)(low){low};
		\draw[-latex] (low) -- (0);
		\node[font=\Large, draw=none] at(7,-1.5)(high){high};
		\draw[-latex] (high) -- (7);
   \end{tikzpicture}
\end{document}

取 $4 9_{1}$ 作为枢轴，high指针向前遍历，直到high<pivot，再交换high所指元素到low的位置，low指针开始向后遍历。

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,1) (pivot){$49_{1}$};
		\def\myNum{,$38$,$65$,$97$,$76$,$13$,$27$,$49_{2}$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\Large, draw=none] at(0,-1.5)(low){low};
		\draw[-latex] (low) -- (0);
		\node[font=\Large, red, draw=none] at(6,-1.5)(high){high};
		\draw[-latex, red] (high) -- (6);
 
		\draw[-latex] (val-6.north) [out=120, in=60]to (val-0.north);
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-7), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

low指针不断向后遍历，直到low>pivot，再交换low所指元素到high的位置，high指针开始向前遍历

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,1) (pivot){$49_{1}$};
		\def\myNum{$27$,$38$,$65$,$97$,$76$,$13$, ,$49_{2}$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\Large, red, draw=none, red] at(2,-1.5)(low){low};
		\draw[-latex, red] (low) -- (2);
		\node[font=\Large, draw=none] at(6,-1.5)(high){high};
		\draw[-latex] (high) -- (6);
 
		\draw[-latex] (val-2.north) [out=60, in=120]to (val-6.north);
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-7), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

再进行若干次交换后，low与high指向同一位置，找到pivot最终所在位置

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,1) (pivot){$49_{1}$};
		\def\myNum{$27$,$38$,$13$, ,$76$,$97$,$65$,$49_{2}$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\node[font=\large, draw=none, xshift=-1em] at(3,-1.5)(low){low};
		\draw[-latex] (low) -- ([xshift=-0.5em]3.south);
		\node[font=\large, draw=none, xshift=1em] at(3,-1.5)(high){high};
		\draw[-latex] (high) -- ([xshift=0.5em]3.south);
 
		\draw[-latex](pivot) [out=0, in=90] to (val-3);
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-7), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

排序表分为两个部分，再分别对两个部分进行排序

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\def\myNum{$27$,$38$,$13$, ,$76$,$97$,$65$,$49_{2}$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
		\node[fill=green!20] at (3,0) (pivot){$49_{1}$};
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-2), rectangle, rounded corners, drop shadow={gray!10}] {};
			\node [draw, ultra thick,dashed, fit=(val-4)(val-7), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

快速排序算法题

//个人理解：取第一个元素作为枢轴（顺便空出一个位置来，且空位置由low指针指向），扫描到大于枢轴的元素，就把这个元素移动到空位置，然后开始扫描小于枢轴的元素（空位置由high指针指向）。循环往复
 
//用随机一个元素将待排序序列划分为左右两个部分
int Partition(int A[], int low, int high){
	把数组A[]中随机一个元素与A[low]交换;//快速排序的优化
	int pivot = A[low];          //用第一个元素作为枢轴
	while(low<high){
		while(low<high && A[high]>=pivot)
			high--;			//high所指元素大于等于枢轴，high左移
		A[low] = A[high];	//high所指元素小于枢轴，交换到左侧
		while(low<high && A[low]<=pivot)
			low++;			//low所指元素小于等于枢轴，low右移
		A[high] = A[low];   //low所指元素大于枢轴，交换到右侧
	}
	A[low] = pivot;	//枢轴元素存放到最终位置
	return low;		//返回存放枢轴的最终位置
}
 
//快速排序
void QuickSort(int A[], int low, int high){
	if(low < high){	//递归跳出条件
		int pivotposition = Partition(A, low, high);//划分
		QuickSort（A, low, pivotposition - 1);		//划分左子表
		QuickSort（A, pivotposition + 1, high);		//划分右子表
	}
}

算法效率分析

每一层的 QuickSort 只需要处理剩余的待排序元素，时间复杂度不超过 $O (n)$
把 $n$ 个元素组织成二叉树，二叉树的层数就是递归调用的层数， $n$ 个结点的二叉树最小高度 $= ⌊ lo g_{2} n ⌋ + 1$ , 最大高度 $= n$
- 若每一次选中的“枢轴”可以将待排序序列划分为“均匀”的两个部分，则递归深度最小，算法效率最高；
- 若初始序列本就有序或者逆序，则快速排序的性能最差；
时间复杂度 $= O (n \times 递归层数)$
- 最好时间复杂度 $= O (n lo g_{2} n)$ ：每次选的枢轴元素都能将序列划分成均匀的两部分；
- 最坏时间复杂度 $= O (n^{2})$ ：序列本就有序或逆序，此时时间、空间复杂度最高；
- 平均时间复杂度 $= O (n lo g_{2} n)$ （接近最好而不是最坏）
空间复杂度 $= O (递归层数)$
- 最好 $= O (lo g_{2} n)$
- 最坏 $= O (n)$
稳定性：不稳定（如： $2_{1}, 2_{2}, 1$ ，取 $2_{1}$ 为pivot，排序后得到： $1, 2_{2}, 2_{1}$ ）

快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素

选头、中、尾三个位置的元素，取中间值作为枢轴元素；
随机选一个元素作为枢轴元素

判定给定序列是否可以是经过 $n$ 趟快速排序的序列

至少有 $n$ 个元素在其最终位置上
每个子序列经过一次排序都会有一个元素在其最终位置上（可能第一次1个序列，第2次2个序列，第3次4个序列……）。如2019年第10题D选项，5,2,12,28,16,32,72,60 就不可能是经过两趟排序得到的结果

8.3.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

8.4 选择排序

选择排序思想：每一趟在待排序元素中选取关键字最小（或最大）的元素，交换到最终所在位置；

8.4.1 简单选择排序

简单选择排序演示

简单选择排序.pdf

$n$ 个元素的简单选择排序需要 $n - 1$ 趟处理，最后剩下的一个不需要处理

//个人理解：循环一轮找到最小的元素，然后把最小的元素和此轮排序的元素交换
 
//交换
void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
 
void SelectSort(int A[], int n){	//A从0开始
	for(int i=0; i<n-1; i++){	//一共进行n-1趟，i指向待排序序列中第一个元素
		int min = i;		//记录最小元素位置
		for(int j=i+1; j<n; j++)//在A[i...n-1]中选择最小的元素
			if(A[j]<A[min])
				min = j;	//更新最小元素位置
		if(min!=i)
			swap(A[i], A[min]);	//交换
	}
}

算法效率分析

空间复杂度： $O (1)$
时间复杂度： $O (n^{2})$ 。无论有序、逆序、乱序，都需要 $n - 1$ 次的处理，总共需要对比关键字 $(n - 1) + (n - 2) + \dots + 1 = n (n - 2) /2$ 次，元素交换次数 $< n - 1$ ；时间复杂度
稳定性：不稳定（如： $2_{1}, 2_{2}, 1$ ，排序后得到： $1, 2_{2}, 2_{1}$ ）
适用性：既可以用于顺序表，也可以用于链表

8.4.2 堆排序

堆演示

堆排序演示

堆排序.pdf

堆：若 $n$ 个关键字序列 L[1 ... n] 满足下面某一条性质，则称为堆(Heap)

若满足： $L (i) ⩾ L (2 i)$ 且 $L (i) ⩾ L (2 i + 1)$ $(1 ⩽ i ⩽ n /2)$ ——大根堆，即完全二叉树中，根 ≥ 左右
若满足： $L (i) ⩽ L (2 i)$ 且 $L (i) ⩽ L (2 i + 1)$ $(1 ⩽ i ⩽ n /2)$ ——小根堆，即完全二叉树中，根 ≤ 左右

可理解为顺序存储的二叉树，注意

可以将堆视为一棵完全二叉树 (✔)

可以将堆视为一棵二叉排序树 (✖)

基本思路：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列，堆顶元素的关键字最大或最小（以下以大根堆为例）

将给定初始序列（ $n$ 个元素），建立初始大根堆：把所有非终端结点从后往前都检查一遍，是否满足大根堆的要求—— $根 ⩾ 左、右$ ，若不满足，则将当前结点与更大的孩子互换(实际做题中，可以每次从下往上从后往前调整一层)
更小的元素“下坠”后，可能导致下一层的子树不符合大根堆的要求，则从下坠的元素继续调整，小元素不断“下坠”，直到满足大根堆要求。再回到原位置继续从后往前检查
基于大根堆进行排序：每一趟将堆顶元素加入有序子序列中，堆顶元素与待排序序列中最后一个元素交换后，即最大元素换到末尾，之后该位置就不用改变，即移出完全二叉树(len=len-1)，把剩下的待排序元素序列再调整为大根堆；
剩下最后一个元素则不需要再调整；

基于大根堆的堆排序得到递增序列，基于小根堆的堆排序得到递减序列

0	1	2	3	4	5	6	7	8
	53	17	78	09	45	65	87	32

建堆，堆的初始结构如下：

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=3em},
	level 2/.style={sibling distance=8em/2, level distance=3em},
	level 3/.style={sibling distance=8em/2, level distance=3em},
	]
	\node (53){53}
		child {node (17){17}
			child {node (9){9}
				child {node[xshift=-4em] (32){32}}
			}
			child {node (45){45}}
		}
        child {node (78){78}
			child {node (65){65}}
			child {node (87){87}}
		};
	\end{tikzpicture}
\end{document}

依次调整分支结点9、78、17、53，其中调整以结点53的过程如下：

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=6em},
	level 2/.style={sibling distance=8em/2, level distance=6em},
	level 3/.style={sibling distance=8em/2, level distance=6em},
	]
	\node[fill=red!20] (53){53}
		child {node (45){45}
			child {node (32){32}
				child {node[xshift=-2em] (9){9}}
			}
			child {node (17){17}}
		}
        child {node (87){87}
			child {node (65){65}}
			child {node (78){78}}
		};
 
	\node[font=\LARGE, draw=none, fill=none] [above=of 53, yshift=-3em] {$A[0]=53$};
	\node[font=\LARGE, draw=none, fill=none] [right=of 53] (k){$k$};
	\draw[-latex] (k) -- (53);
	\node[font=\LARGE, draw=none, fill=none] [right=of 45] (i){$i$};
	\draw[-latex] (i) -- (45);
	\node[font=\LARGE, draw=none, fill=none] [right=of 87] (i+1){$i+1$};
	\draw[-latex] (i+1) -- (87);
	\end{tikzpicture}
 
	\begin{tikzpicture}[scale=1, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=6em},
	level 2/.style={sibling distance=8em/2, level distance=6em},
	level 3/.style={sibling distance=8em/2, level distance=6em},
	]
	\node  (87){87}
		child {node (45){45}
			child {node (32){32}
				child {node[xshift=-2em] (9){9}}
			}
			child {node (17){17}}
		}
        child {node (53){ }
			child {node (65){65}}
			child {node (78){78}}
		};
 
	\node[font=\LARGE, draw=none, fill=none] [above=of 87, yshift=-3em] {$A[0]=53$};
	\node[font=\LARGE, draw=none, fill=none] [right=of 53] (k){$k$};
	\draw[-latex] (k) -- (53);
	\node[font=\LARGE, draw=none, fill=none] [below=of 65] (i){$i$};
	\draw[-latex] (i) -- (65);
	\node[font=\LARGE, draw=none, fill=none] [below=of 78] (i+1){$i+1$};
	\draw[-latex] (i+1) -- (78);
	\end{tikzpicture}
 
	\begin{tikzpicture}[scale=1, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=6em},
	level 2/.style={sibling distance=8em/2, level distance=6em},
	level 3/.style={sibling distance=8em/2, level distance=6em},
	]
	\node (87){87}
		child {node (45){45}
			child {node (32){32}
				child {node[xshift=-2em] (9){9}}
			}
			child {node (17){17}}
		}
        child {node (78){78}
			child {node (65){65}}
			child {node (53){53}}
		};
 
	\node[font=\LARGE, draw=none, fill=none] [above=of 87, yshift=-3em] {$A[0]=53$};
	\node[font=\LARGE, draw=none, fill=none] [right=of 53] (k){$k$};
	\draw[-latex] (k) -- (53);
	\end{tikzpicture}
 
\end{document}

将堆顶元素87与最后一个元素交换，并调整剩余元素为大根堆

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1.5, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[fill=green!20] at(0,0) {87}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em] {9}}
			}
			child {node {17}}
		}
        child {node {78}
			child {node {65}}
			child {node {53}}
		};
	\node[fill=red!20] at(6,0) {9}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em, fill=green!20] {87}}
			}
			child {node {17}}
		}
        child {node {78}
			child {node {65}}
			child {node {53}}
		};
	\node at(12,0) {78}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em, fill=green!20] {87}}
			}
			child {node {17}}
		}
        child {node {65}
			child {node[fill=red!20] {9}}
			child {node {53}}
		};
	\end{tikzpicture}
\end{document}

将堆顶元素78与最后y一个元素交换，并调整剩余元素为大根堆

\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=1.5, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/2, level distance=4em},
	]
	\node[fill=green!20] at(0,0) {78}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em, fill=green!20] {87}}
			}
			child {node {17}}
		}
		child {node {65}
			child {node {9}}
			child {node {53}}
		};
	\node[fill=red!20] at(6,0) {53}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em, fill=green!20] {87}}
			}
			child {node {17}}
		}
        child {node {65}
			child {node {9}}
			child {node[fill=green!20] {78}}
		};
	\node at(12,0) {65}
		child {node {45}
			child {node {32}
				child {node[xshift=-2em, fill=green!20] {87}}
			}
			child {node {17}}
		}
        child {node[fill=red!20] {53}
			child {node {9}}
			child {node[fill=green!20] {78}}
		};
	\end{tikzpicture}
\end{document}

不断调整后，最终的堆如下，得到递增序列：

\begin{document}
\begin{tikzpicture}[scale=1.5, line width=1.5pt,
	every node/.style={draw=black, circle, very thick, fill=green!20, font =\huge, minimum size=3em},
	level 1/.style={sibling distance=8em/1, level distance=4em},
	level 2/.style={sibling distance=8em/2, level distance=4em},
	level 3/.style={sibling distance=8em/2, level distance=4em},
	]
	\node {9}
		child {node {17}
			child {node {45}
				child {node[xshift=-2em] {87}}
			}
			child {node {53}}
		}
        child {node {32}
			child {node {65}}
			child {node {78}}
		};
	\end{tikzpicture}
\end{document}

//个人理解
	//①建堆——从后往前调整每一个分支结点
	//②利用堆进行排序——把最后一个结点与根结点互换，再调整根结点
	//调整：HeadAdjust()，把树从当前结点开始往下检查，来满足大根堆要求
 
//对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
	for(int i=len/2; i>0; i--)	//从后往前调整所有非终端结点
		HeadAdjust(A, i, len);
}
 
//将以k为根的子树调整为大根堆，从最底层的分支结点开始调整
void HeadAdjust(int A[], int k, int len){
	A[0] = A[k];	//A[0]暂存子树的根结点
	for(int i=2*k; i<=len; i*=2){	// 沿key较大的子结点向下筛选
							// i为当前所选根结点的左孩子
							// i*=2是为了判断调整后再下一层是否满足大根堆
		if(i<len && A[i]<A[i+1])	// 选出两个孩子结点中较大者
			// i<len 保证右孩子存在
			i++;
		if(A[0] >= A[i])
			break;			//当前根结点根≥左右，筛选结束
		else{
			A[k] = A[i];	//子结点A[i]大于父结点，将值赋值给父结点
			k=i;			//k标记根结点“下坠”后的最终位置
		}
	}
	A[k] = A[0];//把被筛选的根结点的值放入最终位置
}
 
//交换
void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}
 
//基于大根堆进行排序
void HeapSort(int A[], int len){
	BuildMaxHeap(A, len);	//初始建堆
	for(int i=len; i>1; i--){		//i=len指向当前排序元素的最后一个元素（最小值）
		//n-1趟的交换和建堆过程
		swap(A[i], A[1]);		//堆顶元素和堆底元素交换
		HeadAdjust(A,1,i-1);	//把剩余的待排序元素整理成堆
	}
}

算法效率分析

一个结点每下坠一层，最多只需对比关键字2次（找出较大的子结点，父结点与子结点对比）。若树高为 $h$ ，某结点在第 $i$ 层，则将这个结点向下调整最多只需要下坠 $h - i$ 层，关键字对比次数不超过 $2 (h - i)$ ，而 $n$ 个结点的完全二叉树树高 $h = ⌊ lo g_{2} n ⌋ + 1$
第 $i$ 层最多有 $2^{i - 1}$ 个结点，而只有第 $1 \sim (h - 1)$ 层的结点才有可能需要下坠调整，故关键字对比次数 $⩽ 4 n$
建堆时间复杂度 $= O (n)$ ，排序时间复杂度 $= O (n lo g_{2} n)$ ，总的时间复杂度 $= O (n lo g_{2} n)$
空间复杂度 $= O (1)$
稳定性：不稳定（如： $1, 2_{1}, 2_{2}$ ，大根堆排序后得到： $1, 2_{2}, 2_{1}$ ）

堆的插入和删除

堆的插入删除.pdf

插入元素：对于小根堆，先将新元素直接放在表尾，再与父结点对比，若新元素比父结点更小，则将两则互换。新元素就这样一路上升，直到无法继续上升为止
删除元素：对于小根堆，将被删除的元素用堆底元素替代，然后让该元素不断下坠，直到无法继续下坠为支持

8.4.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

8.5 归并排序和基数排序

8.5.1 归并排序

归并排序演示

归并排序.pdf

归并（Merge）：把两个或多个已经有序的序列合并成一个；
$k$ 路归并：每选出一个元素，每选出一个元素需要对比关键字 $k - 1$ 次；
外部排序通常采用归并排序；内部排序一般采用2路归并，把相邻有序子序列两两进行归并
2路归并排序：假定待排序表有 $n$ 个记录，则可将其视为 $n$ 个有序的子表，每个子表的长度为1，然后两两归并，得到 $⌈ n /2 ⌉$ 个长度为2或1的有序表；继续两两归并……如此重复，直到合并成一个长度为 $n$ 的有序表为止

初始序列

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,0) (55){$55$};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\def\myNum{$49$,$38$,$65$,$97$,$76$,$13$,$27$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\begin{scope}[on background layer]
		\foreach \i in{0,1,...,6}{
			\node [draw, ultra thick,dashed, fit=(val-\i), rectangle, rounded corners, drop shadow={gray!10}] {};
		}
		\end{scope}
   \end{tikzpicture}
\end{document}

一趟归并后：

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,0) (55){$55$};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\def\myNum{$38$,$49$,$65$,$97$,$13$,$76$,$27$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-1), rectangle, rounded corners, drop shadow={gray!10}] {};
			\node [draw, ultra thick,dashed, fit=(val-2)(val-3), rectangle, rounded corners, drop shadow={gray!10}] {};
			\node [draw, ultra thick,dashed, fit=(val-4)(val-5), rectangle, rounded corners, drop shadow={gray!10}] {};
			\node [draw, ultra thick,dashed, fit=(val-6), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

两趟归并后：

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,0) (55){$55$};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\def\myNum{$38$,$49$,$65$,$97$,$13$,$27$,$76$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-1)(val-2)(val-3), rectangle, rounded corners, drop shadow={gray!10}] {};
			\node [draw, ultra thick,dashed, fit=(val-4)(val-5)(val-6), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

三趟归并后：

\usetikzlibrary{fit, backgrounds, shadows}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, rectangle, very thick, font =\huge, minimum width=3em, minimum height=3em},
	]
		\node[fill=green!20] at (0,0) (55){$55$};
		\node[font=\large, draw=none] at(0,-0.5) (0){0};
		\def\myNum{$13$,$27$,$38$,$49$,$65$,$76$,$97$}
		\foreach \num [count=\i] in \myNum {
			\pgfmathtruncatemacro{\idx}{\i-1};
			\node[fill=gray!20] at (\idx,0) (val-\idx){\num};
			\node[font=\large, draw=none] at(\idx,-0.5) (\idx){\idx};
		}
 
		\begin{scope}[on background layer]
			\node [draw, ultra thick,dashed, fit=(val-0)(val-1)(val-2)(val-3)(val-4)(val-5)(val-6), rectangle, rounded corners, drop shadow={gray!10}] {};
		\end{scope}
   \end{tikzpicture}
\end{document}

//个人理解：利用递归把整个数组拆分成若干个小块，让小块有序，再逐渐合并成整个数组
//归并：把两个部分中的最小元素进行对比，较小者加入到有序表。循环进行，直到某个部分无剩余元素，就把另一个部分中的剩余元素依次添加到有序表中
 
//创建辅助数组B
int *B=(int *)malloc(n*sizeof(int));	//辅助数组B
 
//归并操作
//A[low,...,mid]，A[mid+1,...,high] 各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
	int i, j, k;
	for(k=low; k<=high; k++)	//将A中所有元素复制到B中
		B[k] = A[k];
	for(i=low,j=mid+1,k=i; i<=mid&&j<=high; k++){
		if(B[i]<=B[j])	//将较小值复制到A中，为保证稳定性，两个元素相等时优先使用靠前的那个
			A[k]=B[i++];
		else
			A[k]=B[j++];
	}//for
 
	//没有归并完的部分复制到尾部（while只会执行一个）
	while(i<=mid)
        A[k++]=B[i++];	//若第一个表未检测完，复制
	while(j<=high)
        A[k++]=B[j++];	//若第二个表未检测完，复制
}
 
//递归操作
void MergeSort(int A[], int low, int high){
	if(low<high){
		int mid = (low+high)/2;		//从中间划分
		MergeSort(A, low, mid);		//对左半部分归并排序
		MergeSort(A, mid+1, high);	//对右半部分归并排序
		Merge(A,low,mid,high);		//归并
	}//if
}

算法效率分析

归并排序的比较次数与序列的初始状态无关；
2路归并的“归并树”形态上是一棵倒立的二叉树，树高 $h$ ，归并排序趟数 $m = h - 1$ ，第 $h$ 层最多 $2^{(h - 1)}$ 个结点，则满足 $n ⩽ 2^{(h - 1)}$ ，即 $h - 1 = ⌈ lo g_{2} n ⌉$ ；所以n个元素进行2路归并排序，归并趟数 $m = ⌈ lo g_{2} n ⌉$
每趟归并时间复杂度为 $O (n)$ , 算法总时间复杂度为 $O (n lo g_{2} n)$
空间复杂度： $O (n)$ ，辅助数组+递归；归并排序算法可视为本章占用辅助空间最多的排序算法
稳定性：归并排序是稳定的
对于 $N$ 个元素进行 $k$ 路归并排序，排序的趟数 $m$ 满足 $k^{m} = N$ ，所以 $m = ⌈ lo g_{k} N ⌉$

8.5.2 基数排序

基数排序演示

基数排序.pdf

基数排序(Radix Sort)算法思想：假设长度为 n 的线性表中每个结点 $a_{j}$ 的关键字由 $d$ 元组 $(k_{j}^{d - 1}, k_{j}^{d - 2}, \dots, k_{j}^{1}, k_{j}^{0})$ 组成，其中 $0 ⩽ k_{j}^{i} ⩽ r - 1$ ， $r$ 为基数。基数排序得到递增序列的过程如下：

初始化：设置 $r$ 个空队列 $Q_{0}, Q_{1}, \dots, Q_{r - 1}$
按照各个关键字位权重递增的次序（个、十、百）对 $d$ 个关键字位分别做分配和收集
- 分配：顺序扫描各个元素，若当前处理的关键字位 $= x$ ，则将元素插入 $Q_{x}$ 队尾
- 收集：把 $Q_{0}, Q_{1}, \dots, Q_{r - 1}$ 各个队列中的结点依次出队并链接

对于以下序列：

\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myNum{520,211,438,888,007,111,985,666,996,233,168}
		\foreach \num [count=\idx] in \myNum {
			\node at (\idx*1.5,0) (\idx){\num};
		}
		\foreach \i in{2,3,...,11}{
			\pgfmathtruncatemacro{\pre}{\i-1};
			\draw[-latex](\pre)--(\i);
		}
	\end{tikzpicture}
\end{document}

第一趟归并如下，以个位分配

\usetikzlibrary{positioning}
\newcommand{\drawMyVar}[2]{
	\pgfmathsetmacro{\myvar}{#1}
	\def\keys{#2}
	\foreach \num [count=\i] in \keys {
		\pgfmathtruncatemacro{\pre}{\i-1};
		\node[fill=gray!20, minimum width=3em, minimum height=3em, below=of \myvar-\pre] (\myvar-\i){\num};
		\draw[-latex] (\myvar-\pre) -- (\myvar-\i);
		}
	}
 
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myChar{$Q_{9}$,$Q_{8}$,$Q_{7}$,$Q_{6}$,$Q_{5}$,$Q_{4}$,$Q_{3}$,$Q_{2}$,$Q_{1}$,$Q_{0}$}
		\foreach \char [count=\idx] in \myChar {
			\pgfmathtruncatemacro{\q}{10-\idx};
			\node at (\idx,0) (\q-0){\char};
		}
 
		\drawMyVar{0}{520};
		\drawMyVar{1}{211,111};
		\drawMyVar{3}{233};
		\drawMyVar{5}{985};
		\drawMyVar{6}{666,996};
		\drawMyVar{7}{007};
		\drawMyVar{8}{438,888,168};
	\end{tikzpicture}
\end{document}

第一趟收集结束，得到按个位递减排序的序列

\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myNum{438,888,168,007,666,996,985,233,211,111,520}
		\foreach \num [count=\idx] in \myNum {
			\node at (\idx*1.5,0) (\idx){\num};
		}
		\foreach \i in{2,3,...,11}{
			\pgfmathtruncatemacro{\pre}{\i-1};
			\draw[-latex](\pre)--(\i);
		}
	\end{tikzpicture}
\end{document}

第二趟归并以第一趟的结果为基础，以十位分配，十位相同的按个位递减排序

\usetikzlibrary{positioning}
\newcommand{\drawMyVar}[2]{
	\pgfmathsetmacro{\myvar}{#1}
	\def\keys{#2}
	\foreach \num [count=\i] in \keys {
		\pgfmathtruncatemacro{\pre}{\i-1};
		\node[fill=gray!20, minimum width=3em, minimum height=3em, below=of \myvar-\pre] (\myvar-\i){\num};
		\draw[-latex] (\myvar-\pre) -- (\myvar-\i);
		}
	}
 
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myChar{$Q_{9}$,$Q_{8}$,$Q_{7}$,$Q_{6}$,$Q_{5}$,$Q_{4}$,$Q_{3}$,$Q_{2}$,$Q_{1}$,$Q_{0}$}
		\foreach \char [count=\idx] in \myChar {
			\pgfmathtruncatemacro{\q}{10-\idx};
			\node at (\idx,0) (\q-0){\char};
		}
 
		\drawMyVar{0}{007};
		\drawMyVar{1}{211,111};
		\drawMyVar{2}{520};
		\drawMyVar{3}{438,233};
		\drawMyVar{6}{168,666};
		\drawMyVar{8}{888,985};
		\drawMyVar{9}{996};
	\end{tikzpicture}
\end{document}

第二趟收集结束，得到按十位递减排序的序列

\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myNum{996,888,985,168,666,438,233,520,211,111,007}
		\foreach \num [count=\idx] in \myNum {
			\node at (\idx*1.5,0) (\idx){\num};
		}
		\foreach \i in{2,3,...,11}{
			\pgfmathtruncatemacro{\pre}{\i-1};
			\draw[-latex](\pre)--(\i);
		}
	\end{tikzpicture}
\end{document}

第三趟归并以第二趟的结果为基础，以百位分配，百位相同的按十位递减排序

\usetikzlibrary{positioning}
\newcommand{\drawMyVar}[2]{
	\pgfmathsetmacro{\myvar}{#1}
	\def\keys{#2}
	\foreach \num [count=\i] in \keys {
		\pgfmathtruncatemacro{\pre}{\i-1};
		\node[fill=gray!20, minimum width=3em, minimum height=3em, below=of \myvar-\pre] (\myvar-\i){\num};
		\draw[-latex] (\myvar-\pre) -- (\myvar-\i);
		}
	}
 
\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myChar{$Q_{9}$,$Q_{8}$,$Q_{7}$,$Q_{6}$,$Q_{5}$,$Q_{4}$,$Q_{3}$,$Q_{2}$,$Q_{1}$,$Q_{0}$}
		\foreach \char [count=\idx] in \myChar {
			\pgfmathtruncatemacro{\q}{10-\idx};
			\node at (\idx,0) (\q-0){\char};
		}
 
		\drawMyVar{0}{007};
		\drawMyVar{1}{168,111};
		\drawMyVar{2}{233,211};
		\drawMyVar{4}{438};
		\drawMyVar{5}{520};
		\drawMyVar{6}{666};
		\drawMyVar{8}{888};
		\drawMyVar{9}{996,985};
	\end{tikzpicture}
\end{document}

第三趟收集结束，得到按百位递减排序的序列

\begin{document}
	\begin{tikzpicture}[scale=1.5, ultra thick]
	\tikzstyle{every node}=[font=\huge, draw=black, very thick, rectangle, minimum width=1.5cm, minimum height=3em]
		\def\myNum{996,985,888,666,520,438,233,211,168,111,007}
		\foreach \num [count=\idx] in \myNum {
			\node at (\idx*1.5,0) (\idx){\num};
		}
		\foreach \i in{2,3,...,11}{
			\pgfmathtruncatemacro{\pre}{\i-1};
			\draw[-latex](\pre)--(\i);
		}
	\end{tikzpicture}
\end{document}

算法效率分析

空间效率： $O (r)$ ，其中 $r$ 为基数，需要的辅助空间（队列）为 $r$ ；（链式存储）
时间效率：一共进行 $d$ 趟分配收集，一趟分配需要 $O (n)$ ，一趟收集需要 $O (r)$ ，时间复杂度为 $O [d (n + r)]$ ，且与序列的初始状态无关
稳定性：稳定
基数排序不是基于比较的排序算法

基数排序擅长解决的问题

数据元素的关键字可以方便地拆分为 $d$ 组，且 $d$ 较小；（如出生时间可以拆分为年月日）
每组关键字的取值范围不大，即 $r$ 较小；
数据元素个数 $n$ 较大；

8.5.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

8.6 各种内部排序算法的比较及应用

1. 时间复杂度、空间复杂度、稳定性

算法种类	最好情况	平均情况	最坏情况	空间复杂度	稳定性
直接插入排序	$O (n)$	$O (n^{2})$		$O (1)$
折半插入排序		$O (n^{2})$		$O (1)$
希尔排序		$O (n^{2})$		$O (1)$	否
冒泡排序	$O (n)$	$O (n^{2})$		$O (1)$
快速排序		$O (n lo g_{2} n)$	$O (n^{2})$	$O (lo g_{2} n) \sim O (n)$	否
简单选择排序		$O (n^{2})$		$O (1)$	否
堆排序		$O (n lo g_{2} n)$		$O (1)$	否
2路归并排序		$O (n lo g_{2} n)$		$O (n)$
基数排序		$O (d (n + r))$		$O (r)$

时间复杂度

快速排序：对称时时间复杂度为 $O (n lo g_{2} n)$ ，最大限度不对称时为 $O (n^{2})$
堆排序：建堆时间 $O (n)$ ，每次调整 $O (h)$ ，总时间复杂度为 $O (n lo g_{2} n)$
2路归并排序：每趟归并 $O (n)$ ，共需要 $⌈ lo g_{2} n ⌉$ 趟归并，总时间复杂度为 $O (n lo g_{2} n)$
基数排序： $d$ 趟分配和收集，每趟分配 $O (n)$ ，每趟收集 $O (r)$ ，总时间复杂度 $O (d (n + r))$

空间复杂度

快速排序：平均 $O (lo g_{2} n)$ ，最坏 $O (n)$ —— 辅助栈用于递归
2路归并排序： $O (n)$ —— 辅助队列用于元素复制
基数排序： $O (r)$ —— 辅助队列用于分配元素

稳定性

希尔排序：当相同关键字的记录被划分到不同子表时，有可能会改变它们之间的相对次序
快速排序：划分算法中，若右端区间有两个关键字相同，且均小于基准值，则在交换到左端区间后，它们的相对位置就会发生变化
简单选择排序：在第 i 趟找到最小元素后，和第i个元素交换，可能会导致第 i 个元素与其含有相同关键字元素的相对位置发生改变
堆排序：进行筛选时，有可能把后面相同关键字的元素调整到前面

2. 过程特征

经过一趟排序，能够保证一个元素到达最终位置
- 交换类：冒泡排序、快速排序
- 选择类：简单选择排序、堆排序
元素比较次数与原始序列无关：简单选择排序、折半插入排序、归并排序易错
排序趟数与原始序列有关：交换类，即冒泡排序、快速排序
排序方法中，元素的移动次数与原始序列无关：基数排序
只适用于顺序存储：折半插入排序、希尔排序、快速排序、堆排序
适合并行的算法：快速排序、归并排序、希尔排序

3. 排序算法的选择

若 $n$ 较小，可采用时间复杂度为 $O (n^{2})$ 的排序方法：直接插入排序、简单选择排序，该情况下，若记录本身信息量较大，用简单选择排序；
若 $n$ 较大，应采用时间复杂度为 $O (n lo g_{2} n)$ 的排序方法：快速排序、归并排序、堆排序
- 快速排序——目前基于比较的内部排序方法中最好的方法，当关键字随机分布时，平均实际最短；
若 $n$ 很大，记录的关键字位数较少且可分解，选择基数排序
若记录本上信息量较大，可用链表作为存储结构；
若要求排序稳定且时间复杂度为 $O (n lo g_{2} n)$ ，则选择归并排序，通常和直接插入排序结合使用：先利用直接插入排序求得较长的有序子文件，再两两归并，仍是稳定；易错
基数排序不能对 float 和 double 类型的实数进行排序；

个人体会

为了方便理解，这里有些叙述可能只包含了正序排序

插入排序：每一趟将一个待排序的元素，插入到前面已经排好序的子序列中，直到全部记录插入完成

直接插入排序：每次让已经遍历过的元素局部有序
希尔排序：每次让所选子表局部有序

交换排序：根据序列中两个元素的比较结果来对换这两个元素在序列中的位置

冒泡排序：每次找到最小元素的最终位置（并且让后续元素更有序？）
快速排序：每次找到中间某个元素的最终位置，并划分左右子序列

选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列

简单选择排序：每次找到最小元素的最终位置

8.6.3 本节习题精选

选择题：题目、答案

综合题：题目、答案

8.7 外部排序

8.7.2 外部排序的方法

外部排序资料（已拆分为两个网页附件）：

外存与内存之间的数据交换

操作系统以块为单位对磁盘存储空间进行管理，每个磁盘块内存放着各种各样的数据。磁盘的读写以块为单位，数据读入内存后才能修改，修改完了还要写回磁盘

外部排序：数据元素太多，无法一次全部读入内存进行排序

使用归并排序的方法，最少只需要的内存中分配3块大小的缓冲区即可对任意一个大文件进行排序
- 归并排序要求各个子序列有序，每次读入两块的内容，进行内部排序后写回磁盘
- 将两个有序归并段归并为一个

\usetikzlibrary{matrix}
\usetikzlibrary{fit, backgrounds, shadows}
\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=0.8, ultra thick,
	every node/.style={font=\huge, draw=black, very thick, rectangle, minimum width=3em, minimum height=3em},
	block/.style={dashed, rectangle, rounded corners, drop shadow={gray!20}},
	]
		\matrix[draw=none] at(0,0) (node)[matrix of nodes, column sep=0.5em, row sep=2.5em, nodes in empty cells, nodes={fill=blue!20}]{
			 & & & [2em] & & & [2em] & & & [2em] & & \\
			 & & & [2em] & & & [2em] & & & [2em] & & \\
			 & & & [2em] & & & [2em] & & & [2em] & & \\
			 & & & [2em] & & & [2em] & & & [2em] & & \\
		};
		\matrix[draw=none] at(20,0) (iocache)[matrix of nodes, column sep=0.5em, row sep=5em, nodes in empty cells, nodes={draw=none}]{
			 & & & [2em] & & \\
			 & & & [2em] & & \\
			 & & & [2em] & & \\
		};
 
	\begin{scope}[on background layer]
		\node [fit=(node), inner sep=2em] (disk){};
		\node [fit=(iocache), inner sep=2em] (cache){};
		\foreach \i in{1,2,3,4}{
			\node [fit=(node-\i-1)(node-\i-3), block] (shadow-\i-1){};
			\node [fit=(node-\i-4)(node-\i-6), block] (shadow-\i-2){};
			\node [fit=(node-\i-7)(node-\i-9), block] (shadow-\i-3){};
			\node [fit=(node-\i-10)(node-\i-12), block] (shadow-\i-4){};
		}
		\foreach \i in{1,2,3,4}{
			\node [fit=(shadow-\i-1)(shadow-\i-2), red, inner sep=0.5em] (shadow-\i-5){};
			\node [fit=(shadow-\i-3)(shadow-\i-4), red, inner sep=0.5em] (shadow-\i-6){};
		}
		\node [fit=(iocache-1-4)(iocache-1-6), block, fill=blue!10](incache1){};
		\node [fit=(iocache-2-1)(iocache-2-3), block, fill=brown!10](outcache){};
		\node [fit=(iocache-3-4)(iocache-3-6), block, fill=blue!10](incache2){};
 
	\end{scope}
 
	\draw[latex-latex] (disk) -- (cache);
 
	\end{tikzpicture}
\end{document}

假设内存中共有一个输出缓冲区、两个输入缓冲区，磁盘中共有16个磁盘块
生成初始归并段：每次读入相邻两个磁盘块，直接排序后输出到原位置，从而实现包含两个磁盘块的归并段，最终得到8个段内有序归并段
第1次归并：利用归并原理每次对相邻两个归并段进行归并操作。输出缓冲区满后写回磁盘，每当一个缓冲区空了就用对应归并段的下一个磁盘块补上。最终归并为一个更大的归并段。
第 $i$ 次归并：利用归并原理再对相邻两个更大的归并段进行归并操作，最终完成所有磁盘块中数据的排序。

$k$ 路平衡归并：最多只能有 $k$ 个段归并为一个；每一趟归并中，若有 $m$ 个归并段参与归并，则经过这一趟处理得到 $⌈ m / k ⌉$ 个新的归并段

时间开销分析

外部排序时间开销=读写外存时间+内部排序所需时间+内部归并所需时间

优化思路

对于 $r$ 个初始归并段，做 $k$ 路归并，则归并树可以用 $k$ 叉树来表示。若树高为 $h$ ，则 $k$ 叉树第 $h$ 层最多有 $k^{h - 1}$ 个结点，则 $r ⩽ k^{h - 1}$ ，归并趟数 $S = h - 1 = ⌈ lo g_{k} r ⌉$
优化思路1：使用多路归并来增加路数 $k$
- 代价1：需要增加相应的输入缓冲区
- 代价2：每次从 $k$ 个归并段中选一个最小元素需要进行 $k - 1$ 次关键字对比——可以通过“败者树”减少关键字对比次数
优化思路2：减少初始归并段数量 $r$ ，即增加初始归并段长度

按照本节介绍的方法生成的初始归并段，若共有 $N$ 个记录，内存工作区可以容纳 $L$ 个记录，则初始归并段数量 $r = ⌈ N / L ⌉$ 可以通过“置换-选择排序”进一步减少初始归并段数量

8.7.3 多路平衡归并与败者树

通过败者树减少关键字对比次数

败者树.pdf

疑问

没太理解这个，比如说下面的例子中，来个6，然后来个5咋办

败者树：可视为一棵完全二叉树（多一个头头）。 $k$ 个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的失败者，从而让胜者往上继续进行比较，一直到根结点

败者树每一个叶子结点对应一个归并段，分支结点记录失败者来自哪个归并段
$k$ 路归并的败者树只需要定义一个长度为 $k$ 的数组即可，而叶子结点的虚拟的
对于 $k$ 路归并，第一次构造败者树需要对比关键字 $k - 1$ 次，有了败者树选出最小元素只需要对比关键字 $⌈ lo g_{2} k ⌉$ 次

\usetikzlibrary{matrix}
\usetikzlibrary{fit, backgrounds, shadows}
\usetikzlibrary{positioning}
\begin{document}
	\begin{tikzpicture}[scale=2, ultra thick,
	every node/.style={draw=black, circle, very thick, font =\huge, minimum size=3em},
	mymatrix/.style={matrix of nodes, yshift=-6em, rectangle, row sep=0.5em, nodes={rectangle}},
	level 1/.style={sibling distance=16em/1, level distance=3em},
	level 2/.style={sibling distance=16em/1, level distance=3em},
	level 3/.style={sibling distance=16em/2, level distance=3em},
	level 4/.style={sibling distance=16em/4, level distance=3em},
	]
	\node {3}
	child {node {5}
		child {node {2}
			child {node {1}
				child {node (1){27}}
				child {node (2){12}}
			}
			child {node {4}
				child {node (3){1}}
				child {node (4){17}}
			}
		}
        child {node {8}
			child {node {6}
				child {node (5){2}}
				child {node (6){9}}
			}
			child {node {7}
				child {node (7){11}}
				child {node (8){4}}
			}
		}
	};
 
	\matrix [mymatrix, below of=1]{27\\30\\46\\};
	\matrix [mymatrix, below of=2]{12\\36\\40\\};
	\matrix [mymatrix, below of=3]{1\\6\\7\\};
	\matrix [mymatrix, below of=4]{17\\22\\27\\};
	\matrix [mymatrix, below of=5]{2\\3\\89\\};
	\matrix [mymatrix, below of=6]{9\\15\\19\\};
	\matrix [mymatrix, below of=7]{11\\13\\53\\};
	\matrix [mymatrix, below of=8]{4\\31\\77\\};
	\end{tikzpicture}
\end{document}

8.7.4 置换-选择排序

构造更长的初始归并段

置换-选择排序.pdf

土办法：用于内部排序的内存工作区WA可容纳 l 个记录，则每个初始归并段也只能包含 l 个记录，若文件共有 $n$ 个记录，则初始归并段的数量 $r = n / l$ ——由内存区大小决定

置换-选择排序流程：现有待排序文件FI、内存工作区WA、初始归并输出文件FO

从 FI 输入 w 个记录到工作区 WA
从 WA 中选出其中关键字取最小值的记录，作为MINIMAX记录
将MINIMAX记录输出到FO中去
若 FI 不空，则从 FI 输入下一个记录到 WA 中
从 WA 中所有关键字比MINIMAX 记录的关键字大的记录中选出最小关键字记录，作为新的 MINIMAX 记录
重复3~5，直到 WA 内的关键字都比MINIMAX更小，则该归并段在此截止，得到一个初始归并段
重复2~6，直到WA为空，由此得到全部的初始归并段

8.7.5 最佳归并树

如果使用置换选择排序构造初始归并段，则初始归并段所占块数将各不相同，利用哈夫曼树让磁盘I/O次数最少

最佳归并树.pdf

归并段的神秘性质：初始归并段所占块数各不相同，进行两两合并进行二路归并
每个初始归并段可以看作一个叶子结点，归并段的长度作为结点权值，则归并树的带权路径长度WPL = 读磁盘次数 = 写磁盘次数，即I/O次数=2WPL
构造哈夫曼树来优化归并过程
- 对于 $k$ 叉归并，若初始归并段的数量无法构成严格的 $k$ 叉归并树，则需要补充几个长度为0的虚段，再进行k叉哈夫曼树的构造
- $k$ 叉最佳归并树最终一定是一棵严格的 $k$ 叉树，即树中只包含度为 $k$ 和度为 $0$ 的结点。设度为 k 的结点有 $n_{k}$ 个，度为 0 的结点有 $n_{0}$ 个，归并树总结点树 $= n$ ，则：初始归并段数量 + 虚段数量 $= n_{0}$ 且 $n = n_{0} + n_{k}$ ，除根结点外头上都连着一个分叉 $k n_{k} = n - 1$ ，所以如果是严格 $k$ 叉树， $n_{k} = \frac{n _{0} - 1}{k - 1}$ 一定能除的尽
  - 如果 $(初始归并段数量 - 1) % (k - 1) = 0$ ，则刚好可以构成严格 $k$ 叉树
  - 如果 $(初始归并段数量 - 1) % (k - 1) = u \neq = 0$ ，则需要补充 $(k - 1) - u$ 个虚段

8.7.6 本节习题精选

选择题：题目、答案

综合题：题目、答案

我的 Obsidian 知识库

探索

第8章排序

8.1 排序的基本概念

8.1.2 本节习题精选

8.2 插入排序

8.2.1 直接插入排序

8.2.2 折半插入排序

8.2.3 希尔排序

8.2.4 本节习题精选

8.3 交换排序

8.3.1 冒泡排序

8.3.2 快速排序

8.3.3 本节习题精选

8.4 选择排序

8.4.1 简单选择排序

8.4.2 堆排序

堆的插入和删除

8.4.3 本节习题精选

8.5 归并排序和基数排序

8.5.1 归并排序

8.5.2 基数排序

8.5.3 本节习题精选

8.6 各种内部排序算法的比较及应用

1. 时间复杂度、空间复杂度、稳定性

2. 过程特征

3. 排序算法的选择

个人体会

8.6.3 本节习题精选

8.7 外部排序

8.7.2 外部排序的方法

8.7.3 多路平衡归并与败者树

8.7.4 置换-选择排序

8.7.5 最佳归并树

8.7.6 本节习题精选

关系图谱

目录

反向链接

我的 Obsidian 知识库

探索

第8章 排序

8.1 排序的基本概念

8.1.2 本节习题精选

8.2 插入排序

8.2.1 直接插入排序

8.2.2 折半插入排序

8.2.3 希尔排序

8.2.4 本节习题精选

8.3 交换排序

8.3.1 冒泡排序

8.3.2 快速排序

8.3.3 本节习题精选

8.4 选择排序

8.4.1 简单选择排序

8.4.2 堆排序

堆的插入和删除

8.4.3 本节习题精选

8.5 归并排序和基数排序

8.5.1 归并排序

8.5.2 基数排序

8.5.3 本节习题精选

8.6 各种内部排序算法的比较及应用

1. 时间复杂度、空间复杂度、稳定性

2. 过程特征

3. 排序算法的选择

个人体会

8.6.3 本节习题精选

8.7 外部排序

8.7.2 外部排序的方法

8.7.3 多路平衡归并与败者树

8.7.4 置换-选择排序

8.7.5 最佳归并树

8.7.6 本节习题精选

关系图谱

目录

反向链接

第8章排序