1. 什么是选择排序？
首先贴上从wiki上弄下来的关于选择排序的定义。
选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
更加直白的解释是，每次都从数组中选出最大或者最小的元素，然后放到数组的左边。
2. 选择排序的过程展示
老规矩，我们还是通过动图来看一下选择排序的过程。以下的gif来自于wiki。
然后我们再通过我制作的gif，配上数据再了解一下过程。假设我们的待排序数组还是[5, 1, 3, 7, 6, 2, 4]。
3. 选择最小值的算法
我们使用Java来实现最常见的，选择最小值的选择排序，其代码如下。
private voidt(int[] arr) { int min; int minIndex; for (int i = 0; i < arr.length - 1; i++) { min = arr[i]; minIndex = -1; for (int j = i; j < arr.length; j++) { if (arr[j] < min) { min = arr[j]; minIndex = j; } } // 排序结束 交换位置 if (minIndex != -1) { exchange(arr, i, minIndex); } }}private void exchange(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};selectionSort(arr);System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]假设数组的长度为7，那么算法就需要进行6轮。如果数组的长度为n，则算法需要进行n - 1轮。
每一轮，算法都会从剩下的待排序元素中，选出最小的元素，并将其与当前数组下标为i也就是有序序列的起始位置的元素交换。这样一来，经过反复的排序，最终形成有序数组。
4. 选择最大值的算法
上面实现了选择最小值的代码，接下来我们继续实现选择最大值的代码。
private void selectionSort(int[] arr) { int max; int maxIndex; for (int i = 0; i < arr.length - 1; i++) { max = Integer.MIN_VALUE; maxIndex = -1; for (int j = 0; j < arr.length - i; j++) { if (max < arr[j]) { max = arr[j]; maxIndex = j; } } // 排序结束 交换位置 if (maxIndex != -1) { exchange(arr, maxIndex, arr.length - i - 1); } }}private void exchange(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};selectionSort(arr);System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]这个思想与选择最小值的算法完全一样，只不过是选择了最大值，每次都将剩余序列的最大值放到数组的有序序列的最左边。
那么到此，选择排序最常见的两种写法我们都已经实现了。有的兄弟可能会想，这篇博客是不是结束了。其实我们可以从上面两个算法中想到可以优化的点。
既然我们有两个选择，一种选择最小值，另外一种选择最大值。那么我们为什么不同时进行两个操作呢？
下面我们就来实现这种算法。
5. 同时选择最大值和最小值
private void selectionSort(int[] arr) { int min; int max; int minIndex; int maxIndex; for (int i = 0; i <= arr.length / 2; i++) { min = Integer.MAX_VALUE; max = Integer.MIN_VALUE; minIndex = -1; maxIndex = -1; for (int j = i; j < arr.length - i; j++) { if (arr[j] < min) { min = arr[j]; minIndex = j; } if (arr[j] > max) { max = arr[j]; maxIndex = j; } } // 排序结束 交换位置 if (minIndex != -1) { if (maxIndex == i) { maxIndex = minIndex; } exchange(arr, i, minIndex); } if (maxIndex != -1) { exchange(arr, maxIndex, arr.length - 1 - i); } }}private void exchange(int arr[], int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}int[] arr = new int[]{5, 1, 3, 7, 6, 2, 4};selectionSort(arr);System.out.println(Arrays.toString(arr)); // [1, 2, 3, 4, 5, 6, 7]因为选择最大值和最小值同时进行，相对于上面两种算法，同时选择算法在执行次数上比前两种算法减少了50%。
在运行时间上相对于选择最小值和最大值分别减少了39.22%和62.20%。
6. 总结
以下是对同一个长度为10000的随机乱序数组使用三种算法的情况。
| [0 - 10000] 的乱序数组 | 取最小值 | 取最大值 | 同时取最大值最小值 |
|---|---|---|---|
| 100次平均执行时间（ms） | 51 | 82 | 31 |
| 执行次数（次） | 50004999 | 50004999 | 25005000 |
最后我们看一下选择排序算法的时间复杂度。
- 最好的情况为O(n ^ 2). 即使整个数组都是有序的，选择排序也会执行完选择最大值或者最小值的过程，只是不会去进行元素交换。
- 最坏的情况为O(n ^ 2). 同上，会执行完选择最大值或者最小值的过程，并且每次都需要进行元素交换。
其空间复杂度为O(n)，上面三种算法都属于原地排序算法，除了交换元素使用了一个辅助空间之外，没有额外申请空间，同时选择排序是不稳定排序。
往期文章：
- 你知道和你不知道的冒泡排序
- 聊聊微服务集群当中的自动化工具
- go源码解析-Println的故事
- 用go-module作为包管理器搭建go的web服务器
- WebAssembly完全入门——了解wasm的前世今身
- 小强开饭店-从单体应用到微服务
相关：
- 微信公众号： SH的全栈笔记（或直接在添加公众号界面搜索微信号LunhaoHu）