Java 选择排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。排序算法按特定顺序排列元素，通常是数字或按字典顺序排列。高效排序对于优化其他算法至关重要。
常见的排序算法包括冒泡排序、插入排序、选择排序、归并排序、快速排序和堆排序。 每种算法都有不同的时间和空间复杂度特性，因此适用于不同的场景。
选择排序概述
选择排序是一种简单的基于比较的算法。 它将输入分为已排序和未排序区域。 它重复从未排序区域中选择最小（或最大）的元素，并将其移动到已排序区域。
该算法在所有情况下都具有 O(n²) 的时间复杂度，因此对于大型数据集来说效率低下。 但是，它在小型列表上表现良好，并且具有最多执行 n-1 次交换的优点。
选择排序的实现
这是一个 Java 中选择排序的基本实现，用于按升序对整数进行排序。 该算法的工作原理是在每次遍历中找到最小的元素。
SelectionSort.java
package com.zetcode;
public class SelectionSort {
public 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;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11};
System.out.println("Before sorting:");
for (int num : numbers) {
System.out.print(num + " ");
}
selectionSort(numbers);
System.out.println("\nAfter sorting:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
此实现显示了核心选择排序算法。 外循环移动未排序子数组的边界。 内循环查找最小元素。 最后，我们将找到的最小值与第一个元素交换。
降序排序
要按降序排序，我们只需修改比较以查找最大元素而不是最小元素。 以下是算法的更改方式
SelectionSortDescending.java
package com.zetcode;
public class SelectionSortDescending {
public static void selectionSortDesc(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int maxIdx = i;
for (int j = i+1; j < n; j++) {
if (arr[j] > arr[maxIdx]) {
maxIdx = j;
}
}
// Swap the found maximum element with the first element
int temp = arr[maxIdx];
arr[maxIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] numbers = {64, 25, 12, 22, 11};
System.out.println("Before sorting:");
for (int num : numbers) {
System.out.print(num + " ");
}
selectionSortDesc(numbers);
System.out.println("\nAfter sorting (descending):");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
唯一需要的更改是内循环中的比较运算符。 我们不是寻找小于当前最小值的元素，而是寻找大于当前最大值的元素。
使用选择排序对字符串进行排序
选择排序也可以对文本数据进行排序。 这是使用 Java 的 compareTo 方法进行字典比较以按升序对字符串进行排序的实现。
StringSelectionSort.java
package com.zetcode;
public class StringSelectionSort {
public static void selectionSortStrings(String[] 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].compareTo(arr[minIdx]) < 0) {
minIdx = j;
}
}
// Swap the found minimum element with the first element
String temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
String[] words = {"banana", "apple", "pear", "orange", "grape"};
System.out.println("Before sorting:");
for (String word : words) {
System.out.print(word + " ");
}
selectionSortStrings(words);
System.out.println("\nAfter sorting:");
for (String word : words) {
System.out.print(word + " ");
}
}
}
此实现演示了按字母顺序对字符串进行排序。 如果字符串按字典顺序较小，compareTo 方法将返回一个负数，我们使用它来查找每次遍历中的最小字符串。
选择排序 vs 快速排序
选择排序和快速排序代表了两种不同的排序方法。 选择排序简单但效率低下 (O(n²))，而快速排序更复杂但平均速度更快 (O(n log n))。
这是一个基准测试，比较了两种算法在相同数据集上的性能。 请注意，随着数据集大小的增长，快速排序如何优于选择排序。
SortBenchmark.java
package com.zetcode;
import java.util.Arrays;
import java.util.Random;
public class SortBenchmark {
public 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;
}
}
int temp = arr[minIdx];
arr[minIdx] = arr[i];
arr[i] = temp;
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
public static void main(String[] args) {
int[] smallArray = new int[1000];
int[] mediumArray = new int[10000];
int[] largeArray = new int[100000];
Random rand = new Random();
for (int i = 0; i < smallArray.length; i++) {
smallArray[i] = rand.nextInt();
}
for (int i = 0; i < mediumArray.length; i++) {
mediumArray[i] = rand.nextInt();
}
for (int i = 0; i < largeArray.length; i++) {
largeArray[i] = rand.nextInt();
}
// Benchmark selection sort
long startTime = System.nanoTime();
selectionSort(Arrays.copyOf(smallArray, smallArray.length));
long endTime = System.nanoTime();
System.out.println("Selection sort (1,000 elements): " +
(endTime - startTime)/1_000_000 + " ms");
startTime = System.nanoTime();
selectionSort(Arrays.copyOf(mediumArray, mediumArray.length));
endTime = System.nanoTime();
System.out.println("Selection sort (10,000 elements): " +
(endTime - startTime)/1_000_000 + " ms");
// Benchmark quick sort
startTime = System.nanoTime();
quickSort(Arrays.copyOf(smallArray, smallArray.length), 0, smallArray.length-1);
endTime = System.nanoTime();
System.out.println("Quick sort (1,000 elements): " +
(endTime - startTime)/1_000_000 + " ms");
startTime = System.nanoTime();
quickSort(Arrays.copyOf(mediumArray, mediumArray.length), 0, mediumArray.length-1);
endTime = System.nanoTime();
System.out.println("Quick sort (10,000 elements): " +
(endTime - startTime)/1_000_000 + " ms");
startTime = System.nanoTime();
quickSort(Arrays.copyOf(largeArray, largeArray.length), 0, largeArray.length-1);
endTime = System.nanoTime();
System.out.println("Quick sort (100,000 elements): " +
(endTime - startTime)/1_000_000 + " ms");
}
}
该基准测试清楚地显示了性能差异。 选择排序对于大型数据集来说变得不切实际，而快速排序保持了良好的性能。 但是，当内存写入成本很高时，选择排序可能是首选。
何时使用选择排序
尽管效率低下，但选择排序有一些优点。 它执行的交换次数有限 (O(n))，因此在写入操作成本高昂时非常有用。 它也很容易实现和理解，适用于教学目的。
选择排序适用于小型数据集或几乎排序的数据。 但是，对于大多数实际应用，Java 的内置 Arrays.sort （它使用经过优化的快速排序）对于原始类型来说是更可取的，而对于对象来说，归并排序是更可取的。
来源
在本教程中，我们介绍了 Java 中的选择排序算法，包括升序和降序的数字和文本数据的实现。 我们还将它的性能与快速排序进行了比较。
作者
列出所有Java教程。