[数据结构与算法][Alg]排序算法之选择排序

[Alg]排序算法之选择排序

作者：屎壳郎 miaosg01@163.com

时间：Aug 2021

版次：初版

简介： 当数据量较大时，堆排序优于shell排序。但无论如何比不过快速排序。快排的效率只是平均意义上的（概率上说），最坏的情况会退化至$N^2$。堆排序的优势在于，在恶化的情况下也能保证时间复杂度在$O(N\lg N)$。后续我们会讲到归并排序也有这个特性，任何情况下都能保证$N\lg N$，但归并排序要求更多的空间。

1、直接选择排序

直接选择排序遍历所有记录N，确定最大值（或最小值），然后输出到最终位置。缩小范围至剩余N-1，重复这个步骤。这个过程和直接插入排序完全相反，直接插入排序是从1个记录开始，一个接一个的往里插入记录，并逐步扩大遍历范围。选择排序直接确定记录的最终位置，而插入排序直到插入最后一个记录后在能确定记录的最终位置。
直接选择排序很简单，直接列算法，一眼就看明白，不须解释。

算法S：（直接选择排序）

设记录$R_1,R_2,\dots ,R_N$，其键值$K_1,K_1,\dots ,K_N$。

• S1.[循环j] For $j=N,N?1,\dots ,2$，执行S2和S3.
• S2.[查找最大值$max(K_1,K_2,\dots ,K_j)$] 遍历$K_j,K_{j?1},\dots ,K_1$，确定最大值$K_i$.
• S3.[交换] 交换$R_i?R_j$，此时$R_j,\dots ,R_N$为最终位置。

要从N个记录中确定最大值，至少比较N-1次，所以直接选择排序的时间复杂度$O(N^2)$。比较次数是没办法节省的，难道就没有改进的余地了吗？要改进算法的效率，无外乎两种途径，其一是对要待解决问题的本质有深入的洞察，并有深厚的数学功底来确立模型，建立高效算法。这点好像比较难。另一个相对简单的方法，不要每次都从零开始，要善于并充分利用前序的工作成果来减小后续的工作量或改善后续工作的复杂度。

对于第一种改进算法的方式，我们直接跳过就好了，毕竟那是计算机专家兼数学家或数学家兼计算机专家的饭碗，做人不能做绝了，给他们留口饭吃。我们重点来讲后一种方法。

我们在遍历$R_j\dots R_1$过程中，如果没有第一次就选中最大值，遍历过程会发生替换，产生一个序列。例如（1 3 2 5 4）第一次选 $max=4$，继续向左搜索，找到 $5>4$，替换 $max=5$，确定5为最大值。直接选择排序没有充分利用这个序列，直接舍弃4（第二大值），下次又从头开始。虽然第一次遍历不能减少比较次数，但我们可以充分利用遍历过程产生的有价值信息。

直接选择排序改进1

对算法做如下改进：
我们需要一个辅助表AUX记录当前最大值信息。我们改为从左到右遍历，这样更方便一点，从max=1开始，遇到3令max=3并保存1的位置，继续向右搜索遇到5，令max=5，并保存3的位置信息2。当5和4交换后，不必从头开始查找，取出辅助表中的位置信息2，从此处开始，位置2代表的意义为，K[2]是从头到2位置的最大值，不必查找位置2以前的记录。这就充分利用了以前比较的成果，减少了不必要的比较。采取这项改进措施，能把平均比较次数减半。

2、方根选择

另一个利用前序比较结果的例子是分组，这种方法不需要额外的空间存储位置信息。下面介绍称之为方根选择的分组选择方法。设$N$ 项记录，分为 $\sqrt{N}$ 组，每组$\sqrt{N}$ 项。
见图例

我们选出最大数908后，要确定第二大值，只需在（170，897，275）中确定最大值，然后与其它组的最大值比较（512，653，765）。我们从上图看到，不影响不含最大值的项。故方根选择要在选出最大值的组内进行$(\sqrt{N}?2)$次比较，与其它组进行$(\sqrt{N}?1)$次比较，其复杂度 $O(N\sqrt{N})$。

推广开来，我们也扩展至立方根，即$N$ 分$\sqrt[3]{N}$组，每组包含$\sqrt[3]{N}$小组，每小组$\sqrt[3]{N}$个项，可降至$O(N\sqrt[3]{N})$。

如果我们再推广，再分，再分，再分…最后每个组只含一个项的时候，是棵树。记得我们在《[Alg] 排序算法之插入排序》中提到两个算法改进，直接插入算法为减少搜索长度改为两路插入，再改进四路，再分，再分，再分…是棵树；链表插入中，为减小链表长度，再分，再分，再分…是棵树！！！我们好像发现了一个秘密！！！好多数据结进化的终点都是棵树！！！

3、选择树

我们先考虑一个典型的树选择的例子——乒乓球淘汰赛：

$4$个选手至少$4?1=3$场比赛才能决定冠军，但樊振东就是亚军吗？那可不一定，被马龙打败的奥恰洛夫也可能是亚军。所以要加赛，奥恰洛夫对樊振东才能确定亚军。但是，右侧樊振东对水谷隼不用比，我们利用了以前的结果。可以看出，选出冠军马龙后，只需要马龙这个分支的需要重新比较。我们再看一个更大一点的例子。

当取走最大值908后，要比较产生新的最大值只需比较原最大值908所在的分支即可，红色线标出部分，共要比较$\lg N$次（蓝色线段标出）即可在原有基础上重新产生最大值。理解了上面的内容，是时候介绍今天的主角：堆排序。

4、堆排序

堆的定义：定义$K_1,K_2,\dots ,K_N$满足下列条件称之为堆。

$$K_{?j/2?}\ge K_{j}for1\le ?j/2?<j\le N$$

根据堆的定义，知$K_1\ge K_2$，$K_1\ge K_3$，$K_2\ge K_4$。
$$K_1=max(K_1,K_2,\dots ,K_N)$$

根据我们优良的革命传统，举个例子说明：（5 9 1 8 2 6 4 7 3）。设LOC（k）代表位置k。

第一步：$l=4$ LOC（4）8>LOC(8)7和LOC（9）3。满足堆条件。$l=l?1$。

第二步：$l=3$ LOC(3)1<LOC(6)6和LOC（7）4，LOC(3)1与大者LOC（6）6交换。$l=l?1$。

第三步：$l=2$ 无需交换。

第四步：$l=1$ 取$R=5$，与子结点LOC（2）LOC（3）比较，LOC（2）9大，上浮；继续与LOC（2）的子结点LOC（4）LOC（5）比较，LOC（4）8大，上浮至LOC(2)，继续与LOC（4）的子结点LOC(8)LOC(9)比较，LOC(8)大，上浮至LOC（4），无子结点$R=5$放入LOC（8）。第四步详细过程见图示：

见表（前四步为建堆阶段，后面为选择排序阶段）。

算法H：（堆排序）

• H1.[初始化] 置$l\leftarrow ?N/2?+1$，$r\leftarrow N$。
• H2.[减小$l$或$r$] 如果$l>1$，置$l\leftarrow l?1$，$R\leftarrow R_l$，$K\leftarrow K_l$。否则（$l=1$），置$R\leftarrow R_r$，$K\leftarrow K_r$，$R_r\leftarrow R_l$，并置$r\leftarrow r?1$；如果$r=l$，置$R_l\leftarrow R$并结束。
• H3.[准备siftup] 置$j\leftarrow l$。
• H4.[下移] 置$i\leftarrow j$，$j\leftarrow 2j$。如果$j<r$，运行下步H5；如果$j=r$跳转至H6；如果$j>r$跳转至H8.
• H5.[比较子结点] 如果$K_j<K_{j+1}$， 置$j\leftarrow j+1$。
• H6.[与父节点比较] 如果$K\ge K_j$，转至H8。
• H7.[上移] 置$R_i\leftarrow R_j$，并返回H2。
• H8.[存入R] 置$R_i\leftarrow R$，并返回H2.

了解一个算法最有效的方法是拿出纸和笔实际跑一遍，掌握一个算法最有效的方法是编写程序运行一遍。别无它法！

从上面的表格看起来很难让人相信堆排序是一种高效的算法。当$N$较小是确实如此，但随着$N$增大，堆排序优于shell排序。但无论如何比不过快速排序。然而堆排序相对于快排有另一方面的优势，快排的效率只是平均意义上的（概率上说），最坏的情况会退化至$N^2$。堆排序的优势在于，在恶化的情况下也能保证时间复杂度在$O(N\lg N)$。后续我们会讲到归并排序也有这个特性，任何情况下都能保证$N\lg N$，但归并排序要求更多的存储空间。

堆排序边界条件问题

编程实践中一个很大的麻烦就是处理边界条件，很多错误往往也出现在边界条件上，我们看到堆排序算法H4中，有三个条件分支，分别为$j<r$，$j=r$和$j>r$，都是为了防止插入操作越界。可以采用《[Alg]排序算法之插入排序》中提到的第一种应对措施，即在$N+1$处插入$K_{N+1}=?\infty$确保$K\ge K_{N+1}$。为了在程序运行都满足这个条件，我们还要对其它方面进行改造，H2改为$R_{r+1}\leftarrow R_{N+1}$，同样，在$r=1$之后置$R_2\leftarrow R_{N+1}$。这样的设置不同于在插入排序中作用，既不能使代码更简洁，也不能提高代码运行速度，只是减少了处理不当出错的机会。

堆排序的改进

如果你认认真真的拿着纸和笔推演了一遍堆排序算法，你会发现一个问题。第一阶段建堆完成，进入选择阶段，从头部取最大值放在末尾，末尾的值重新插入堆中，这个过程特别长。因为我们每次从堆末尾取值，值都很小，从头部最大值向左侧小值搜索位置且几乎总是$K<K_i$，几乎总是在接近堆末端插入，这要进行大量的对比操作（H6步中）。如何规避这种情况？我们可以采取另一个策略，不进行对比，整体移动数据，直到堆的末尾，然后从尾端向前搜索然后插入。

具体实现如下：

• 删除算法H中的H6，H8改为如下的：
• H8’.[从尾端向前移] 置$j\leftarrow i$，$i\leftarrow ?j/2?$。
• H9‘.[确定插入位置]如果$K\le K_i$或$j=l$，插入$R_j\leftarrow R$并返回H2。否则，置$R_j\leftarrow R$并返回H8‘。

堆插入操作

算法I：（堆插入）

• I.[设置键值] 置$K$为要插入的键值，$j\leftarrow n+1$。
• I.[初始化] 置$i\leftarrow ?j/2?$。
• I.[寻找插入位置] 如果$i=0$或$K_i\ge K$，置$K_j\leftarrow K$，并结束程序。
• I.[移动数据] 置$K_j\leftarrow K_i$，$j\leftarrow i$并返回I2。

删除堆内数据

算法D：（删除堆内数据）

给定位置$s$，删除位置$s$的数据。

• D1.[初始化] $K\leftarrow K_N$，$l\leftarrow 1$，$r\leftarrow N?1$。
• D2.[上浮数据]置$j\leftarrow s$。（后续与算法H相同）
• D3.[下移] 置$i\leftarrow j$，$j\leftarrow 2j$。如果$j<r$，运行下步D4；如果$j=r$跳转至D5；如果$j>r$跳转至D7.
• D4.[比较子结点] 如果$K_j<K_{j+1}$， 置$j\leftarrow j+1$。
• D5.[与父节点比较] 如果$K\ge K_j$，转至D7。
• D6.[上移] 置$R_i\leftarrow R_j$，并返回D3。
• D7.[存入R] 置$R_i\leftarrow R$，并返回D3