《Java 实现选择排序：原理剖析与代码详解》

时间：2024-11-04 12:03:17

目录

一、引言

二、选择排序原理

三、代码分析

1. 代码整体结构

2. main方法

3. sort方法（选择排序核心逻辑）

四、测试结果

一、引言

排序算法在计算机科学领域中是非常重要的一部分，它能够帮助我们将无序的数据按照特定的顺序进行排列，以便于后续的处理和分析。选择排序作为一种简单直观的排序算法，虽然在效率上可能不如一些更高级的排序算法，但它是理解排序概念的一个很好的入门选择。在这篇博客中，我们将深入解析一段用 Java 实现选择排序的代码，帮助大家透彻理解选择排序的原理以及代码的具体实现细节。

二、选择排序原理

选择排序的基本思想是：在未排序的序列中找到最小（或最大）的元素，然后将其与未排序序列的第一个元素进行交换位置。接着，在剩余的未排序序列中继续寻找最小（或最大）元素，并与未排序序列的第二个元素进行交换，以此类推，直到整个序列都被排序完成。

简单来说，每一轮排序都能确定一个元素在最终有序序列中的位置，经过多次这样的轮次，就能将整个数组排序好。

三、代码分析

1. 代码整体结构

以下是我们要详细分析的 Java 选择排序代码：

package 排序;

import java.util.Arrays;

public class SelectSort {

    public static void main(String[] args) {
        int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        for (int j = 0; j < arr.length; j++) {
            int min = arr[j];
            int minIndex = j; //记录真正最小值的下标
            //找真正的最小值
            for (int i = j; i < arr.length; i++) {
                if (arr[i] < min) {
                    min = arr[i];
                    minIndex = i;
                }
            }
            //真正的最小值和待排序数组第一个进行交换

            arr[minIndex] = arr[j];
            arr[j] = min;
        }
    }
}

2. main方法

在 main 方法中，首先定义了一个整数数组 arr，并初始化其值为 {5, 7, 4, 2, 0, 3, 1, 6}。这就是我们要进行排序的原始数组。

int[] arr = {5, 7, 4, 2, 0, 3, 1, 6};

然后调用了 sort 方法，并将数组 arr 作为参数传递给它，目的是对这个数组进行排序操作。

sort(arr);

最后，在排序完成后，使用 Arrays.toString 方法将排序后的数组以字符串的形式输出到控制台，以便直观地查看排序的结果。

System.out.println(Arrays.toString(arr));

3. sort方法（选择排序核心逻辑）

sort 方法实现了选择排序的核心逻辑，下面我们来详细剖析其内部的操作。

  • 外层循环：
    通过 for (int j = 0; j < arr.length; j++) 这个外层循环，控制着排序的轮数。每一轮循环都会确定一个元素在最终有序序列中的位置。总共需要进行 arr.length 轮循环，因为每一轮都能将一个元素放到它正确的位置上，经过 arr.length 轮就能将整个数组排序完成。

  • 寻找每轮的最小值及其下标：
    在每一轮循环开始时，先假设当前未排序序列的第一个元素（即 arr[j]）就是最小值，并将其值赋给 min，同时记录其下标 minIndex 为 j。

然后，通过内层循环 for (int i = j; i < arr.length; i++) 在剩余的未排序序列（从索引 j 到数组末尾）中寻找真正的最小值。如果发现某个元素 arr[i] 比当前假设的最小值 min 更小，就更新 min 的值为 arr[i]，并更新 minIndex 为 i，这样就能准确找到这一轮未排序序列中的最小值及其下标。

int min = arr[j];
int minIndex = j; //记录真正最小值的下标
//找真正的最小值
for (int i = j; i < arr.length; i++) {
    if (arr[i] < min) {
        min = arr[i];
        minIndex = i;
    }
}
  • 交换元素：
    在找到每一轮的最小值及其下标后，将最小值与当前未排序序列的第一个元素（即 arr[j]）进行交换。通过以下两行代码实现交换操作：
arr[minIndex] = arr[j];
arr[j] = min;

先将 arr[j] 的值赋给 arr[minIndex]，然后将找到的最小值 min 赋给 arr[j]，这样就完成了这一轮的排序操作，将一个元素放到了它正确的位置上。

四、测试结果

当我们运行上述代码时，对于给定的初始数组 {5, 7, 4, 2, 0, 3, 1, 6}，经过选择排序后，控制台会输出排序后的数组，其结果应该是 {0, 1, 2, 3, 4, 5, 6, 7}。

相关文章