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

java 选择排序，涵盖工作原理、算法分析、实现细节、优缺点以及一些实际应用场景

article 2025/3/4 19:39:42

选择排序的详细解析

更深入地探讨选择排序的各个方面，包括其工作原理、算法分析、实现细节、优缺点以及一些实际应用场景。

动画演示
在这里插入图片描述

1. 基本概念

选择排序是一种简单的比较排序算法。它的核心思想是将数组分为两个部分：已排序部分和未排序部分。每一轮从未排序部分找到最小（或最大）元素，并将其放到已排序部分的末尾。

2. 工作原理

初始化：整个数组都被视为未排序部分。
迭代过程：
- 从未排序部分中选出最小元素。
- 将最小元素与未排序部分的第一个元素交换。
- 已排序部分增加一个元素，未排序部分减少一个元素。

3. 详细步骤

考虑一个数组 arr，假设其长度为 n。

第 1 轮：
- 在 arr[0] 到 arr[n-1] 中找最小值，假设找到的最小值在位置 minIndex。
- 交换 arr[0] 和 arr[minIndex]。
- 已排序部分：[arr[0]]，未排序部分：[arr[1], arr[2], ..., arr[n-1]]。
第 2 轮：
- 在 arr[1] 到 arr[n-1] 中找最小值，假设找到的最小值在位置 minIndex。
- 交换 arr[1] 和 arr[minIndex]。
- 已排序部分：[arr[0], arr[1]]，未排序部分：[arr[2], ..., arr[n-1]]。
继续：重复以上过程，直到未排序部分为空。

4. 伪代码

function selectionSort(array):
    n = length(array)
    for i from 0 to n - 1:
        minIndex = i
        for j from i + 1 to n - 1:
            if array[j] < array[minIndex]:
                minIndex = j
        if minIndex != i:
            swap(array[i], array[minIndex])

5. Java 实现

public class SelectionSort {

    public static void selectionSort(int[] array) {
        int n = array.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // 假设当前元素为最小值
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j; // 更新最小值的索引
                }
            }
            // 如果最小值的索引变化了，则交换
            if (minIndex != i) {
                swap(array, i, minIndex);
            }
        }
    }

    // 交换数组中两个元素的方法
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 测试选择排序
    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        selectionSort(array);
        System.out.println("排序后的数组：");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

6. 复杂度分析

时间复杂度：
- 最坏情况：(O(n^2))，每次外层循环运行 n - 1 次，内层循环运行的次数依次为 n - 1, n - 2, …, 1。
- 最好情况：(O(n^2))，无论数组是正序还是逆序，选择排序的比较次数都是固定的。
- 平均情况：(O(n^2))。
空间复杂度：选择排序是原地排序，额外空间复杂度为 (O(1))。