简单选择排序实现简单易懂，适用于数据规模较小，对排序效率要求不高的场景-CSDN博客

本文链接：https://blog.csdn.net/blog_programb/article/details/147742785

1. 基本概念

简单选择排序（Simple Selection Sort）是一种基于比较的排序算法。它的基本思想是：每次从未排序部分中找出最小（或最大，这里以升序为例，即找最小）的元素，将其与未排序部分的第一个元素交换位置，逐步将未排序部分元素减少，使已排序部分元素增多，直至整个序列有序。

2. 算法步骤

设待排序数组为 arr，长度为 n ：

从第一个元素（即 arr[0] ）开始，将其视为当前未排序部分的最小值，记录其索引为 min_index ，初始值为当前位置索引。
遍历未排序部分（从当前位置的下一个元素 arr[1] 到数组末尾 arr[n - 1] ），依次将每个元素与当前记录的最小值比较。如果找到比当前最小值更小的元素，更新 min_index 为该更小元素的索引。
遍历完未排序部分后，将找到的最小元素（索引为 min_index ）与未排序部分的第一个元素（即最初选定的位置）交换位置。
重复上述步骤，每次将当前未排序部分的第一个元素作为起始点，直到整个数组都变为已排序状态。

3. 代码实现（Python 语言）

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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

4. 算法分析

时间复杂度：
- 无论数组初始状态如何，简单选择排序都要进行固定次数的比较操作。外层循环执行 n - 1 次，内层循环在第 i 次外层循环时执行 n - i 次。总的比较次数为 ((n - 1) + (n - 2) + \cdots + 1 = \frac{n(n - 1)}{2}) ，所以时间复杂度为 (O(n^2)) 。
- 移动操作次数较少，最好情况（数组已有序）下移动次数为 0 ；最坏情况（数组逆序）下移动次数为 (3(n - 1)) （每次交换涉及 3 次移动操作），平均移动次数也相对较少，但由于比较操作占主导，整体时间复杂度仍为 (O(n^2)) 。
空间复杂度：简单选择排序在排序过程中只需要常数级的额外空间，用于临时存储最小元素索引和进行元素交换时的临时变量等，空间复杂度为 (O(1)) 。
稳定性：简单选择排序是不稳定的排序算法。例如序列 [5, 5, 3] ，在排序过程中，第一个 5 可能会与 3 交换位置，导致两个 5 的相对顺序发生改变。

5. 应用场景

简单选择排序实现简单易懂，适用于数据规模较小，对排序效率要求不高的场景。例如在一些简单的教学示例、测试代码或者对少量数据进行排序的程序中可以使用。但当数据规模较大时，由于其 (O(n^2)) 的时间复杂度，性能较差，不适合用于对大量数据的排序处理，此时更推荐使用时间复杂度更低的排序算法，如快速排序、归并排序等。
简单选择排序（Simple Selection Sort）是一种简单直观的排序算法。它的基本思想是从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余未排序元素中寻找最小（或最大）元素，然后放到已排序序列的末尾。这个过程重复进行，直到所有元素均排序完毕。

一、简单选择排序的算法原理

简单选择排序的核心思想是逐步构建有序序列。具体步骤如下：

初始化：假设数组的第一个元素是有序的。
选择最小（或最大）元素：
- 从数组的未排序部分（从当前索引到数组末尾）中找到最小（或最大）的元素。
- 将找到的最小（或最大）元素与未排序部分的第一个元素交换位置。
重复上述过程：逐步缩小未排序部分的范围，直到整个数组都变为有序。

二、简单选择排序的实现步骤

假设有一个数组arr，长度为n，简单选择排序的步骤如下：

外层循环：从第一个元素开始，逐步将每个元素放到正确的位置。
- 外层循环变量i从0到n-2。
内层循环：从第i个元素开始，找到未排序部分的最小元素。
- 内层循环变量j从i+1到n-1。
- 记录最小元素的索引min_index。
交换元素：将找到的最小元素与第i个元素交换位置。

三、简单选择排序的代码示例

以下是简单选择排序的Python代码实现：

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):  # 外层循环：从第一个元素开始
        min_index = i  # 假设当前索引的元素是最小的
        for j in range(i + 1, n):  # 内层循环：从第i+1个元素开始
            if arr[j] < arr[min_index]:  # 找到更小的元素
                min_index = j
        # 交换最小元素与当前索引的元素
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

# 示例
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:", arr)

四、简单选择排序的性能分析

时间复杂度：
- 最好情况：即使数组已经是有序的，也需要进行完整的比较和交换操作，时间复杂度为(O(n^2))。
- 最坏情况：数组完全逆序时，时间复杂度为(O(n^2))。
- 平均情况：时间复杂度为(O(n^2))。
空间复杂度：简单选择排序只需要一个临时变量来交换元素，因此空间复杂度为(O(1))。
稳定性：简单选择排序是一种不稳定的排序算法，因为在交换元素时，相等元素的相对顺序可能会被改变。