简介

从元素序列中找出最大（或最小）的那个元素，然后与末尾的元素进行交换位置，执行完一轮排序后，最末尾的元素就是交换之后最大的元素，如果继续下一轮排序，则忽略第一轮排序过最大的那个元素，然后继续寻找下一个最大的元素。

  • 特点：
    • 寻找元素列中的最小或最大值，然后和最左侧的元素交换位置。
    • 已经排序过的最小或最大值如果在最左端，则不进行任何的操作
    • 选择排序不稳定。

图解

例如给出下图中一组数字。

image.png
对数字1-5进行排序。

  • 根据选择排序算法，首先找到了最小的值 1

image.png

  • 在找到了最小值1后，就会与序列最左边的 5 进行位置交换

image.png

至此第一轮排序操作就完成了，在将最小值归位于左侧之后，不需要再对其做任何操作，因为最小值已经在左侧。

  • 继续往下排序，最小值是2，确定的是2已经在最左侧，所以不需要任何操作，再往后找到了最小值3。

image.png

这样第二轮的操作就完成了，3不比2小，需要调换位置的就是5元素，而4恰好又比5小，由此完成了排序过程。

代码实现（Java）

根据正序的方式实现，挑出最小元素放到最左侧。

  1. package sort.example.select;
  3. import java.util.Arrays;
  4. /**
  5.  *  选择排序
  6.  */
  7. public class Selection {
  8.     public static void main(String[] args) {
  10.         int[] arrays = { 6,1,7,8,9,3,5,4,2 };
  11.         System.out.println("排序前" + Arrays.toString(arrays));
  13.         int count;  //用于保存临时变量
  14.         int min; // 交换i变量的索引值
  15.         for (int i = 0; i < arrays.length -1; i++) { // 控制等待排序的元素列
  16.             min = i; // 将i索引赋值给临时变量min
  17.             for (int j = i + 1; j < arrays.length ; j++) { // 控制排序的次数
  18.                 if (arrays[j] < arrays[min]) { // 如果j下标的值比min小
  19.                     min = j; // 交换索引下标
  20.                 }
  21.             }
  22.             if (min != i) { // 如果min 不等于i索引再进行下面交换操作。
  23.                 count = arrays[min]; // 将最小值赋给临时变量count
  24.                 arrays[min] = arrays[i]; // 进行元素位置的交换
  25.                 arrays[i] = count; // 将count赋值给arrays[i]
  26.             }
  27.         }
  28.         System.out.println(Arrays.toString(arrays)); // 打印数组
  29.     }
  30. }
  • 打印结果

image.png

根据倒序的方式实现，挑出最大元素放到最左侧。

  1. package sort.example.select;
  3. import java.util.Arrays;
  4. /**
  5.  *  选择排序
  6.  */
  7. public class Selection {
  8.     public static void main(String[] args) {
  10.         int[] arrays = { 6,1,7,8,9,3,5,4,2 };
  11.         System.out.println("排序前" + Arrays.toString(arrays));
  13.         int count;  
  14.         int max; 
  15.         for (int i = 0; i < arrays.length; i++) {
  16.             max = i; 
  17.             for (int j = i + 1; j < arrays.length ; j++) {
  18.                 if (arrays[j] > arrays[max]) { // 实现倒序排序，如果j大于记录的max值则交换位置
  19.                     min = j;
  20.                 }
  21.             }
  22.             if (max != i) {
  23.                 count = arrays[max];
  24.                 arrays[max] = arrays[i]; 
  25.                 arrays[i] = count; 
  26.             }
  27.         }
  28.         System.out.println(Arrays.toString(arrays)); 
  29.     }
  30. }

image.png

Debug分析

  1. 通过打断点的方式分析程序运行的流程。
  • 在外层 for 循环打上一个断点

image.png
可以看到循环默认值为数组中定义的元素，下面点击 Step Over 进行下一步。
image.png

这一步是将循环的i的元素索引值交给min临时变量。然后接着 Step Over 下一步分析

image.png
这一步来到了内层 for 循环，可以看到i的索引下标仍然为0，也就是对应着元素6的值。

  • 下面继续 Step Over ，进入到 if 语句判断。

image.png

此时 j 变量的下标为1，也就是对应着元素值1号，而 min 变量被 i 赋值，所以其下标为1，也就是对应着元素6

  • 继续下一步，来到下标交换的部分。

image.png

将 j 的下标值和 min （此时min变量已经被i赋值）进行交换，1代表着元素1，0代表着元素6

此时的最小值已经被 min 变量记录，继续下一步会回到内层循环继续寻找有没有比 min 还小的数。
image.png

继续往下寻找最小值，判断2号索引元素是否小于被记录的 min 1号元素，如果小于则继续交换，没有则继续内循环其它元素，当前2号元素为7，1号元素为1。

可以看到在这一步里元素值中没有比1还小的数了，依次比较到最后一个元素为止，跳出循环进入下一个判断，然后进行位置的排序。
image.png

图上为查找的最后一个元素，发现也不满足大于 min 的条件，那么跳入下一个 if 判断

image.png

这一行判断min是否是最小的元素，如果是最小元素则进行下面的位置交换。

  • 首先先将最小值赋给 count 变量。

image.png

  • 然后进行 1 和 0 号下标元素的位置交换

image.png

  • 最后再将 count 的值赋给 i 号元素，此时0和1下标的值都变为了6，但其索引下标对应的值不变

image.png

通过这最后一步的交换即完成了对最小值 1 和左边 6 元素进行位置的交换。此时再进行下一步可以看到元素位置的变换。

image.png
到这里就完成了第一轮排序的流程，步骤依次类推，核心在于每一次内循环都会找到最小值，然后将下标索引交换给 min 变量保存，每找到一个最小的值都如此重复，直到没有更小的值为止。再紧接着就是跳出循环进行判断和值的互换。