第七章 内排序(4)——选择排序
选择排序
选择排序的主要思想是每一趟从待排序列中选取一个关键字值最小的记录，也即第1趟从n个记录中选取关键字值最小的记录，在第2趟中，从剩下的n-1个记录中选取关键字值最小的记录，直到整个序列中的记录都选完位置。这样，由选取记录的顺序便可得到按关键字值有序的序列。
直接选择排序
直接选择排序(Straight Selection Sort)的基本思想是：在第1趟中，从n个记录中找出关键字值最小的记录与第1个记录交换；在第2趟中，从第2个记录开始的n-1个记录中再选出关键字值最小的记录与第二个记录交换；以此类推，在第i趟中，从第i个记录开始的n-i+1个记录中选出关键字值最小的记录与第i个记录交换，直到整个序列按关键字值有序为止。
假设待排序的 8个记录的关键字序列为{52,39,67,95,70,8,95',25}，直接选择排序过程如下图所示。
假设记录存放在数组r中，开始时，有序序列为空，无序序列为{r[0]，r[1]，…，r[n-1]}。
直接选择排序算法的主要步骤归纳如下：
(1)置i的初值为0。
(2)当i<n-1时，重复下列步骤：
①在无序子序列{r[i+1]，…，r[n-1]}中选出一个关键字值最小的记录r[min]；
②若r[min]不是r[i](即min!=i)，则交换r[i]和r[min]的位置，否则不进行任何交换；
③将i的值加1。
左右滑动或点击查看全图
算法性能分析：
(1)空间复杂度。直接选择排序仅用了一个辅助单元，空间复杂度为O(1)。
(2)时间复杂度。从直接选择排序算法可以看出，整个排序过程中关键字的比较次数与初始关键字的状态无关。算法中每执行一次循环都必须进行一次关键字的比较，其外循环共需执行n-1次，内循环共需执行n-1-i次，因此，总的比较次数为n(n-1)/2。
从算法中也可看到，直接选择排序移动记录的次数较少，最好情况是当待排序记录序列有序时，移动记录次数为0；最坏情况是当待排序记录序列逆序时，移动记录次数为3(n-1)。综上所述，直接选择排序算法的时间复杂度为O(n²)。
(3)算法稳定性。从上图的排序结果可以看出，直接选择排序是一种不稳定的排序算法。
树形选择排序
在直接选择排序中，关键字的总比较次数为n(n-1)/2。实际上，在该方法中，有许多关键字之间进行了不止一次的比较，也就是说，两个关键字之间可能进行了两次以上的比较。能否在选择最小关键字值记录的过程中，把关键字比较的结果保存下来，以便在以后需要的时候直接查看这个比较结果，而不需要再进行比较呢？答案是肯定的。体育比赛中的淘汰制就是每两个对手经过比赛留下胜者继续参加下一轮的淘汰赛，直到最后剩下两个对手进行决赛争夺冠军。
树形选择排序(Tree Selection Sort)的原理与此类似。树形选择排序又称为锦标赛排序，其基本思想是，首先针对n个记录进行两两比较，比较的结果是把关键字值较小者作为优胜者上升到父结点，得到[n/2]个比较的优胜者(关键字值较小者)，作为第1步比较的结果保留下来；然后对这[n/2]个记录再进行关键字的两两比较，如此重复，直到选出一个关键字值最小的记录为止。这个过程可以用一个含有n个叶子结点的完全二叉树来表示，称这种树为胜者树。例如：对于由8个关键字组成的序列{52,39,67,95,70,8,25,45}，使用树形选择排序选出最小关键字值的过程可以用下图(a)所示的完全二叉树来表示。树中的每一个非叶子结点中的关键字均等于其左、右孩子结点中较小的关键字，则根结点中的关键字就是所有叶子结点中的最小关键字。
要求出次小关键字记录，只需将叶子结点中最小的关键字值改为“∞”，然后从该叶子结点开始与其左(或右)兄弟的关键字进行比较，用较小关键字修改父结点关键字，用此方法，从下到上修改从该叶子结点到根结点路径上的所有结点的关键字值，则可得到次小关键字记录，如图(b)所示。以此类推，可依次选出从小到大的所有关键字。
如果开始时记录个数n不是2的k次幂，则将叶子结点数补足到2^k个(k满足2^(k-1)<n<2^k)，这样，胜者树就为一棵满二叉树。
胜者树中的每一个结点可以定义为一个类TreeNode，它包含3个成员变量，分别是data、index和active。其中，成员data的类型定义为顺序表记录结点类RecordNode；成员index定义为int类型，表示此结点在满二叉树中的序号；成员active表示此结点是否要参加选择，1表示参选，0表示不参选。当需将叶子结点关键字改为“∞”时，只需将该结点的active值置为0。胜者树结点类的定义如下：
左右滑动或点击查看全图
胜者树采用顺序存储结构，可用如下数组定义：
TreeNode[] tree; //胜者树结点数组
设待排序的记录序列是{r[0]，r[1]，…，r[n-1]}，胜者树中的结点按满二叉树的结点编号顺序依次存放在顺序表tree中，胜者树中的叶子结点即为待排序的记录。在树形选择排序算法中引入变量leafSize、TreeSize和loadindex分别记录胜者树中的叶子结点个数、胜者树的结点总数和叶子结点在顺序表tree中的起始存放位置。其中，leafSize=n，n为待排序记录的长度，TreeSize=2n-1,loadindex=n-1。上图(a)中胜者树的顺序存储结构示意图如下图所示。
树形选择排序算法的主要步骤归纳如下：
(1)变量初始化，令待排序的结点个数为n，则leafSize=n,TreeSize=2n-1，loadindex=n-1。
(2)将n个待排序结点复制到胜者树的n个叶子结点中，即将r[0..n-1]依次赋值到tree[loadindex..TreeSize-1]中。
(3)构造胜者树：将n个叶子结点的关键字进行两两比较，得到n/2个关键字值较小的结点，保留下来，再将n/2个结点的关键字进行两两比较，得到n/4个较小关键字值的结点，保留下来，依次类推，最后得到根结点为最小关键字值的结点为止。
(4)调整胜者树：先将根结点保存到原数组r中，再把具有根结点值所对应的叶子结点的值改为“最大值”，然后从该叶子结点开始，和其左(或右)兄弟的值进行比较，修改从该叶子结点到根的路径上各结点的值，直到根结点。
(5)重复步骤(4)，直到得到n个结点为止。
左右滑动或点击查看全图
上述算法中的updateTree()方法实现的功能是完成从当前最小关键字的叶子结点开始到根结点路径上的所有结点关键字的修改，即关键字的调整过程，其具体描述如下：
左右滑动或点击查看全图
算法性能分析：
(1)空间复杂度。树形选择排序虽然减少了排序时间，但使用了较多的附加存储空间。对于含有n个记录的顺序表，当n=2^k时，需要使用2n-1个结点来存放胜者树；当2^(k-1)<n<2^k时，需要使用2×2^k-1个结点，总的存储空间需求较大。
(2)时间复杂度。树形选择排序过程可以用一棵满二叉树来表示，其高度为[log2n]+1，其中，为待排序记录个数。除第1次选择具有最小关键字值的记录，需要进行n-1次关键字比较外，调整胜者树所需要的关键字比较次数为O(log2n)，总的关键字比较次数为O(nlog2n）。由于结点的移动次数不会超过比较的次数，所以树形选择排序的时间复杂度为O(nlog2n)。
(3)算法稳定性。树形选择排序是一种稳定的排序算法。
堆排序
树形选择排序存在所需要的辅助空间较多的缺点，为了弥补此缺点，J.Willioms在1964年提出了堆排序(Heap Sort)方法。堆排序是一种重要的选择排序方法，它只需要一个记录大小的辅助存储空间，每个待排序的记录仅占用一个记录大小的存储空间，因此弥补了树形选择排序的弱点。
①堆的定义
假设有n个记录关键字的序列{k0，k1，…，kn-1}，当且仅当满足下列一个公式时，称为堆(Heap)。
前者称为小顶堆，后者称为大顶堆。例如：关键字序列(12,36,24,85,47,30,53,91)是一个
小顶堆；关键字序列(91,47,85,24,36,53,30，16)是一个大顶堆。
采用一个数组存储序列{k0，k1，…，kn-1}，则该序列可以看作是一棵顺序存储的完全二
叉树，那么ki和k2i+1、k2i+2的关系就是双亲与其左、右孩子之间的关系。因此，通常用完全二叉树的形式来直观地描述一个堆。上述两个堆的完全二叉树的表示形式和它们的存储结构如下图所示。
以小顶堆为例，由堆的特点可知，虽然序列中的记录无序，但在小顶堆中，堆顶记录的关键字值是最小的，因此堆排序的基本思想是首先将这n条记录按关键字值的大小建成堆(称为初始堆)，将堆顶元素r[0]与r[n-1]交换(或输出)；然后，将剩下的r[0]..r[n-2]序列调整成堆，再将r[0]与r[n-2]交换，又将剩下的r[0]..r[n-3]序列调整成堆，如此反复，便可得到一个按关键字值有序的记录序列，这个过程称为堆排序。
由上述堆排序的主要思想可知，要实现堆排序需解决以下两个主要问题：
(1)如何将n条记录的序列按关键字值的大小建成初始堆。
(2)将堆顶记录r[0]与r[i]交换后，如何将序列r[0]..r[i-1]按其关键字值的大小调整成一个新堆。
下面从第2个问题开始分别进行讨论。
②筛选法调整堆
由堆的定义可知，堆顶结点的左右子树也是堆，当将堆顶最小关键字值的结点与堆最后一个结点(第n-1个结点)交换后，这个根结点与其左右子树之间可能不符合堆的定义。此时，需要调整根结点与其左右两个堆顶结点之间的大小关系，使之符合堆的定义。其调整方法如下：将根结点r[0]与左、右孩子中关键字值较小的结点进行交换。若与左孩子交换，则左子树堆被破坏，且仅左子树的根结点不满足堆的性质；若与右孩子交换，则右子树堆被破坏，且仅右子树的根结点不满足堆的性质。继续对不满足堆性质的子树进行上述交换操作，直到叶子结点或者堆被建成为止。这种从堆顶到叶子结点的调整过程也称为“筛选”。例如：下图(a)为一个堆，当根结点与最后一个结点交换后，得到如图(b)所示的完全二叉树，它不满足堆的定义，为此，需要比较根结点63的左右孩子结点关键字值的大小，将小者18与根结点63交换，得到如图(c)所示的完全二叉树，其中以63为根结点的子树又不满足堆的定义，再对此子树作上述同样的调整，可得到如图(d)所示的完全二叉树，此时，完全二叉树已满足堆的定义，则整个筛选过程结束。
假设待调整成堆的完全二叉树存放在r[low..high]中，实现上述过程的调整堆算法的主要步骤归纳如下：
(1)置初值i=low，j=2×i+1，temp=r[i]。
(2)当j<high时，重复下列操作：
①若j<high-1且r[j].key>r[j+1].key，则j++。
②若temp.key>r[j].key，则r[i]=r[j]，i=j，j=2*i+1，否则j=high+1。
(3)r[i]=temp。
左右滑动或点击查看全图
③建初始堆
为一个无序序列建堆的过程就是对完全二叉树从下往上反复“筛选”的过程。因为完全二叉树的最后一个非叶子结点的编号是[n/2]-1，所以“筛选”只需从编号为[n/2]-1的结点开始。例如：下图(a)是无序序列{33,25,46,13,58,95,18,63}所对应的完全二叉树，则“筛选”从编号为3的结点开始，首先考察以编号为3的结点13为根结点的子树，由于13<63，满足堆定义，故无须进行筛选；接着考察以编号为2的结点46为根结点的子树，由于46>18，需对结点46进行“筛选”，“筛选”后的状态如图(b)所示；再考察以编号为1的结点25为根结点的子树，“筛选”后的状态如图(c)所示；最后考察以编号为0的结点33为根结点的二叉树，“筛选”后的状态如图(d)所示。此时，即得到一个初始堆。
④堆排序
将一个无序序列构造成堆，如下图(a)所示；然后将堆顶次小值结点与最后第2个(第n-2个结点)交换，再调整构造成第3个堆，如图(c)所示，如此反复，直至整个序列有序，堆排序完成，如图(d)所示。
由上述分析可见，堆排序的主要步骤归纳如下：
(1)将待排序记录{r[0]，r[1]，…，r[n-1]}建成为一颗完全二叉树。
(2)将下标为[n/2]-1的记录作为开始调整的子树的根结点。
(3)找出此结点的两个孩子结点中的关键字值较小者，将其与父结点比较，若父结点的关键字值较大，则交换，然后以交换后的子结点作为新的父结点，重复此步骤，直到没有子结点为止。
(4)以步骤(3)中原来的父结点所在位置往前推一个位置，作为新的调整的子树的根结点。继续重复步骤(3)，直到调整到树根。此时初始堆已形成。
(5)堆建成后，将树根与二叉树的最后一个结点交换后，再将最后一个结点输出(即输出的是原本的树根)，然后比较根结点的两个子结点，若左子结点的关键字值较小，则调整左子树；反之，调整右子树，使它再成为堆。
(6)重复步骤(5)，直到二叉树仅剩下一个结点为止。
堆排序的算法分为两个部分，一部分通过一个循环构造一个初始堆；另一部分将堆顶记录与第i个记录对调(i从n-1递减到1)，再调用筛选算法，反复构造新堆以便进行堆排序。
算法性能分析：
(1)空间复杂度。堆排序需要一个记录的辅助存储空间，空间复杂度为O(1)。
(2)时间复杂度。假设堆排序过程中产生的二叉树的树高为k，则k=[log2n]+1。从树的根结点到叶子结点的筛选，关键字的比较次数至多为2(k-1)次，交换记录至多为k次。所以，在建好堆后，排序过程中的筛选次数不超过2([log2(n-1)]+[log2(n-2)]+···+[log22])<2nlog2n。由于建初始堆时的比较次数不超过4n次，因此，在最坏情况下，堆排序算法的时间复杂度为O(nlog2n)。
(3)算法稳定性。堆排序算法具有较好的时间复杂度，是一种效率非常高的排序算法，但从上图的排序结果可以看出，它不满足稳定性要求，即堆排序算法是一种不稳定的排序算法，不适合用于求解对稳定性有严格要求的排序问题。