选择排序

选择排序的原理与冒泡排序不同，它是指通过每一趟排序过程，从待排序记录中选择出最大（小）的元素，将其依次放在数组的最前或最后端，最终实现数组的排序。接下来，以升序排列为例分步骤讲解选择排序的整个过程，具体如下。

第1步：在数组中选择出最小的元素，将它与0索引元素交换，即放在开头第1位。

第2步：除0索引元素外，在剩下的待排序元素中选择出最小的元素，将它与1索引元素交换，即放在第2位。

第3步：以此类推，直到完成最后两个元素的排序交换，就完成了升序排列。

根据上述步骤，选择排序的流程可使用图1描述。

图1 选择排序流程图（以升序排列为例）

同样以数组{9,8,3,5,2}为例，使用选择排序调整数组顺序的过程如图2所示。

图2 选择排序过程

在图2中，一共经历四轮循环完成数组的排序，每一轮循环的作用如下。

第1轮：循环找出最小值2，将它与第一个元素9进行交换。

第2轮：循环找出剩下的4个元素中的最小值3，将它与第二个元素8交换。

第3轮：循环找出剩下的3个元素中的最小值5，将它与第三个元素8交换。

第4轮：对最后两个元素进行比较，比较后发现不需要交换，则排序完成。

选择排序的代码如例1所示。

例1 selectSort.c

 1  #include <stdio.h>
 2  int main()
 3  {
 4    int arr[5] = { 9,8,3,5,2 };
 5    int i, j, temp, min;
 6    printf("排序之前：");
 7    for (i = 0; i < 5; i++)
 8      printf("%d\t", arr[i]);
 9    for (i = 0; i < 5 - 1; i++)    //外层循环控制比较的轮数
 10   {
 11     min = i;      //暂定i索引处的元素是最小的，用min记录其索引
 12     for (j = i + 1; j < 5; j++)   //内层循环在剩下的元素中找出最小的元素
 13     {
 14       if (arr[j] < arr[min])
 15         min = j;
 16     }
 17     if (min != i)         //交换两个元素的位置
 18     {
 19       temp = arr[i];
 20       arr[i] = arr[min];
 21       arr[min] = temp;
 22     }
 23   }
 24   printf("\n排序之后：");
 25   for (i = 0; i < 5; i++)
 26     printf("%d\t", arr[i]);
 27   return 0;
 28 }

例1的运行结果如图3所示。

图3 例1运行结果