选择排序：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
与冒泡排序相比，选择排序的交换次数较少，但比较次数相同
基本思想
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。
实现逻辑
- 第一轮从下标为 1 到下标为 n-1 的元素中选取最小值，若小于第一个数，则交换
- 第二轮从下标为 2 到下标为 n-1 的元素中选取最小值，若小于第二个数，则交换
- 依次类推下去……
动图演示
注：红色表示当前最小值，黄色表示已排序序列，绿色表示当前位置。
java
public static void selectionSort(int[] arr) {
// 如果数组为空或长度小于2，则直接返回，无需排序
if (arr == null || arr.length < 2) return;
// 外层循环，从第一个元素开始遍历到倒数第二个元素
// 每一次循环都将选出一个最小元素并将其交换到当前位置
for (int i = 0; i < arr.length - 1; i++) {
// 初始化最小元素的索引为当前位置
int minIndex = i;
// 内层循环，从当前位置的下一个元素开始遍历到最后一个元素
// 找出最小元素的索引
for (int j = i + 1; j < arr.length; j++) {
// 如果当前元素比最小元素小，则更新最小元素的索引
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
// 交换当前位置和最小元素的位置
swap(arr, i, minIndex);
}
}
// 交换数组中两个元素的位置
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
文档信息
- 本文作者：carpe
- 本文链接：https://carpedx.com/wiki/algorithm-selection-sort/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）