选择排序

#选择排序

• 什么是选择排序
• 操作步骤
• Python 实现
• 时间复杂度
• 特点

#什么是选择排序

选择排序的思路很直观：每轮从剩下的数据中找出最小值，与最左边的未排序位置交换。就像老师给学生排队——每次挑出最矮的，放到队伍最前面，然后从剩下的人中再挑最矮的。

#操作步骤

以 6 1 7 8 9 3 5 4 2 为例：

第1轮: 从全部数据中找最小值
  [6  1  7  8  9  3  5  4  2]
   最小值是 1，与最左边的 6 交换
  [1] 6  7  8  9  3  5  4  2   ← 1 归位

第2轮: 从剩下的数据中找最小值
   1 [6  7  8  9  3  5  4  2]
       最小值是 2，与 6 交换
   1 [2] 7  8  9  3  5  4  6   ← 2 归位

第3轮: 继续找最小值
   1  2 [7  8  9  3  5  4  6]
          最小值是 3，与 7 交换
   1  2 [3] 8  9  7  5  4  6   ← 3 归位

  ...（继续直到全部归位）

排序完成: 1  2  3  4  5  6  7  8  9

#Python 实现

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)       # 找出最小元素的索引
        newArr.append(arr.pop(smallest))   # 取出并加入新数组
    return newArr

print(selectionSort([5, 3, 6, 2, 10]))  # => [2, 3, 5, 6, 10]

#时间复杂度

找最小值需要检查 n 个元素（O(n)），这个操作要执行 n 次：

选择排序的比较次数与冒泡排序相同，但交换次数远少于冒泡排序（每轮最多交换 1 次）。

#特点

• 交换次数少（每轮最多 1 次），适合「交换代价高」的场景
• 不稳定排序（交换可能改变相等元素的相对顺序）
• 原地排序，不需要额外空间
• 速度慢，不适合大数据量

#小结

• 选择排序每轮找最小值放到前面
• 时间复杂度 O(n²)，但交换次数比冒泡排序少
• 是快速排序的基石（理解选择排序有助于理解更复杂的排序算法）