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

【算法-选择排序】挑挑拣拣，排出顺序——选择排序入门

article 2025/2/23 23:20:05

什么是选择排序？

选择排序是一种比较简单直接的排序方式。想象你在打散一副牌，想按照大小顺序从小到大排列这些牌。你会怎么做？可能会先找出最小的那张，放在最前面，然后在剩下的牌里找第二小的，依次类推，这就是选择排序的基本思路！

在程序中，选择排序的操作流程也类似：它逐步将未排序的部分中最小的元素找到，放到前面的位置，直到整个数组有序。

选择排序的操作步骤

为了更直观，我们来看看每一步是如何进行的：

步骤1：找到未排序部分中的最小值

首先，从一堆数字中找到最小的那个。这就像玩扑克牌时，眼睛在一张张扫过，看看哪一张最小。

步骤2：把最小值放到正确的位置

找到最小值之后，就把它交换到最前面的位置，让它“坐在”已经排好序的队伍的最前面。剩下的数字依然是乱的，我们继续重复这个过程。

步骤3：重复以上操作，直到所有数字排好

这个操作会一直重复，下一步我们会从第二个位置开始，再找出剩余部分的最小值，放在第二位。这样一轮一轮地把最小值一个个找出来，依次放到前面，最终就会得到一个按从小到大的顺序排列的列表！

图解选择排序

选择排序

假设我们有以下一个无序数组：[29, 10, 14, 37, 13]

我们用选择排序来一步步将它排好顺序：

第一轮：
- 从[29, 10, 14, 37, 13]中找最小值。
- 发现最小的是10，把10放到第一个位置。
- 交换后数组变成：[10, 29, 14, 37, 13]
第二轮：
- 从[29, 14, 37, 13]中找最小值。
- 最小的是13，把13放到第二个位置。
- 交换后数组变成：[10, 13, 14, 37, 29]
第三轮：
- 从[14, 37, 29]中找最小值。
- 最小的是14，已经在正确的位置，无需交换。
- 数组保持不变：[10, 13, 14, 37, 29]
第四轮：
- 从[37, 29]中找最小值。
- 发现最小的是29，交换到第四个位置。
- 交换后数组变成：[10, 13, 14, 29, 37]

到这里，整个数组从小到大排列完成：[10, 13, 14, 29, 37]

代码

public class SelectionSortExample {

    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++) {
                // 如果找到更小的元素，则更新minIndex
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 将找到的最小元素与当前位置的元素交换
            // 这里的交换确保了当前索引i位置是最小的元素
            if (minIndex != i) {  // 仅在必要时交换
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            
            // 打印当前排序的进度，便于观察每一轮的结果
            System.out.print("第 " + (i + 1) + " 轮排序结果：");
            printArray(arr);
        }
    }

    // 辅助方法，用于打印数组内容
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    // 主方法，用于测试选择排序
    public static void main(String[] args) {
        int[] arr = {29, 10, 14, 37, 13};  // 初始化无序数组
        
        System.out.print("初始数组：");
        printArray(arr);

        // 进行选择排序
        selectionSort(arr);

        System.out.print("最终排序结果：");
        printArray(arr);
    }
}

代码说明

外层循环：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; }，找到比当前最小值更小的元素后，更新 minIndex。
交换操作：if (minIndex != i)，交换当前元素和找到的最小元素的位置，以确保当前索引 i 上放的是该轮的最小值。
打印当前排序进度：在每轮结束时调用 printArray(arr); 打印数组内容，便于观察排序过程。