8.4.1　简单选择排序

1.简单选择排序的基本思想

简单选择排序的基本思想是：通过n－1次排序操作，每一趟在n－i＋1（i＝1，2，3，…，n－1）个记录中选取关键字最小的记录作为有序序列中的第i个记录，并和第i（1≤i≤n）个记录交换之。

它的具体实现过程为：

（1）将整个记录序列划分为有序区域和无序区域，有序区域位于最左端，无序区域位于右端，初始状态有序区域为空，无序区域含有待排序的所有n个记录。

（2）设置一个整型变量index，用于记录在一趟的比较过程中，当前关键字值最小的记录位置。开始将它设定为当前无序区域的第一个位置，即假设这个位置的关键字最小，然后用它与无序区域中其他记录进行比较，若发现有比它的关键字还小的记录，就将index改为这个新的最小记录位置，随后再用a［index］.key与后面的记录进行比较，并根据比较结果，随时修改index的值，一趟结束后index中保留的就是本趟选择的关键字最小的记录位置。

（3）将index位置的记录交换到无序区域的第一个位置，使得有序区域扩展了一个记录，而无序区域减少了一个记录。

不断重复（2）和（3），直到无序区域剩下一个记录为止。此时所有的记录已经按关键字从小到大的顺序排列就位。

2.直接选择排序算法

简单选择排序的整体结构应该为：

下面我们进一步分析一下“第i趟简单选择排序”的算法实现。

（1）初始化：假设无序区域中的第一个记录为关键字值最小的元素，即将index＝i；

（2）搜索无序区域中关键字值最小的记录位置：

（3）将无序区域中关键字最小的记录与无序区域的第一个记录进行交换，使得有序区域由原来的i－1个记录扩展到i个记录。

算法8.9 直接选择排序

排序过程如图8－10所示。

图8－10 排序过程示例

3.简单选择排序算法的复杂度

直接选择排序的比较次数和记录的初始顺序无关。显然，对L.r［1..n］中记录进行简单选择排序的算法为：令i从1至n－1，进行n－1趟选择操作，如算法8.8所示。容易看出，简单选择排序过程中，所需进行记录移动的操作次数较少，其最小值为“0”，最大值为3（n—1）。然而，无论记录的初始排列如何，所需进行的关键字间的比较次数相同，均为n（n－1）／2。因此，虽然移动次数较少，但比较次数仍多，总的时间复杂度也是O（n2）；没有附加单元（仅用到1个temp），空间效率为O（1）；属于不稳定排序。

那么，能否加以改进呢？

从上述可见，选择排序的主要操作是进行关键字间的比较，因此改进简单选择排序应从如何减少“比较”出发考虑。显然，在n个关键字中选出最小值，至少进行n－1次比较，然而，继续在剩余的n－1个关键字中选择次小值就并非一定要进行n－2次比较，若能利用前n－1次比较所得信息，则可减少以后各趟选择排序中所用的比较次数。