简单选择排序

9.3　简单选择排序

简单选择排序又称为直接选择排序,是选择排序中最简单的一种方法。选择排序算法的基本思想是:每次从待排无序记录序列中选出关键字最小的记录插入至已排好序的记录序列的后面,直到n个记录全部插入已排好序的记录序列中。常用的两种选择排序方法是简单选择排序和堆排序。

简单选择排序算法的操作步骤如下。

（1）第一次操作时,整个待排序列是无序的,从待排记录序列中找出关键字最小的记录,并将其与下标为1的记录交换位置。

（2）在第i次操作时,1≤i≤n－1,下标为1、2、…、i－1的记录已经为有序序列,在下标为从i至n的无序记录中找出关键字最小的记录,与下标为i的记录交换位置。

（3）不断重复步骤（2）,每次重复都会从剩余待排记录序列中选出关键字最小的记录排在已经排好序的有序记录序列的最后一个记录之后。经过n－1次的选择和多次交换后,R[1]～R[n]就排成了有序序列,整个排序过程结束。具有n个记录的待排记录序列要做n－1次的选择和交换才能成为有序表。

由上述描述可见,简单选择排序的过程中同样有数据元素的交换。

【算法描述】

外循环用于控制排序次数,内循环用于查找当前待排记录序列中关键字最小的记录。

【算法分析】

（1）稳定性　由于该算法在第i次循环时查找关键字最小的记录的过程中,需要将该记录与下标为i的记录进行位置交换,这种交换的发生,可能会导致关键字相等的两个记录在排序前后相对位置发生改变,故而该算法不稳定。

（2）空间复杂度　在整个算法的执行过程中,使用的辅助存储空间仅为一个,即R[0]所占据的存储空间,故而空间复杂度为O（1）。

（3）时间复杂度　简单选择排序算法的关键字比较次数与记录的初始排列无关。假定整个序列表有n个记录,则总共需要n－1趟的选择；第i（i＝1,2,…,n－1）趟选择具有最小关键字记录所需要的比较次数是n－i－1次,总的关键字比较次数为:

比较次数＝（n－1）＋（n－2）＋…＋1＝n（n－1）/2

而记录的移动次数与其初始排列有关。当这组记录的初始状态是按关键字从小到大有序排列时,每一趟选择后都不需要进行交换,记录的总移动次数为0,这是最好的情况；而最坏的情况是每一趟选择后都要进行交换,一趟交换需要移动记录3次。总的记录移动次数为3（n－1）。所以,简单选择排序的时间复杂度为O（n²）。

【例9－2】　假设有无序记录9个,它们的关键字分别为29＊,18,20,19,38,30,29,31,23,用简单选择排序法进行排序。

初始:29＊　18　20　19　38　30　29　31　23

i＝1:{18}　29＊20　19　38　30　29　31　23【18和29＊交换】

i＝2:{18　19}　20　29＊38　30　29　31　23【19和29＊交换】

i＝3:{18　19　20}　29＊38　30　29　31　23【20不动】

i＝4:{18　19　20　23}　38　30　29　31　29＊【23和29＊交换】

i＝5:{18　19　20　23　29}　30　38　31　29＊【29和38交换】

i＝6:{18　19　20　23　29　29＊}38　31　30【29＊和30交换】

i＝7:{18　19　20　23　29　29＊30}　31　38【38和30交换】

i＝8:{18　19　20　23　29　29＊30　31}　38【31不动】

排序的结果为:18,19,20,23,29,29＊,30,31,38。