选择法排序流程图

2。2  常规的选择法排序

选择法排序还可以细分为三种排序法：第一是简单排序法；第二是树形选择法排序；第三是堆选择排序法。在下面的章节中，将详细分析这三种排序方法，比较它们之间的优缺点。

2。2。1 简单选择法排序

简单选择法排序的基本排序思想是：第i趟排序从序列的后n-i+1（i=1,2,3。。。。。。n-1）个元素中选择一个最小的元素，与该n-i+1个元素的前面那个元素进行位置交换，也就是与第i个位置上元素进行交换，直到i=n-1[4]。

下面通过一个例子来介绍它的执行过程。有这样一组序列{3,6,4,2,11,10}

第一趟排序从全部元素中选出最小的一个，并将它与第一个元素交换位置。初始序列中最小的元素是2，所以将2与第一个元素3交换位置，得到序列{2,6,4,3,11,10}

第二趟排序，从后5个元素中选出最小的元素，并将它与第二个元素交换位置。后5个元素中，3最小，所以将3与第二个元素6交换位置，得到序列：{2,3,4,6,11,10}

第三趟排序，从后4个元素中选出最小的元素是4，此时4正好是第三个元素，所以不需要交换位置，得到序列：{2,3,4,6,11,10}

接下来的每一堂操作都按照这样的“选择--交换”的方法进行。

2。2。2 树形选择法排序

树形选择法排序运行的基本操作是把初始数列的所有元素的关键字，两个两个的互相比较，然后从[(n/2)+1]个较小者的元素之间比较筛选，这样循环，最后选出最小的元素。

下面用一颗含8个叶子节点的完全二叉树来图示树形选择法的选择过程。如图2就是用二叉树从8个元素中比较出最小关键字的流程[4]：

 最小关键字的流程

    在图中，分别把原始数列的八个元素写到树中的八个叶子节点上，左右孩子为任意两个数，根结点中的元素是左右孩子中最小的元素。最深层的孩子比出最小后，根据关系的可传递性，把叶子结点中的最小元素13改为左孩子，再依次比较次深层，这样完全二叉树的根结点的元素就是次小值，如图3。

同理，即能完成对初始序列从小到大的排序。

2。3。3 堆选择法排序文献综述

堆排序的基本原理是每从堆中取出元素时总是按照顺序返回的特点。利用这个特点就可以把给定的初始序列保存到堆中，按顺序取出就能完成排序。堆排序还有一个优点就是从堆中取出一个元素后，保存堆的数组最后会空出一个存储空间，此时把取出的元素保存在最后空出来的空间中就可以，这样在不用使用额外内存的情况下就能完成排序[5]。

(1) 堆的性质

    堆其实可以看成一棵完全二叉树，它的每个非叶子节点都满足如下的性质：

 K[i]<=k[2*i+1]&&K[i]<=k[2*i+2]，通常称为大顶堆；

 K[i]>=K[2*i+1]&&k[i]>=k[2*i+2]，通常被称为小顶堆。

    据上述性质可得，堆顶元素要么是初始序列的最大元素要么是最小元素，而堆顶为最大元素的堆即是大顶堆，堆顶为最小元素的则称为小顶堆。

(2) 堆排序的思想

    根据堆的堆顶元素最大或最小，就简化每次从初始序列中选择最大或最小元素的步骤。

    以大顶堆为例，简单分析堆排序的基本思想：

     把初始序列元素(A1,A2。。。。An)组成大顶堆，把它当成无序区；

     把堆顶元素A[1]与最后一个元素A[n]替换，即把最大的元素放到有序区的第一个，得到新的无序区(A1,A2,。。。。。。An-1)和新的有序区(An),且满足A[1,2。。。n-1]<=A[n]；