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

重温经典算法——选择排序

ds 2025/8/24 7:47:00

版权声明

本文原创作者：谷哥的小弟
作者博客地址：http://blog.csdn.net/lfdfhl

在这里插入图片描述

基本原理

选择排序属于简单的原地排序算法，通过将待排序序列分为已排序和未排序两部分，每次从未排序部分选择最小元素，与未排序部分的起始位置交换，逐步扩大已排序范围。其核心操作是“选择最小元素并固定位置”，时间复杂度始终为 O(n²)（无论数据是否有序），空间复杂度为 O(1)，属于不稳定排序（如对 [5, 5, 3] 排序可能破坏相同元素的原始顺序），适用于小规模数据或内存敏感的场景。

代码实现

import java.util.Arrays;public class SelectionSort {public static void selectionSort(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; // 更新最小值索引}}// 将最小值交换到已排序部分的末尾if (minIndex != i) { // 避免无效交换int temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}}}public static void main(String[] args) {int[] arr = {64, 25, 12, 22, 11};selectionSort(arr);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [11, 12, 22, 25, 64]}
}