开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> [Alg]排序算法之交换排序（写文章要有深度，直接刨它祖坟） -> 正文阅读

[数据结构与算法][Alg]排序算法之交换排序（写文章要有深度，直接刨它祖坟）

[Alg]排序算法之交换排序（写文章要有深度，直接刨它祖坟）#

作者：屎壳郎 miaosg01@163.com

日期：July 2021

版次：初版

简介： 交换排序是排序算法中的一大类，通过构成反序数据对的两两交换来消除反序，最终得到有秩序的排列。那么排列交换的本质是什么呢？说来话长，让我们回到远古时代，重温数据结构，从环形链表开始说起。

0、交换排序的本质

环形链表的合并：

假设现在我们有两个指针分别指向两个环形链表，要想把两个环形链表合并成一个的操作为： $LINK(ptr1)\leftrightarrow LINK(ptr2)$ ，即交换这两个指针的链接地址。见下图：
在这里插入图片描述

环形链表的拆分：

那么反过来，我们想把一个环形链表拆分成两个环形链表，如何操作呢？同样的操作，只是两个指针要指向同一个环形链表内： $LIND(ptr1)\leftrightarrow LINK(ptr2)$ ，即交换这两个指针的链接地址。区别就在于合并两个链表时，两个指针指向不同的环形链表；而拆分环形链表时，两个指针指向同一个链表。 见下图：
在这里插入图片描述

讲了这么多，环形链表的合并拆分跟交换排序又有什么关系？我要说数组就是一个或多个环形链表组成，你信吗？我们举个例子： $(3\,7\,6\,9\,8\,1\,4\,5\,2)$ ， $R_1$ 的值为3，表示 $R_1$ 存储的指针指向 $R_3$ ，即 $R_1\rightarrow R_3$ ，依此推算 $R_1\rightarrow R_3\rightarrow R_6\rightarrow R_1$ 构成了一个环形链表（红色表示）；同理 $R_5,R_8)$ （蓝色表示）和 $R_2,R_7,R_4,R_9)$ （黑色表示）分别构成了两个环形链表。所以这个排列可表示为： $((3\,6\,1)(2\,7\,4\,9)(5\,8))$ 共三个环形链表构成的数组排列（在《排列与反序》中，应用这个思想解决了由反序表生成对应的排列问题，同时提供了数组转链表、链表转数组的算法）。见下图：
在这里插入图片描述

我们在不同的环中交换一次数据，环数减少1；在同环中交换一次数据环数增加1。我们交换排序的目标是把它排列为 $(1\,2\,3\,4\,5\,6\,7\,8\,9)$ ，只包含一个元素、指向自身的环。还是以上面的例子为例，有3个环，我们的排序目标是9个元素要形成9个环，那么最少的交换次序 $9 ? 3 = 6$ ，即最少要交换（同环交换）6次才能完成排序。理解了排列是由不同的环构成的，也就明白为什么第一类斯特林数满足 $\sum_k{n\brack k}=n!$ 性质—— $n$ 个元素形成不同环的数量总和等于 $n$ 的排列数，其有一一的对应关系。（参考《排列与反序》，里面有详细的数组转链表、链表转数组的讲解，可加深对这方面知识的理解。）

1、最短的排序程序，没有之一

最基本的算法就是与相邻的数据两两比较、交换，这是冒泡排序的基本思路。与直接插入排序类似，两两的比较交换数据是非常低效的，因其数据需要的平均净移动量为 ${1\over3}N$ ，见《[Alg]排序算法之插入排序》。当然，万事万物都有其两面性，牺牲了性能，得到的好处是最简洁的代码，下面是最短的排序程序描述：

	   int i;
begin: i = N; //设置从头开始遍历
	   for( ; i > 0; --i){
	    	if(R[i] < R[i-1]){
		    	R[i] <-> R[i-1];//交换数据
			    goto begin;
		    } 
	   }

这个算法原理非常之简单，从头开始遍历数据记录并与其相邻的记录比较，发现一个反序后即对进行数据交换，然后从头开始重新遍历，直到消除所有的反序，至此if分支不成立，不执行条件语句中的goto跳转，然后从循环退出。这是一个比冒泡排序还苯的算法，大约平均执行 ${1\over4}N^2$ （见拆分数，反序的均值）次循环（一个反序对应一次循环）时间复杂度 $O(N^3)$ 。这个算法除了能增加一点我们的见识，貌似没有其它作用了(在快排中，选头、中、尾三个数据时用到了，这个排序很简洁，比写一大堆的if语句要好）。

回过头来接着聊冒泡排序，冒泡排序相邻的数据两两比较，成反序则交换。一趟遍历后，大数据上浮；我们可以在下一趟遍历时，让小数据下沉。这点改进稍稍能提高点性能，但与直接插入比起来，虽然都很垃圾，但冒泡排序更垃圾，其代码量相当于直接插入排序的两倍。好像除了冒泡排序妇孺皆知、广为传诵的名字，也没有其它让人欣赏的东西了。

2、Batcher’s 并行排序算法

我们从《[Alg]排序算法之插入排序》的分析中得知，要提高算法的效率，就要增大比较和交换的跨度。下面提到的算法和shell排序算法类似，增加比较交换跨度。虽然其原理相似，但其具体的实现手段却相去甚远。这种增大跨度的方式很新奇，亦非常的错综复杂，不容易理解。我们先列出算法的实现，再配以例子逐条解释。可能也只有这个方法能把算法过程说的明白一点，我实在想不出其它更好的方式了。

算法M：（Batcher’s 并行算法）

设记录 $R_0,R_1,\ldots, R_{N-1}$ ，其关键词为： $K_0,K_1,\ldots,K_{N-1}$ ，假设 $N ? 1 > 2$ 。

M1.[初始化 $p$ .] 置 $p\gets2^{t-1}$ ，在这里 $t=\lceil\lg N\rceil$ ，即 $t$ 取满足条件 $2^t\geq N$ 的最小值。
M2.[初始化 $q, r, d$ .] 置 $q\gets2^{t-1}$ ， $r\gets0$ ， $d\gets p$ 。
M3.[循环 $i$ .] For $0\leq i<N-d$ and $i\wedge p=r$ ，执行M4，然后转到M5。
M4.[比较交换] 如果 $K_{i+1}>K_{i+d+1}$ ，交换 $R_{i+1}\leftrightarrow R_{i+d+1}$ 。
M5.[循环 $q$ .] 如果 $q\neq p$ ，置 $d\gets q-p$ ， $q\gets q/2$ ， $r\gets p$ ，并返回M3。
M6.[循环 $p$ .] 置 $p\gets p/2$ ，如果 $p > 0$ ，返回M2；否则结束。

先设置一个例子，设记录 $R$ 其值为 $R_0,R_1,R_2,R_3,R_4,R_5,R_6,R_7)$ 。

1、 $p$ 在算法中的作用是对数据分段，例子 $R$ 中共有8个数据项， $t=3, p=2^{t-1}=4$ 。M1和M6构成了算法的整个外循环，执行 $p = 4, p = 2, p = 1$ 不同分段，然后结束。
2、 $r$ 控制数据段的选取，在M3中条件 $0\leq i<N-d$ 是防止数据越界，和段选择条件 $i\wedge p=r$ （逻辑位and操作，相当于c语言的 $i\&p==r$ ）一起，控制着整个比较交换过程数据段选择。
3、 $q$ 和 $d$ 一起控制着比较、交换过程的跨度。
以上述例子，运行一遍会更清晰：

第一趟： $p = 4$

$p$	$q$	$r$	$d$
4	4	0	4

M3中条件 $0\leq i<4$ 选出大范围保证不越界，然后条件进一步精确到数据段 $i\wedge p=0$ ， $p=4(0100)_2$ 选取的为
$0(0000)_2\wedge4(0100)_2=0$
$1(0001)_2\wedge4(0100)_2=0$
$2(0010)_2\wedge4(0100)_2=0$
$3(0011)_2\wedge4(0100)_2=0$

即为选中 $R_0,R_1,R_2,R_3)$ （在第一步中两条件重合，后续会看的更清楚）在跨度 $d = 4$ 的情况下比较交换，即： $R_0:R_4),(R_1:R_5),(R_2:R_6),(R_3:R_7)$ 。

$p = 2$ 时：

$p$	$q$	$r$	$d$
2	4	0	2
2	2	2	2

首先选出大范围 $0\leq i<6(N-d)$ 以双竖线标出，再在这个大范围内选出长度2的数据段 $(\overline{R_0,R_1},R_2,R_3,\overline{R_4,R_5}||R_6,R_7)$ ，上划线的项与随后的不带上划线的项比较交换。

在M5处，改变跨度 $d\gets q-p$ ， $q\gets q/2$ ；反转数据段选择 $r\gets p$ ，即改为上次没选中的 $(R_0,R_1,\overline{R_2,R_3},\underline{R_4,R_5}||R_6,R_7)$ 以跨度 $d = 2$ 与后面的项比较交换，即上划线为选中数据与下划线部分比较交换。

$p = 1$ 时

$p$	$q$	$r$	$d$	比较次序（上划线与下划线比较交换）
1	4	0	1	$(\overline{R_0},\underline{R_1},\overline{R_2},\underline{R_3},\overline{R_4},\underline{R_5},\overline{R_6}\\|\underline{R_7})$
1	2	1	3	$(R_0,\overline{R_1},{R_2},\overline{R_3},\underline{R_4},{R_5},\underline{R_6}\\|{R_7})$
1	1	1	1	$({R_0},\overline{R_1},\underline{R_2},\overline{R_3},\underline{R_4},\overline{R_5},\underline{R_6}\\|{R_7})$

从上面的详解中可以看出，这个算法是一个非常机械的过程，只要确定了 $N$ ，后续所有的比较、交换、跨度等等要素全部确定，它不依赖于任何前序的执行结果，这点与后面要介绍的快速排序完全不同，快排依赖于上次的划分。万事万物都有其两面性，这个特点使得该算法笨重，但是它这个特征使得它也特别适合于并行计算，在M3步骤中，满足条件多个执行过程数据的对比交换过程没有交叉重叠，完全可同步执行。整个执行过程可在 $O({1\over2}{\lceil\lg N\rceil})(\lceil\lg N\rceil+1)$ 完成，这是串行算法所不能达到的。

3、快速排序

快排应该是应用范围最广、广为人知的一种算法，它是典型的分治思想的应用。其基本原理是选出一项，如 $R_1$ 为基准，与其它项逐个比较，比它大的项放置在右侧，比它小的项放置左侧，这样一个大问题就划分成了两个同样的子问题。依此递归下去，便得到结果。

算法Q：（快速排序）

设记录 $(R_1,R_2,\ldots, R_N)$ ，其对应键值 $(K_1,K_2,\ldots,K_N)$ 。同时需要辅助stack，容量为 $\lfloor\lg N\rfloor$ 。我们对算法实现在了如下处理：

1、在头尾插入 $K_0=-\infty$ 和 $K_{N+1}=\infty$ ，以免除麻烦的边界条件检查；
2、为避免子划分很小时，快排反复划分和stack操作的低效问题，设置了一个阀值， $M = 9$ ，当子划分小于等于该值时，转为直接插入排序。（ $M = 9$ 为最优值，TAOCP 5.2.2 P120给出了详细的数学分析。）
3、为了保持内循环的高效和尽量的划分均等，相等的键值也进行交换。
Q1.[初始化] 如果 $N\leq M$ ，转到Q9。否则，stack置空；并置 $l\gets 1$ ， $r\gets N$ 。
Q2.[准备递归步骤] 置 $i\gets l$ ， $j\gets r+1$ ；并设 $K\gets K_l$ 。
Q3.[比较 $K_i:K$ ] $i\gets i+1$ ，如果 $K_i<K$ ，重复。
Q4.[比较 $K:K_j$ ] $j\gets j-1$ ，如果 $K<K_j$ ，重复。
Q5.[比较 $i : j$ ] 如果 $j\leq i$ ，交换 $R_l\leftrightarrow R_j$ 并跳转至Q7。
Q6.[交换] 交换 $R_i\leftrightarrow R_j$ ，并返回Q3。
Q7.[压栈] 如果 $r-j\geq j-l>M$ ， $(j + 1, r)$ 压栈，置 $r\gets j-1$ 并返回Q2；如果 $j ? l > r ? j > M$ ， $(l, j ? 1)$ 压栈，置 $l\gets j+1$ 并返回Q2；如果 $r ? j > M > j ? l$ ，置 $l\gets j+1$ 并返回Q2；如果 $j-l>M\geq r-j$ ，置 $r\gets j-1$ 并返回Q2.
Q8.[弹栈] 如果stack非空， $(l^{'}, r^{'})$ 出栈，并置 $l\gets l',r\gets r'$ 并返回Q2。
Q9.[直接插入排序]参见《[Alg]排序算法之插入排序》

快排退化问题

不同于其它排序算法，快排喜欢乱序的输入，对接近排好序（秩序越好）是非常不友好的，最坏的情况出现在完全排好序的排列，快排只能每次分离出一个数据，且时间复杂度退化至 $O(N^2)$ 。为避免这种窘境，可以采取以以下措施来改善。

1、采用随机化的方法选择基准（随机选择算法中提到的 $R_l$ ），这样就避免了从头开始选择最大值或最小值，致使划分出一个元素的尴尬。
2、从头、尾及中间分别选取三个值，取中间值，这个方法相对简单，且避免了生成随机数的开销。

我们现在考虑一种更极端的情况，假设所有的排序关键词 $K$ 都相等，会出现什么情况？ $i$ 从头到尾与 $j$ 逐个交换，在中点结束，形成完美的二等分；假设我们把 $Q 3$ 、 $Q 4$ 的 $<$ 改为 $\leq$ 呢？ $i$ $j$ 不交换任何值，只是在 $Q 5$ 步交换 $R_l\leftrightarrow R_j$ ，即 $R_0$ 与 $R_1$ ，随后 $R_0$ 与 $R_2$ 交换，依次的 $R_0$ 与 $R_3,R_4,\ldots,R_N$ 交换，哇——进入灾难模式。

消除边界条件检查

在算法前置条件中提到，在头尾分别插入 $K_0=-\infty$ 和 $K_{N+1}=\infty$ ，它们的作用分别是 $K_0$ 消除最后直接插入排序算法的边界条件检查，后面的 $K_{N+1}$ 的作用是当选择 $K_l$ 为最大值时，防止寻找 $K_i>K_l$ 值时发生越界。

我们在讨论插入排序时，已经采用了第二种消除边界检查的方法，故可取消 $K_0=-\infty$ ；对于 $K_{N+1}=\infty$ ，我们采用如下方法，针对上面提到的快排退化的改进措施，我们稍加改造，可达到一箭双雕的目的，即可预防快排退化，又可消除右侧边界条件检查，具体如下：

从头、尾、中分别取三个值，中间值交换到最左侧（ $R_l$ )，最大值交换到最右侧（ $R_r$ )。

中位数问题

快速排序算法的这种大事化小、分而治之(divide and conquer)的思想有着广泛的应用。下面这个问题的解决方案就是一个典型的应用范例：给出一个乱序的排列，寻找排序后位于中间位置的值。通常第一个想到的就是排序，然后就容易确定中间值，为了确定一个值而排序是很浪费的，尤其是数据很多的时候。如果我们不采用排序的手段，借鉴快排的处理思路，选取第一个 $K_l$ 为基准，进行交换，运行后的结果是，小于 $K_l$ 的项位于左侧，大于 $K_l$ 的位于右侧，设 $K_l$ 的位置为 $POS(K_l)$ 。如果 $POS(K_l)>mid$ （设 $m i d$ 为中间位置），表明中位数位于左侧数据部分，则继续重复该步骤在左侧寻找；如果 $POS(K_l)<mid$ ，则在右侧数据中寻找；直到找到 $POS(K_l)=mid$ 的值为止。也就是运行快排前几步确定中点的值，因舍弃了不需要的另一部分，故不需要stack存储。

我们以此为例说明了寻找中位数的方法，当然，这个方法可以寻找任意一个位置的数，应该称为K位数问题。

荷兰国旗问题

红色、白色、蓝色的标识随机的排成一列，如何通过两两交换使得红色表示位于顶部，蓝色的位于底部（见荷兰国旗图）。我们要把快排的两分改进为三分天下的问题（是不是叫三国问题或隆中对问题更符合国情）。
在这里插入图片描述

算法D：（三分法快速排序——Tripartitioning Quicksort）

在这里插入图片描述
$b$ 相当于快排的 $i$ ，向右搜索时，如果 $= k$ ，则与 $a$ 交换，直到 $K_b>K$ ； $c$ 相当于快排的 $j$ 向左搜索，遇到 $= K$ ，则与 $d$ 交换，直到 $K_c<K$ 后 $K_b\leftrightarrow K_c$ 交换。依此处理，直到耗尽图中 $? ? ?$ 部分。然后做整理工作，把 $= K$ 的部分交换到中央位置。

D1.[初始化] 置 $a\gets b\gets l$ ， $c\gets d\gets r$ 。
D2.[增加 $b$ ，直到 $K_b>K$ ] 如果 $b\leq c$ and $K_b<K$ ，b加1，重复该步；如果 $b\leq c$ and $K_b=K$ ，交换 $R_a\leftrightarrow R_b$ ，a、b、都加1，重复该步。
D3.[减小 $c$ ，直到 $K_c<K$ ] 如果 $b\leq c$ and $K_c>K$ ，c减1，重复该步；如果 $b\leq c$ and $K_c=K$ ，交换 $R_c\leftrightarrow R_d$ ，c、d都减1，重复该步。
D4.[交换] 如果 $b < c$ ，交换 $R_b\leftrightarrow R_c$ ，b加1，c减1，返回D2。
D5.[整理] For $0\leq k < min(a-l,b-a)$ ，交换 $R_{l+k}\leftrightarrow R_{c-k}$ ；For $0\leq k<min(d-c,r-d)$ ，交换 $R_{b+k}\leftrightarrow R_{r-k}$ 。最后设 $i\gets l+b-a$ ， $j\gets r-d+c$ （把相等值移至中间，具体实现数组旋转请参考《[Alg]排序算法之插入排序》旋转数组部分。

上面的算法D2、D3设置了条件检测 $b\leq c$ 。如果进入D2之前确保 $a < b$ 和 $c < d$ ，上述条件检测完全可以取消。

当键值大量重复或在接近排序尾声时键值接近，这时要花大量精力的检查键值以确定后续操作，这严重降低了算法的效率。可以转为三分快排，因为 $= K$ 的部分为最终确定的位置，后续排序不须再移动，这极大的加快了排序速度。

4、基数交换排序

基数交换排序与快速排序没有什么本质不同，只是把比较 $K$ 改为了按位比较0和1。下面列出算法：

算法R：（基数排序）

设关键词 $K$ 的最高有效位为 $m$ 位，则需要容量 $m ? 1$ 的辅助stack。
$b$ 对位计数。

R1.[初始化] 清空stack，并置 $l\gets 1$ ， $r\gets N$ ， $b\gets 1$ 。
R2.[开始排序] 如果 $l = r$ 转到R10。否则置 $i\gets l$ ， $j\gets r$ 。
R3.[检查 $K_i$ 的 $b$ 位是否为1] 如果为1，转到R6。
R4.[增加 $i$ ] $i\gets i+1$ 。如果 $i\leq j$ ，转至R3；否则转至R8.
R5.[检查 $K_j$ 的 $b$ 位是否为0] 如果为0，转至R7.
R6.[减小 $j$ ] $j\gets j-1$ 。如果 $i\leq j$ ，转至R5；否则转至R8.
R7.[交换] 交换 $R_i\leftrightarrow R_{j+1}$ ，然后跳转至R4.
R8.[检查特殊情形]如果 $b > m$ ，说明对所有的位都处理完，转至R10。否则：如果 $j < l$ 或 $j = r$ （所有位为1或0），转至R2；否则，如果 $j = l$ (只有一个0 bit）， $l\gets l+1$ 并转至R2。
R9.[压栈] $(r, b)$ 压栈，并设 $r\gets j$ ，返回R2。
R10.[弹栈] 如果stack空，结束；否则 $l\gets r+1$ ，弹栈 $(r^{'}, b^{'})$ 并置 $r\gets r'$ ， $b\gets b'$ ，并返回R2.

特别注意b处理，b应该取最大值的最高有效位，保证键值中最少有一个b位为1。如果取值比所有键值的最高有效位还高，那第一趟遍历，所有都为0， $i$ 从左向右搜索时遇不到1，这会导致越界；程序会报段错误。只要第一趟发生一次交换，就能保证边界。后续没有必要边界检查。

基数交换排序也有上面提到的键值接近时的退化问题，例如好多键值 $k$ 位以前都相等，必须检查 $k + 1$ 甚至 $k + 2$ ， $k + 3$ 甚至更多位才能确定后续执行的指令。我们也可以采用三分快排的思想来解决这个问题，就是把记录三分为 $(l, i ? 1, k)$ ， $(i, j, k + 1)$ ， $(j + 1, r, k)$ 三个部分，采用三分快排的思路来处理。