您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# Java选择排序方法是什么
## 一、选择排序概述
选择排序（Selection Sort）是一种简单直观的排序算法，其核心思想是：**每次从未排序的部分中选择最小（或最大）的元素，放到已排序序列的末尾**。该算法的时间复杂度为O(n²)，属于基础排序算法之一，适用于小规模数据排序。
### 1.1 算法特点
- **不稳定排序**：相同元素的相对位置可能改变
- **原地排序**：不需要额外存储空间
- **时间复杂度**：始终为O(n²)
- **空间复杂度**：O(1)
## 二、算法原理详解
### 2.1 基本思想
选择排序将数组分为两部分：
- **已排序部分**（左侧）
- **未排序部分**（右侧）
每次迭代从未排序部分找到最小元素，与未排序部分的第一个元素交换位置。
### 2.2 执行步骤
1. 初始化：已排序部分为空
2. 遍历未排序部分，找到最小元素
3. 将最小元素与未排序部分的第一个元素交换
4. 将边界向右移动一位（已排序部分增加一个元素）
5. 重复步骤2-4直到全部排序完成
```java
// 伪代码表示
for (int i = 0; i < arr.length-1; i++) {
int minIndex = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
public class SelectionSort {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 交换位置
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
public static void optimizedSort(int[] arr) {
int left = 0, right = arr.length - 1;
while (left < right) {
int minIndex = left, maxIndex = right;
// 确保minIndex <= maxIndex
if (arr[minIndex] > arr[maxIndex]) {
swap(arr, minIndex, maxIndex);
}
for (int i = left + 1; i < right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
} else if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
swap(arr, left, minIndex);
swap(arr, right, maxIndex);
left++;
right--;
}
}
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n²) | 数组已有序 |
| 最坏情况 | O(n²) | 数组逆序 |
| 平均情况 | O(n²) | 需要进行n(n-1)/2次比较 |
| 特性 | 选择排序 | 冒泡排序 |
|---|---|---|
| 交换次数 | O(n) | O(n²) |
| 比较次数 | O(n²) | O(n²) |
| 稳定性 | 不稳定（默认） | 稳定 |
通过额外空间记录元素原始位置，或在交换时保证相同元素不移动：
void stableSelectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 将最小元素插入到i位置，保持其他元素相对顺序
int key = arr[minIndex];
while (minIndex > i) {
arr[minIndex] = arr[minIndex - 1];
minIndex--;
}
arr[i] = key;
}
}
示例：排序 [5, 8, 5, 2]
- 第一次选择最小元素2与第一个5交换 → [2, 8, 5, 5]
- 两个5的相对顺序发生了改变
即优化版本中同时寻找最小和最大元素，可以减少约50%的迭代轮数。
void recursiveSelectionSort(int[] arr, int start) {
if (start >= arr.length - 1) return;
int minIndex = start;
for (int i = start + 1; i < arr.length; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
}
swap(arr, start, minIndex);
recursiveSelectionSort(arr, start + 1);
}
选择排序作为最基础的排序算法之一，虽然在实际工程中应用有限，但仍然是理解算法设计思想的重要案例。其简单直观的实现方式非常适合算法初学者，同时也能帮助开发者理解时间复杂度分析的基本方法。当处理小规模数据或受限于内存资源时，选择排序仍可作为备选方案。 “`
注：本文实际约1200字，可通过以下方式扩展： 1. 增加更多代码示例（如泛型实现） 2. 添加可视化排序过程说明 3. 补充性能测试数据对比 4. 增加更多语言实现对比
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。