选择排序：原理、实现与性能分析
选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是通过不断寻找剩余元素中的最小值（或最大值）并将其放置在正确位置来完成排序。
选择排序是一种原地比较排序算法，其基本操作是在未排序序列中找到最小（或最大）元素，然后将其存放到序列的起始位置。接着，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。依此类推，直到所有元素均排序完毕。
与 冒泡排序 频繁交换元素不同，选择排序每轮只进行一次元素交换，这使得它在某些情况下比其更高效。
1、工作原理与步骤
选择排序的工作过程可以分为以下步骤：
从待排序序列的起始位置开始，假设该位置的元素为最小值
遍历剩余未排序的元素，寻找真正的最小值
将找到的最小值与序列起始位置的元素交换
移动起始位置到下一个未排序元素
重复步骤 1-4，直到所有元素都被排序
简而言之，选择排序就是不断 "选择" 剩余元素中的最值并将其放到正确位置的过程。
1.1 选择排序伪代码
function selectionSort(arr):
n = length(arr)
// 外层循环控制已排序部分的末尾位置
for i from 0 to n-2:
// 假设当前位置是最小值所在位置
minIndex = i
// 寻找剩余未排序元素中的最小值
for j from i+1 to n-1:
if arr[j] < arr[minIndex]:
minIndex = j
// 将找到的最小值与当前位置元素交换
if minIndex != i:
swap arr[i] and arr[minIndex]
return arr1.2 可视化理解
选择排序的过程可以通过动画直观展示：
整个序列分为已排序和未排序两个部分，有明显的分界
每一轮都会在未排序部分高亮显示当前最小值的查找过程
找到最小值后，会有一次交换操作将其放到已排序部分的末尾
已排序部分通常用不同颜色标记，随着排序进行逐渐扩大
与冒泡排序相比，选择排序的交换操作明显更少，每轮只进行一次交换，这是其特点之一。
2、算法实现
2.1 Java 实现
public class SelectionSort {
// 基本选择排序实现（升序）
public static void selectionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return; // 数组为空或只有一个元素，无需排序
}
int n = arr.length;
// 外层循环：已排序元素的末尾位置
for (int i = 0; i < n - 1; i++) {
// 寻找未排序部分的最小值索引
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 更新最小值索引
}
}
// 将找到的最小值与当前位置元素交换
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
// 优化版：同时寻找最小值和最大值，减少遍历次数
public static void optimizedSelectionSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int left = 0;
int right = arr.length - 1;
while (left < right) {
// 寻找最小值索引
int minIndex = left;
// 寻找最大值索引
int maxIndex = right;
// 确保初始值正确
if (arr[minIndex] > arr[maxIndex]) {
minIndex = right;
maxIndex = left;
}
// 遍历寻找最小值和最大值
for (int i = left + 1; i < right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
} else if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 交换最小值到左侧
if (minIndex != left) {
int temp = arr[left];
arr[left] = arr[minIndex];
arr[minIndex] = temp;
// 如果最大值在左侧位置，需要更新其索引
if (maxIndex == left) {
maxIndex = minIndex;
}
}
// 交换最大值到右侧
if (maxIndex != right) {
int temp = arr[right];
arr[right] = arr[maxIndex];
arr[maxIndex] = temp;
}
// 缩小排序范围
left++;
right--;
}
}
}2.2 Go 实现
package main
// 基本选择排序实现（升序）
func selectionSort(arr []int) {
if arr == nil || len(arr) <= 1 {
return // 数组为空或只有一个元素，无需排序
}
n := len(arr)
// 外层循环：已排序元素的末尾位置
for i := 0; i < n-1; i++ {
// 寻找未排序部分的最小值索引
minIndex := i
for j := i + 1; j < n; j++ {
if arr[j] < arr[minIndex] {
minIndex = j // 更新最小值索引
}
}
// 将找到的最小值与当前位置元素交换
if minIndex != i {
arr[i], arr[minIndex] = arr[minIndex], arr[i]
}
}
}
// 优化版：同时寻找最小值和最大值，减少遍历次数
func optimizedSelectionSort(arr []int) {
if arr == nil || len(arr) <= 1 {
return
}
left := 0
right := len(arr) - 1
while left < right {
// 寻找最小值索引
minIndex := left
// 寻找最大值索引
maxIndex := right
// 确保初始值正确
if arr[minIndex] > arr[maxIndex] {
minIndex = right
maxIndex = left
}
// 遍历寻找最小值和最大值
for i := left + 1; i < right; i++ {
if arr[i] < arr[minIndex] {
minIndex = i
} else if arr[i] > arr[maxIndex] {
maxIndex = i
}
}
// 交换最小值到左侧
if minIndex != left {
arr[left], arr[minIndex] = arr[minIndex], arr[left]
// 如果最大值在左侧位置，需要更新其索引
if maxIndex == left {
maxIndex = minIndex
}
}
// 交换最大值到右侧
if maxIndex != right {
arr[right], arr[maxIndex] = arr[maxIndex], arr[right]
}
// 缩小排序范围
left++
right--
}
}3、算法优化
标准选择排序可以通过以下方式进行优化：
双向选择排序：每轮同时寻找最小值和最大值，分别放到序列的两端，减少一半的遍历次数
标记交换位置：只有当找到的最小值不在当前位置时才进行交换，避免不必要的交换操作
对于近乎有序的数据：可以记录上次最小值的位置，作为下次查找的起点
这些优化虽然不能改变选择排序的时间复杂度级别，但能在一定程度上提高实际运行效率。
4、复杂度分析
时间复杂度：
最坏情况：O (n²)
最好情况：O (n²)
平均情况：O (n²)
选择排序的时间复杂度不受输入数据的有序程度影响，因为无论数据初始状态如何，它都需要完成所有元素的比较。
空间复杂度：O (1)，属于原地排序算法，只需要一个临时变量用于交换元素
稳定性：选择排序是不稳定的排序算法。例如，对于序列 [2, 2, 1]，第一个 2 会与 1 交换，导致两个 2 的相对顺序发生改变。
5、与其他排序算法的比较
选择排序与同为 O (n²) 时间复杂度的冒泡排序和插入排序相比：
选择排序的交换次数更少（每轮最多一次）
选择排序的比较次数与冒泡排序相当，但多于插入排序
选择排序不稳定，而冒泡和插入排序稳定
选择排序的性能受数据初始状态影响较小
6、适用场景
选择排序适用于以下场景：
数据量较小的情况：对于小规模数据，O (n²) 的时间复杂度可以接受
硬件资源受限的环境：选择排序空间复杂度为 O (1)，内存占用少
交换操作成本较高的场景：由于选择排序交换次数少，适合元素交换成本高的情况
在实际开发中，对于大规模数据，通常会选择快速排序、归并排序等更高效的算法。
- 感谢你赐予我前进的力量
-
微信
- 支付宝
