引言
选择排序（Selection Sort）是计算机科学中最基础、最直观的比较排序算法之一。它的核心思想非常朴素：在每一轮遍历中，从待排序区间里找出最小（或最大）的元素，将其放到已排序区间的末尾。尽管选择排序的时间复杂度并非最优，但它实现简单、空间复杂度极低，且排序过程中交换次数最少，这些特性使其在特定场景下仍具实用价值。本文将用Java完整实现选择排序，深入剖析其原理，并与其他基础排序算法进行性能对比。
算法原理
选择排序的算法步骤如下：
- 将数组分为已排序区间和未排序区间，初始时已排序区间为空。
- 从未排序区间中找到最小元素的索引。
- 将找到的最小元素与未排序区间的第一个元素交换位置。
- 已排序区间扩展一位，未排序区间缩小一位。
- 重复步骤2-4，直到未排序区间只剩一个元素。
对于一个长度为 n 的数组，选择排序需要进行 n-1 轮选择，每轮选择需要扫描剩余未排序元素。
核心Java实现
基础版本
/**
* 选择排序基础实现
* 时间复杂度：O(n²)，空间复杂度：O(1)
*/
public class SelectionSort {
/**
* 对整型数组进行升序排序
* @param arr 待排序数组
*/
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
// 外层循环：控制已排序区间的右边界
for (int i = 0; i < n - 1; i++) {
// 假设当前位置i是最小值的位置
int minIndex = i;
// 内层循环：在未排序区间[i+1, n-1]中寻找真正的最小值
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果最小值不在位置i，则交换
if (minIndex != i) {
swap(arr, i, minIndex);
}
}
}
/**
* 交换数组中两个位置的元素
*/
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11, 90, 33, 77};
System.out.println("排序前: " + arrayToString(arr));
sort(arr);
System.out.println("排序后: " + arrayToString(arr));
}
private static String arrayToString(int[] arr) {
StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]);
if (i < arr.length - 1) sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
泛型版本（支持Comparable对象）
import java.util.Arrays;
/**
* 选择排序泛型实现，支持任意Comparable类型
*/
public class GenericSelectionSort {
/**
* 对Comparable数组进行升序排序
*/
public static <T extends Comparable<T>> void sort(T[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
// 使用compareTo进行元素比较
if (arr[j].compareTo(arr[minIndex]) < 0) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr, i, minIndex);
}
}
}
private static <T> void swap(T[] arr, int i, int j) {
T temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
String[] fruits = {"banana", "apple", "cherry", "date", "elderberry"};
System.out.println("排序前: " + Arrays.toString(fruits));
sort(fruits);
System.out.println("排序后: " + Arrays.toString(fruits));
Integer[] numbers = {5, 2, 8, 1, 9, 3};
sort(numbers);
System.out.println("数字排序: " + Arrays.toString(numbers));
}
}
双向选择排序（每次找出最大和最小）
/**
* 双向选择排序优化版
* 每轮同时找出未排序区间的最大值和最小值
* 交换次数从O(n)减少到约O(n/2)
*/
public class BidirectionalSelectionSort {
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int left = 0;
int right = arr.length - 1;
while (left < right) {
int minIndex = left;
int maxIndex = right;
// 在[left, right]区间内同时找最小和最大
for (int i = left; i <= right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
// 将最小值放到left位置
swap(arr, left, minIndex);
// 如果最大值恰好在left位置，交换后它到了minIndex位置
if (maxIndex == left) {
maxIndex = minIndex;
}
// 将最大值放到right位置
swap(arr, right, maxIndex);
left++;
right--;
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {64, 25, 12, 22, 11, 90, 33, 77, 5, 50};
System.out.print("排序前: ");
printArray(arr);
sort(arr);
System.out.print("排序后: ");
printArray(arr);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
复杂度分析
时间复杂度
选择排序的时间复杂度在所有情况下都是 O(n²)：
- 最好情况：数组已经有序。选择排序仍然需要进行完整的比较操作，时间复杂度为 O(n²)。
- 最坏情况：数组逆序。同样需要 O(n²) 的比较和交换。
- 平均情况：O(n²)。
比较次数的精确计算：第一轮比较 n-1 次，第二轮 n-2 次，…，最后一轮 1 次。总比较次数为 (n-1) + (n-2) + ... + 1 = n(n-1)/2。
空间复杂度
选择排序是原地排序算法，仅需常数级别的额外空间用于临时变量交换，空间复杂度为 O(1)。
交换次数
选择排序的最大特点是交换次数极少，最多进行 n-1 次交换。相比冒泡排序在最坏情况下需要进行 O(n²) 次交换，选择排序在写操作代价较高的场景（如闪存、网络传输）具有优势。
稳定性
选择排序是不稳定排序。当将最小元素与前面位置交换时，可能改变相等元素的相对顺序。例如 [5a, 8, 5b, 2]，第一次选择会将 2 与 5a 交换，得到 [2, 8, 5b, 5a]，两个 5 的相对顺序被破坏。
性能对比测试
import java.util.Random;
/**
* 选择排序与其他基础排序的性能对比
*/
public class SortComparison {
public static void main(String[] args) {
int[] sizes = {1000, 5000, 10000};
Random rand = new Random(42);
for (int size : sizes) {
int[] arr1 = new int[size];
int[] arr2 = new int[size];
int[] arr3 = new int[size];
for (int i = 0; i < size; i++) {
int val = rand.nextInt(100000);
arr1[i] = val;
arr2[i] = val;
arr3[i] = val;
}
System.out.println("\n数组大小: " + size);
System.out.println("选择排序: " + benchmark(() -> selectionSort(arr1)) + " ms");
System.out.println("冒泡排序: " + benchmark(() -> bubbleSort(arr2)) + " ms");
System.out.println("插入排序: " + benchmark(() -> insertionSort(arr3)) + " ms");
}
}
private static long benchmark(Runnable sortFunc) {
long start = System.currentTimeMillis();
sortFunc.run();
return System.currentTimeMillis() - start;
}
private static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
}
if (minIdx != i) {
int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;
}
}
}
private static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
boolean swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break;
}
}
private static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
}
适用场景与总结
选择排序适用于以下场景：
– 数据量较小：当 n < 1000 时，O(n²) 的算法性能可以接受。
– 写操作代价高：如闪存写入、网络I/O，选择排序仅需 O(n) 次交换。
– 需要最少交换：某些硬件或分布式系统中，减少交换次数意味着降低通信开销。
– 教学入门：算法思想极其直观，是理解排序算法的最佳起点。
选择排序虽然效率不高，但其简洁的实现和极低的交换次数使其在特定领域仍有一席之地。理解选择排序有助于建立对排序算法时间-空间权衡的直觉，为学习更高效的快速排序、归并排序和堆排序打下基础。
