下载掌阅APP，畅读海量书库
立即打开
选择排序与冒泡排序的思想基本一致，都是通过比较和交换实现元素的排序。冒泡排序在每次比较时都可能进行交换，而选择排序在比较过程中只保存位置，比较完成后再进行交换。通常情况下，选择排序效率比冒泡排序高。
选择排序的基本思想如下。
（1）与冒泡排序相同，将序列分为无序区和有序区两个部分，无序区存放尚未处理好的数据，有序区存放已经按关键字排序后的数据，有序区在前，无序区在后；
（2）在无序区中，选择一个基准元素（通常是第1个），从头至尾按关键字大小比较基准元素与当前元素，若当前元素小于基准元素，则置基准元素值为当前元素值并保存其下标（通常只保存下标），经过本轮排序之后无序区的最小元素就已经选出，将基准元素与无序区的第一个元素进行交换，将无序区的第一个元素合并到有序区尾部；
（3）重复执行（2），直至无序区只有1个元素为止。
从选择排序的思路中可以看出，每轮排序也需要进行从头至尾比较，而且只能筛选出一个元素，因此有 N 个元素的序列，需要进行 N -1轮排序。与冒泡排序不同的是，每轮排序过程中只进行一次数据交换， N -1轮排序共交换 N -1次，效率比冒泡排序高。
设待排序的无序序列存放于数组array［］中，长度为length，下面给出选择排序的伪代码，如表2-2所示。
表2-2 选择排序的伪代码
假定待排序的数据为｛10，1，35，61，89，36，55｝，7个元素最多需要进行6趟排序。排序的原则是定位无序区中最小元素，将之与无序区首元素进行交换，将交换后的无序区首元素合并至有序区的尾部。
初始时，有序区 d =｛｝，无序区 r =｛10，1，35，61，89，36，55｝。
第一趟排序过程如图2-3（a）所示（纵向箭头表示当前元素，横向箭头为基准元素），排序步骤如下。
图2-3 选择排序的过程
（1）无序区起始位置 i =0，基准元素为10，下标 k =0，只有1个元素，即为最小元素；
（2）当前位置为1，基准元素值10大于当前元素值1，用当前元素下标更新 k ，即 k =1；
（3）当前位置为2，基准元素值1小于当前元素值35，不更新 k ， k 值仍为1；
（4）当前位置为3，基准元素值1小于当前元素值61，不更新 k ；
（5）当前位置为4，基准元素值1小于当前元素值89，不更新 k ；
（6）当前位置为5，基准元素值1小于当前元素值36，不更新 k ；
（7）当前位置为6，基准元素值1小于当前元素值55，不更新 k ；
（8）本轮比较结束，基准元素下标 k =1，起始位置 i =0， k 与 i 不等，需要交换两下标对应的元素，交换后结果为 d =｛1｝， r =｛10，35，61，89，36，55｝。
第二趟排序：起始位置 i =1，比较后基准元素下标 k =1， k 与 i 值相等，无须交换，此时 d =｛1，10｝， r =｛35，61，89，36，55｝。
第三趟排序：起始位置 i =2，比较后基准元素下标 k =2， k 与 i 值相等，无须交换，此时 d =｛1，10，35｝， r =｛61，89，36，55｝。
第四趟排序：起始位置 i =3，比较后基准元素下标 k =5， k 与 i 值不等，需要交换，交换后 d =｛1，10，35，36｝， r =｛89，61，55｝。
第五趟排序：起始位置 i =4，比较后基准元素下标 k =6， k 与 i 值不等，需要交换，交换后 d =｛1，10，35，36，55｝， r =｛61，89｝。
第六趟排序：起始位置 i =5，比较后基准元素下标 k =5， k 与 i 值相等，无须交换，此时 d =｛1，10，35，36，55，61｝， r =｛89｝。
第六趟排序结束后，将无序区最后一个元素89并入有序区，排序过程结束。第二至第六趟的排序过程如图2-3（b）所示。
实现选择排序主体功能的是selection_sort（）函数，main（）函数用于测试选择排序的效果。selection_sort（）函数可实现对部分序列进行升序选择排序，为原地排序算法。
selection_sort（）函数有3个参数，data［］为待排序数组，start为排序区间的起始下标，len为待排序区间的长度。例如，对无序序列｛10，1，35，61，89，36，55｝，从第0个位置开始的5个元素进行选择排序，结果应该为｛ 1 ， 10 ， 35 ， 61 ， 89 ，36，55｝。
selection_sort（）函数对区间数据进行升序排列时，有序区在前，无序区在后。每轮排序过程中，选择无序区的第1个元素（即下标为i的元素）作为基准元素并用min保存其下标，从i+1至区间结尾（start+len-1）逐个进行比较，若某元素data［j］值小于基准元素data［min］，则将其下标j保存到min。一轮比较结束后，若最新基准元素下标min与i不同则需要交换data［min］与data［i］。
实现代码如下。
测试数据及运行结果如下。
①数据总数及各数据：
7
10 1 35 61 89 36 55
②待排序的起始位置及排序长度：
0 7
③运行结果：
1 10 35 36 55 61 89
