选择排序

基本原理

>[!TIP] 选择排序（Selection Sort）基本思想： 将数组分为两个区间：左侧为已排序区间，右侧为未排序区间。每趟从未排序区间中选择一个值最小的元素，放到已排序区间的末尾，从而将该元素划分到已排序区间。

代码实现

def selection_sort(nums: list[int]):
    """选择排序"""
    n = len(nums)
    # 外循环：未排序区间为 [i, n-1]
    for i in range(n - 1):
        # 内循环：找到未排序区间内的最小元素
        minindex = i
        for j in range(i + 1, n):
            if nums[j] < nums[minindex]:
                minindex = j  # 记录最小元素的索引
        # 将该最小元素与未排序区间的首个元素交换
        nums[i], nums[k] = nums[minindex], nums[i]

选择排序算法分析

• 时间复杂度：O($n^2$)。排序法所进行的元素之间的比较次数与序列的原始状态无关，时间复杂度总是 O($n^2$)。

• 空间复杂度：O(1)。选择排序算法为原地排序算法，只用到指针变量 i、j 以及最小值位置 minIndex 等常数项的变量。

• 选择排序适用情况：选择排序方法在排序过程中需要移动较多次数的元素，并且排序时间效率比较低。因此，选择排序方法比较适合于参加排序序列的数据量较小的情况。选择排序的主要优点是仅需要原地操作无需占用其他空间就可以完成排序，因此在空间复杂度要求较高时，可以考虑选择排序。

• 排序稳定性：由于值最小元素与未排序区间第 1 个元素的交换动作是在不相邻的元素之间进行的，因此很有可能会改变相等元素的相对顺序，因此，选择排序法是一种 不稳定排序算法。