选择排序（Selection sort）是一种简单直观的排序算法。
它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。
比如说现在有个数组[6,3,5,7,0]，对其从小到大进行排序，那么选择排序的过程应该是这样的：
从这个过程中可以看出选择排序的一些规则：
- 选择排序一共有
数组大小-1轮。 - 而在每一轮的排序中，又会有一个小循环，规则是：
- 先假定当前的这个数是最小的。
- 然后与后面的每个数进行比较，如果发现有更小的数，重新确定最小的数，并得到这个数的下标。
- 继续遍历到数组最后，于是确定出本轮的最小数以及它的下标。
- 进行位置交换
推导过程的代码
将数组[101,34,119,1]从小到大进行排序。
package sort; import java.util.Arrays; public class SelectSorting { public static void main(String[] args) { int [] arr = {101,34,119,1}; selectSort(arr); } // 选择排序 public static void selectSort(int[] arr) { // 原始数组[101,34,119,1] // 第一轮排序 int minIndex = 0; int min = arr[0]; //假定第一个元素就是最小值 for (int j = 0 + 1; j < arr.length; j++) { if (min > arr[j]) { // 比较，如果是true，那么说明min不是最小值 min = arr[j]; // 重置最小值 minIndex = j; // 重置minIndex } } // 最小值与arr[0]交换位置 if (minIndex != 0) { // 优化点：如果第一个用于比较的元素就是最小值，就不用交换位置 arr[minIndex] = arr[0]; arr[0] = min; } System.out.println("第一轮之后："); System.out.println(Arrays.toString(arr)); // 第一轮之后 [1, 34, 119, 101] // 第二轮排序 minIndex = 1; min = arr[1]; //假定第二个元素就是最小值 for (int j = 1 + 1; j < arr.length; j++) { if (min > arr[j]) { // 比较，如果是true，那么说明min不是最小值 min = arr[j]; // 重置最小值 minIndex = j; // 重置minIndex } } // 最小值与arr[1]交换位置 if (minIndex != 1) { arr[minIndex] = arr[1]; arr[1] = min; } System.out.println("第二轮之后："); System.out.println(Arrays.toString(arr)); // 第二轮之后 [1, 34, 119, 101] // 第三轮排序 minIndex = 2; min = arr[2]; //假定第三个元素就是最小值 for (int j = 2 + 1; j < arr.length; j++) { if (min > arr[j]) { // 比较，如果是true，那么说明min不是最小值 min = arr[j]; // 重置最小值 minIndex = j; // 重置minIndex } } // 最小值与arr[2]交换位置 if (minIndex != 2) { arr[minIndex] = arr[2]; arr[2] = min; } System.out.println("第三轮之后："); System.out.println(Arrays.toString(arr)); // 第三轮之后 [1, 34, 101, 119] } }
根据推导过程发现的规律，转化成最终的代码：
package sort; import java.util.Arrays; public class SelectSorting { public static void main(String[] args) { int [] arr = {101,34,119,1}; selectSort(arr); System.out.println("排序后："); System.out.println(Arrays.toString(arr)); } // 选择排序 public static void selectSort(int[] arr) { // 原始数组[101,34,119,1] for (int i = 0; i < arr.length; i++) { int minIndex = i; int min = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { // 比较，如果是true，那么说明min不是最小值 min = arr[j]; // 重置最小值 minIndex = j; // 重置minIndex } } if (minIndex != i) { // 优化点：如果第一个用于比较的元素就是最小值，就不用交换位置 arr[minIndex] = arr[i]; arr[i] = min; } } } }
如果要从大到小进行排序，很简单，只要改动这里即可：
...... if (min < arr[j]) { // 大于号改成小于号 min = arr[j]; minIndex = j; } ......
从过程推导再到最后形态，还是比上来直接看2层for循环要好理解的多了。
