算法、软设 90°C 22-03-2025

^{最近更新于：2025-03-22 15:31:45}

简单选择排序是一种基础的排序算法，其主要思想是：从待排序的序列中不断地选择最小（或最大）的元素，然后将其放到序列的起始（或末尾）位置。

算法步骤

1. 整体思路

选择排序的基本思想是将一个无序数组分成两部分：

已排序部分：最开始为空，随着排序进行逐步扩展。
未排序部分：最开始为整个数组，随着每一轮选择最小值后，该部分会逐步缩小。

在每一轮排序中，从未排序部分中选出最小（或最大）的元素，将其与未排序部分的第一个元素交换，确保该位置的元素正确放置。

2. 详细步骤

(1) 初始化

输入：一个包含 n 个元素的数组 arr。
目标：使 arr 按照从小到大的顺序排列。

(2) 外层循环（遍历每个待排序位置）

范围：下标从 0 到 n-2。
- 说明：最后一个元素无需再排序，因为在前面所有元素都已有序后，剩下的最后一个元素必定已排好序。
步骤：

假设当前下标 i 位置的元素为未排序部分的最小值。
用一个变量（例如 min_index）记录这个位置，即 min_index = i。

(3) 内层循环（寻找未排序部分的最小值）

范围：下标从 i+1 到 n-1。
- 说明：内层循环的目的是在剩余未排序的元素中找出最小值。
步骤：

遍历从 j = i+1 到 j = n-1 的每个元素。
对每个 arr[j]，与当前记录的最小值 arr[min_index] 进行比较：
- 如果 arr[j] < arr[min_index]，则更新 min_index = j，即找到了更小的元素。
内层循环结束后，min_index 就指向了未排序部分的最小值所在的位置。

(4) 交换操作

判断与交换：

判断：如果 min_index 不等于 i，说明在未排序部分找到了比 arr[i] 更小的元素。
交换：将 arr[i] 与 arr[min_index] 的元素进行交换，将最小值放到当前位置 i。
如果 min_index 等于 i，说明当前位置已经是未排序部分中最小的元素，无需交换。

(5) 迭代结束

重复步骤 (2)~(4) 直到外层循环结束，即所有位置都已确定。

3. 以示例数组说明

假设数组为 [64, 25, 12, 22, 11]，我们需要对其进行从小到大排序，下面是排序的详细过程：

1. 第1轮（i = 0）：

初始：假定 min_index = 0（元素 64）。
内层循环比较：
- 25 与 64 比较 → 更新 min_index 为 1。
- 12 与 25 比较 → 更新 min_index 为 2。
- 22 与 12 比较 → 12 仍然最小，min_index 保持 2。
- 11 与 12 比较 → 更新 min_index 为 4。
交换：将下标 0 与下标 4 的元素交换，数组变为 [11, 25, 12, 22, 64]。

2. 第2轮（i = 1）：

初始：假定 min_index = 1（元素 25）。
内层循环比较：
- 12 与 25 比较 → 更新 min_index 为 2。
- 22 与 12 比较 → 12 仍然最小。
- 64 与 12 比较 → 12 仍然最小。
交换：将下标 1 与下标 2 的元素交换，数组变为 [11, 12, 25, 22, 64]。

3. 第3轮（i = 2）：

初始：假定 min_index = 2（元素 25）。
内层循环比较：
- 22 与 25 比较 → 更新 min_index 为 3。
- 64 与 22 比较 → 22 仍然最小。
交换：将下标 2 与下标 3 的元素交换，数组变为 [11, 12, 22, 25, 64]。

4. 第4轮（i = 3）：

初始：假定 min_index = 3（元素 25）。
内层循环比较：
- 64 与 25 比较 → 25 仍然最小。
无需交换，因为 min_index 与 i 相等，数组保持 [11, 12, 22, 25, 64]。

5. 第5轮（i = 4）：

此时只剩一个元素，不需要再排序。

注意细节

最小值记录：
在每一趟排序中，需要维护一个变量（例如 min_index）来记录当前遍历中发现的最小值所在的索引。
遍历范围的变化：
每次内层循环的起始下标随着外层循环的进行而递增。例如，第 1 次内层循环遍历下标 0 到 n-1；第 2 次从下标 1 到 n-1；依次类推。这样保证了前面的部分始终是已排序好的。
交换操作：
只有当最小元素的位置与当前起始位置不同的时候才进行交换操作，以减少不必要的赋值。

示例代码（Python）

下面是一个简单的 Python 实现例子：

def selection_sort(arr):
    n = len(arr)
    # 遍历每个位置
    for i in range(n):
        min_index = i  # 假设当前位置的元素为最小
        # 从 i+1 到 n-1 查找最小元素
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 如果最小元素不是当前元素，则交换
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# 示例使用
sample_list = [64, 25, 12, 22, 11]
sorted_list = selection_sort(sample_list)
print(sorted_list)  # 输出: [11, 12, 22, 25, 64]

算法复杂度

时间复杂度：
外层循环执行 n 次，内层循环分别执行 n-1、n-2 … 1 次，总体比较次数为 O(n²)。
空间复杂度：
选择排序是原地排序算法，不需要额外的存储空间（除了用于交换的临时变量），因此空间复杂度为 O(1)。

总结

简单选择排序的核心在于每一次找到剩余元素中的最小值，并将其交换到当前排序区域的末尾。虽然该算法时间复杂度较高（O(n²)），但其逻辑简单、实现容易，对于数据量较小或者对性能要求不高的场景是个不错的选择。

评论留言

欢迎您，！您可以在这里畅言您的的观点与见解！

0 条评论

简单选择排序