11.3　选择法排序

选择法排序同样是一种相对较为简单和容易实现的排序方法，下面介绍这种排序的实现方法。首先同样需要确定排序的规则，然后以给定排序数组的第一个数为基准，将其后的数依次与其进行比较，根据排序规则来确定是否交换两个数。

在此同样以升序为例来讲解。

第一轮：以第一个数为基准，从第二个数开始，将后面的数据与第一个数一一进行对比，如果有比第一个数还小的，那么就将第一个数与该数进行交换，直到比较到最后一个数为止。

第二轮：由于第一轮比较结束后，第一个数是给定排序数中最小的数，因此第二轮以第二个数为基准，将其后的数依次与其进行比较操作，满足条件则进行交换，直到比较到最后一个数为止。

重复以上操作，直到以倒数第二个数为基准，进行最后一轮比较操作为止。分析下面的实现代码。

include＜stdio.h＞

void sort（int a[]，int n）

{

int i,j，k,tmp；

for（i=0；i＜n-1；i++）

{

k=i；

for（j=i+1；j＜n；j++）

{

if（a[j]＜a[k]）

k=j；

}

if（k！=i）

{

tmp=a[i]；

a[i]=a[k]；

a[k]=tmp；

}

}

}

int main（void）

{

int i；

int a[5]={32，12，56，78，43}；

printf（"排序前\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

sort（a，5）；

printf（"\n排序后\n"）；

for（i=0；i＜5；i++）

printf（"%d\t"，a[i]）；

return 0；

}

运行结果：

排序前

32 12 56 78 43

排序后

12 32 43 56 78

对比排序前后的打印结果发现，成功地实现了通过选择排序法对给定的数组进行排序操作。下面先通过图11-4来了解第一轮的比较操作。

图　11-4　第一轮的比较操作

接下来在第一轮比较结果的基础上进行第二轮比较操作，如图11-5所示。

图　11-5　第二轮的比较操作

分析上面的比较结果，第二轮比较结果与第一轮的比较结果完全一致，没有将第二个数与接下来的任何一个数进行交换操作。下面通过图11-6来了解在此基础上进行的第三轮的比较操作。

图　11-6　第三轮的比较操作

在第三轮的比较操作中，由于第5个数比第三个数要小，因此进行了一次交换操作。接下来再来通过图11-7看看第四轮的比较操作。

图　11-7　第四轮的比较操作

由上面的比较结果可知，这时已经成功地实现了对数组的排序。