选择排序（Selection Sort）

选择排序（Selection Sort）是一种简单直观的排序算法，适合初学者理解和掌握。尽管它的效率不如一些高级排序算法，但作为基础排序算法，选择排序提供了一个良好的学习基础，帮助我们理解排序问题的基本概念。

什么是选择排序？

选择排序是一种比较排序算法，它的核心思想是：每次从未排序的部分中找到最小（或最大）的元素，并将其放到已排序部分的末尾。通过不断重复这一过程，数组最终变得有序。

选择排序的步骤：

1. 遍历数组，找到最小的元素。
2. 将这个元素与当前未排序部分的第一个元素交换位置。
3. 将当前最小元素的索引标记为已排序。
4. 重复以上步骤，直到数组完全有序。

算法的工作原理

假设我们有一个数组 arr = [64, 25, 12, 22, 11]，我们来分析选择排序如何对其进行升序排列：

1. 初始数组：[64, 25, 12, 22, 11]
   • 找到最小值 11，将其与第一个元素 64 交换。
   • 结果：[11, 25, 12, 22, 64]
2. 第二次遍历：[11, 25, 12, 22, 64]
   • 在未排序部分 [25, 12, 22, 64] 中找到最小值 12，与 25 交换。
   • 结果：[11, 12, 25, 22, 64]
3. 第三次遍历：[11, 12, 25, 22, 64]
   • 在未排序部分 [25, 22, 64] 中找到最小值 22，与 25 交换。
   • 结果：[11, 12, 22, 25, 64]
4. 第四次遍历：[11, 12, 22, 25, 64]
   • 未排序部分为 [25, 64]，最小值 25 已经在正确位置。
   • 无需交换，结果：[11, 12, 22, 25, 64]
5. 完成排序。

算法实现

Python实现

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 假设当前索引 i 的元素是最小值
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 交换找到的最小值与当前位置
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 测试
array = [64, 25, 12, 22, 11]
sorted_array = selection_sort(array)
print("排序后的数组:", sorted_array)

输出结果：

排序后的数组: [11, 12, 22, 25, 64]

Java实现

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;
                }
            }

            // 交换最小值和当前位置
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = {64, 25, 12, 22, 11};
        selectionSort(array);

        System.out.print("排序后的数组: ");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

输出结果：

排序后的数组: [11, 12, 22, 25, 64]

算法分析

时间复杂度

1. 最好情况、最坏情况和平均情况的时间复杂度均为 O(n^2)。
   • 外层循环执行 n−1 次。
   • 内层循环执行 n−i次，其中 i 是外层循环的当前索引。
   • 总的比较次数为 (n−1)+(n−2)+…+1=n(n−1)/2≈O(n^2)。

空间复杂度

• 选择排序是原地排序算法，空间复杂度为 O(1)，因为它不需要额外的存储空间。

稳定性

• 不稳定：当最小元素与前面的元素交换时，可能改变两个相同元素的相对顺序。

适用场景

由于选择排序的时间复杂度较高，在实际生产环境中不常用，更多的是作为教学或小型数据排序的工具。适用场景包括：

1. 数据量较小的简单排序任务。
2. 对稳定性要求不高的场景。

优缺点总结

优点

• 实现简单，逻辑清晰。
• 不需要额外的存储空间。

缺点

• 时间复杂度较高，效率低。
• 对于大规模数据集排序表现不佳。
• 不稳定。

总结

选择排序是一种经典的排序算法，尽管效率不高，但非常适合作为入门排序算法的学习对象。它的简单性让我们更容易理解排序问题的基本原理，也为学习更复杂的排序算法（如快速排序、归并排序）打下基础。通过实际动手实现选择排序，我们不仅可以掌握算法的细节，还能锻炼自己的编程能力和算法思维。

你是否还有关于选择排序的疑问或想法？欢迎留言讨论！

PS：可以点击打开“选择排序算法演示”页面亲自体验一下 😊