当前位置：首页 > ai >正文

【java实现+4种变体完整例子】排序算法中【选择排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

ai 2025/7/26 22:11:27

以下是选择排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
在这里插入图片描述

一、选择排序基础实现

原理

每一轮遍历未排序部分，找到最小元素并交换到当前起始位置，逐步构建已排序序列。

代码示例

public class SelectionSort {void sort(int[] arr) {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;}}swap(arr, i, minIndex); // 交换当前元素与最小值}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

复杂度分析

时间复杂度：O(n²)（所有情况）。
空间复杂度：O(1)。
稳定性：不稳定（相同值的元素可能因交换顺序改变相对位置）。

二、常见变体及代码示例

1. 递归实现

改进点：用递归替代循环，代码结构更清晰。
适用场景：教学或代码风格偏好递归。

public class RecursiveSelectionSort {void sort(int[] arr, int n) {if (n <= 1) return;int minIndex = findMinIndex(arr, 0, n);swap(arr, 0, minIndex); // 将最小值放到首位sort(arr, n - 1); // 递归处理剩余部分}private int findMinIndex(int[] arr, int start, int end) {int minIndex = start;for (int i = start + 1; i < end; i++) {if (arr[i] < arr[minIndex]) {minIndex = i;}}return minIndex;}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

2. 双向选择排序（鸡尾酒选择排序）

改进点：每一轮同时找到最小和最大元素，并将它们放到正确的位置。
适用场景：数据分布较分散或两端有序，减少比较次数。

public class CocktailSelectionSort {void sort(int[] arr) {int n = arr.length;int start = 0, end = n - 1;while (start < end) {int minIndex = start;int maxIndex = start;for (int i = start; i <= end; i++) {if (arr[i] < arr[minIndex]) minIndex = i;if (arr[i] > arr[maxIndex]) maxIndex = i;}// 交换最小值到起始位置swap(arr, minIndex, start);// 处理最大值交换（避免与最小值冲突）if (maxIndex == start) swap(arr, maxIndex, minIndex);else swap(arr, maxIndex, end);start++;end--;}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

3. 优化版（减少比较次数）

改进点：通过减少内层循环次数，将比较次数减半。
适用场景：进一步优化基础实现的性能。

public class OptimizedSelectionSort {void sort(int[] arr) {int n = arr.length;for (int i = 0; i < n / 2; i++) {int minIndex = i;int maxIndex = n - 1 - i;for (int j = i + 1; j <= n - 1 - i; j++) {if (arr[j] < arr[minIndex]) minIndex = j;if (arr[j] > arr[maxIndex]) maxIndex = j;}swap(arr, i, minIndex);if (maxIndex == i) swap(arr, maxIndex, minIndex);else swap(arr, maxIndex, n - 1 - i);}}private void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

三、变体对比表格

变体名称	时间复杂度	空间复杂度	稳定性	主要特点	适用场景
基础选择排序	`O(n²)`	`O(1)`	不稳定	简单易实现，每轮仅找最小值	小规模数据或教学场景
递归实现	`O(n²)`	`O(n)`	不稳定	递归替代循环，代码结构清晰	代码风格偏好或教学场景
双向选择排序（鸡尾酒排序）	`O(n²)`	`O(1)`	不稳定	每轮同时找最小和最大值，减少比较次数	数据分布较分散或两端有序
优化版（减少比较次数）	`O(n²)`	`O(1)`	不稳定	通过减少内层循环次数提升效率	需要轻微优化比较次数的场景