选择排序（Selection Sort）
字数 2146 2025-12-11 11:16:34

选择排序（Selection Sort）

题目描述

给你一个整数数组 nums，请使用选择排序算法将其按照非递减顺序（即升序）排序。请描述该算法的过程，并逐步分析其工作原理、时间与空间复杂度。

解题过程

选择排序是一种基于比较的原地排序算法。它的核心思想非常简单：在未排序的部分中，反复查找最小（或最大）的元素，并将其放到已排序部分的末尾。

第一步：理解算法基本思想

想象你有一叠扑克牌散在桌上，你想把它们按从小到大的顺序排好。一个直观的方法是：从所有牌中找出最小的一张，放到最左边；然后从剩下的牌中再找出最小的，放到刚才那张牌的右边；重复这个过程，直到所有牌都排好。这就是选择排序。

在算法中，我们通常将数组分为两个部分：

  1. 已排序部分：位于数组的左端，初始时为空。
  2. 未排序部分：位于数组的右端，初始时为整个数组。

算法的每一轮，我们从“未排序部分”中找出最小的元素，然后将这个最小元素与“未排序部分”的第一个元素进行交换。这个操作完成后，“未排序部分”的第一个元素就加入了“已排序部分”的末尾，而“未排序部分”则减少了一个元素。

第二步：详细步骤拆解

我们以数组 nums = [64, 25, 12, 22, 11] 为例。

  • 初始状态：整个数组都是未排序部分。已排序部分 = []，未排序部分 = [64, 25, 12, 22, 11]。

  • 第1轮 (i=0)：

    • 在未排序部分 [64, 25, 12, 22, 11] 中查找最小值。遍历发现最小值是 11，它的索引位置是 4。
    • 将找到的最小值（索引4）与未排序部分的第一个元素（索引0）交换。交换后数组变为：[11, 25, 12, 22, 64]。
    • 现在，nums[0] = 11 被视为已排序。已排序部分 = [11]，未排序部分 = [25, 12, 22, 64]。

  • 第2轮 (i=1)：

    • 在未排序部分 [25, 12, 22, 64] 中查找最小值。最小值是 12，索引为 2。
    • 将 nums[2] 与 nums[1] 交换。交换后数组：[11, 12, 25, 22, 64]。
    • 现在，已排序部分 = [11, 12]，未排序部分 = [25, 22, 64]。

  • 第3轮 (i=2)：

    • 在未排序部分 [25, 22, 64] 中查找最小值。最小值是 22，索引为 3。
    • 将 nums[3] 与 nums[2] 交换。交换后数组：[11, 12, 22, 25, 64]。
    • 现在，已排序部分 = [11, 12, 22]，未排序部分 = [25, 64]。

  • 第4轮 (i=3)：

    • 在未排序部分 [25, 64] 中查找最小值。最小值是 25，索引正好是 3（即未排序部分的第一个元素）。
    • 自己和自己交换（或无操作）。数组不变：[11, 12, 22, 25, 64]。
    • 现在，已排序部分 = [11, 12, 22, 25]，未排序部分 = [64]。

  • 第5轮 (i=4)：

    • 此时未排序部分只剩一个元素 [64]，它自然是当前最小值。
    • 无需交换。数组保持不变。
    • 最终整个数组已排序：[11, 12, 22, 25, 64]。

注意：对于一个长度为 n 的数组，我们只需要进行 n-1 轮操作，因为最后一轮时，最后一个元素自动处于正确位置。

第三步：算法伪代码

1. 输入：数组 nums，长度为 n
2. 对于 i 从 0 到 n-2 循环：
       a. 设 minIndex = i  // 假设未排序部分的第一个元素是最小的
       b. 对于 j 从 i+1 到 n-1 循环：
           如果 nums[j] < nums[minIndex]，则 minIndex = j
       c. 如果 minIndex != i，则交换 nums[i] 和 nums[minIndex]
3. 输出：排序后的数组 nums

第四步：关键特性与复杂度分析

  1. 原地排序：算法只通过交换元素来排序，除了几个临时变量，不需要额外的数组空间。因此空间复杂度是 O(1)。
  2. 时间复杂度：
    • 最好、最坏、平均情况都是 O(n²)。这是因为无论数组初始顺序如何，外层循环都要执行大约 n 次，内层循环用于查找最小值，每次大约需要比较 (n-i) 次。总的比较次数是 (n-1) + (n-2) + ... + 1 = n(n-1)/2，属于 O(n²) 量级。交换操作最多发生 n-1 次，是 O(n) 量级，不影响主导项。
  3. 不稳定性：选择排序是不稳定的排序算法。考虑数组 [5a, 2, 5b, 1]（用下标区分相同值）。第一轮找到最小值1，与第一个5a交换，得到 [1, 2, 5b, 5a]。两个5的相对顺序（5a在5b之前）被颠倒了。
  4. 交换次数少：这是选择排序相对于其他简单排序（如冒泡排序）的一个优点。在最坏情况下，它也只进行 n-1 次交换，而冒泡排序在最坏情况下可能需要 O(n²) 次交换。这在交换成本很高（例如，要排序的是大型对象或存储在慢速介质中的数据）时是一个优势。

第五步：总结与应用场景

选择排序的优点是思想简单，代码容易实现，并且在交换操作代价高时可能有优势。其缺点是时间复杂度较高，不适合大规模数据排序。在实际应用中，它通常仅用于教学目的，或者用于对数据量非常小（比如 n <= 10）的数组进行排序，因为其简单的代码可能带来较低的开销。

通过以上循序渐进的分析，你应该能够清晰地理解选择排序是如何一步一步从未排序区域中选择最小元素，并通过交换将其归位，从而最终完成整个数组排序的。

选择排序（Selection Sort） 题目描述 给你一个整数数组 nums ，请使用 选择排序 算法将其按照非递减顺序（即升序）排序。请描述该算法的过程，并逐步分析其工作原理、时间与空间复杂度。 解题过程 选择排序是一种基于比较的原地排序算法。它的核心思想非常简单：在未排序的部分中，反复查找最小（或最大）的元素，并将其放到已排序部分的末尾。 第一步：理解算法基本思想 想象你有一叠扑克牌散在桌上，你想把它们按从小到大的顺序排好。一个直观的方法是：从所有牌中找出最小的一张，放到最左边；然后从剩下的牌中再找出最小的，放到刚才那张牌的右边；重复这个过程，直到所有牌都排好。这就是选择排序。 在算法中，我们通常将数组分为两个部分： 已排序部分 ：位于数组的左端，初始时为空。 未排序部分 ：位于数组的右端，初始时为整个数组。 算法的每一轮，我们从“未排序部分”中找出最小的元素，然后将这个最小元素与“未排序部分”的第一个元素进行交换。这个操作完成后，“未排序部分”的第一个元素就加入了“已排序部分”的末尾，而“未排序部分”则减少了一个元素。 第二步：详细步骤拆解 我们以数组 nums = [64, 25, 12, 22, 11] 为例。 初始状态 ：整个数组都是未排序部分。 已排序部分 = [] ， 未排序部分 = [64, 25, 12, 22, 11] 。 第1轮 (i=0) ： 在未排序部分 [64, 25, 12, 22, 11] 中查找最小值。遍历发现最小值是 11 ，它的索引位置是 4 。 将找到的最小值（索引4）与未排序部分的第一个元素（索引0）交换。交换后数组变为： [11, 25, 12, 22, 64] 。 现在， nums[0] = 11 被视为已排序。 已排序部分 = [11] ， 未排序部分 = [25, 12, 22, 64] 。 第2轮 (i=1) ： 在未排序部分 [25, 12, 22, 64] 中查找最小值。最小值是 12 ，索引为 2 。 将 nums[2] 与 nums[1] 交换。交换后数组： [11, 12, 25, 22, 64] 。 现在， 已排序部分 = [11, 12] ， 未排序部分 = [25, 22, 64] 。 第3轮 (i=2) ： 在未排序部分 [25, 22, 64] 中查找最小值。最小值是 22 ，索引为 3 。 将 nums[3] 与 nums[2] 交换。交换后数组： [11, 12, 22, 25, 64] 。 现在， 已排序部分 = [11, 12, 22] ， 未排序部分 = [25, 64] 。 第4轮 (i=3) ： 在未排序部分 [25, 64] 中查找最小值。最小值是 25 ，索引正好是 3 （即未排序部分的第一个元素）。 自己和自己交换（或无操作）。数组不变： [11, 12, 22, 25, 64] 。 现在， 已排序部分 = [11, 12, 22, 25] ， 未排序部分 = [64] 。 第5轮 (i=4) ： 此时未排序部分只剩一个元素 [64] ，它自然是当前最小值。 无需交换。数组保持不变。 最终整个数组已排序： [11, 12, 22, 25, 64] 。 注意：对于一个长度为 n 的数组，我们只需要进行 n-1 轮操作，因为最后一轮时，最后一个元素自动处于正确位置。 第三步：算法伪代码 第四步：关键特性与复杂度分析 原地排序 ：算法只通过交换元素来排序，除了几个临时变量，不需要额外的数组空间。因此 空间复杂度是 O(1) 。 时间复杂度 ： 最好、最坏、平均情况都是 O(n²) 。这是因为无论数组初始顺序如何，外层循环都要执行大约 n 次，内层循环用于查找最小值，每次大约需要比较 (n-i) 次。总的比较次数是 (n-1) + (n-2) + ... + 1 = n(n-1)/2，属于 O(n²) 量级。交换操作最多发生 n-1 次，是 O(n) 量级，不影响主导项。 不稳定性 ：选择排序是 不稳定 的排序算法。考虑数组 [5a, 2, 5b, 1] （用下标区分相同值）。第一轮找到最小值1，与第一个5a交换，得到 [1, 2, 5b, 5a] 。两个5的相对顺序（5a在5b之前）被颠倒了。 交换次数少 ：这是选择排序相对于其他简单排序（如冒泡排序）的一个优点。在最坏情况下，它也只进行 n-1 次交换，而冒泡排序在最坏情况下可能需要 O(n²) 次交换。这在交换成本很高（例如，要排序的是大型对象或存储在慢速介质中的数据）时是一个优势。 第五步：总结与应用场景 选择排序的优点是思想简单，代码容易实现，并且在交换操作代价高时可能有优势。其缺点是时间复杂度较高，不适合大规模数据排序。在实际应用中，它通常仅用于教学目的，或者用于对数据量非常小（比如 n <= 10）的数组进行排序，因为其简单的代码可能带来较低的开销。 通过以上循序渐进的分析，你应该能够清晰地理解选择排序是如何一步一步从未排序区域中选择最小元素，并通过交换将其归位，从而最终完成整个数组排序的。