简单选择排序算法

简单选择排序（Selection Sort）是一种直观的排序算法，主要思想是每一轮从未排序的部分中选择最小的元素，并将其放到已排序部分的末尾。这个过程持续进行，直到整个数组被排序。

简单选择排序算法步骤

1. 初始化：从数组的第一个元素开始，假设它是当前未排序部分中的最小值。
2. 寻找最小值：在未排序部分中，从当前元素向后遍历，找到最小值。
3. 交换：将找到的最小值与当前元素交换位置，这样当前元素所在的位置就确定了。
4. 重复：将范围缩小到剩下的未排序部分，重复上述过程，直到所有元素都排序完成。

代码实现 (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
        # 交换第 i 个元素和找到的最小值
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

例子

假设我们有一个数组：[64, 25, 12, 22, 11]，用简单选择排序进行排序的过程如下：

• 初始数组：[64, 25, 12, 22, 11]
• 第一次循环后：找到最小值 11，与第一个元素交换，结果为 [11, 25, 12, 22, 64]
• 第二次循环后：找到最小值 12，与第二个元素交换，结果为 [11, 12, 25, 22, 64]
• 第三次循环后：找到最小值 22，与第三个元素交换，结果为 [11, 12, 22, 25, 64]
• 第四次循环后：找到最小值 25，与第四个元素交换，结果为 [11, 12, 22, 25, 64]
• 数组已经有序，排序结束。

时间复杂度

• 时间复杂度：O(n^2)，因为在最坏情况下，需要进行大约 n*(n-1)/2 次比较。
• 空间复杂度：O(1)，因为选择排序是原地排序算法，不需要额外的空间。

简单选择排序适用于小规模数据的排序，由于其简单直观的特性，也常用于教学目的。不过，对于大型数据集，选择排序的效率不如更复杂的排序算法如快速排序或归并排序。