选择排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

扫描整个列表，找出最小的元素。把它与下标 0 处的元素交换；此时下标 0 就确定了。从下标 1 开始扫描剩下的部分，找出最小的，交换到下标 1。如此继续，直到只剩一个元素，它必然是最大的。

与冒泡排序和插入排序不同，选择排序不会因为输入已经有序而受益：它仍然必须扫描每个剩余元素，才能确认找到的是最小值。

逐步演示

对 [64, 25, 12, 22, 11] 排序。竖线之前的部分已排好序且已确定。

五个元素四步完成，共 4 + 3 + 2 + 1 = 10 次比较和 3 次真正的交换。

Python 实现

def selection_sort(items):
    """Sort a list in place, ascending. Returns the same list."""
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items
print(selection_sort([64, 25, 12, 22, 11]))   # [11, 12, 22, 25, 64]
print(selection_sort([2, 1]))                 # [1, 2]

外层循环执行 n − 1 次，因为最后剩下的元素自然就在正确位置。内层循环只记录下标；每个外层步骤只交换一次。

时间与空间复杂度

写入次数少是选择排序真正的优点。如果写内存的代价远高于读取（如某些闪存，或移动大型记录时），减少写入就很重要。循环排序（cycle sort）把这一点做到了极致，每个元素最多只写一次。

稳定性：选择排序为什么不稳定

稳定的排序会保持相等元素原有的相对顺序。选择排序中的远距离交换，可能让一个元素越过与它相等的另一个元素。

def selection_sort_by_key(items, key):
    n = len(items)
    for i in range(n - 1):
        m = min(range(i, n), key=lambda j: key(items[j]))
        items[i], items[m] = items[m], items[i]
    return items
cards = [("4", "hearts"), ("4", "spades"), ("2", "clubs")]
print(selection_sort_by_key(cards, key=lambda c: c[0]))
# [('2', 'clubs'), ('4', 'spades'), ('4', 'hearts')]  order of the 4s changed

2 与红桃 4 交换，使红桃 4 跑到了黑桃 4 的后面。稳定的版本也是有的：不做交换，而是取出最小值并插入到位置 i，其他元素右移。这样能保持顺序，但每步要付出 O(n) 次写入。

选择排序与其他排序算法的比较

堆排序是用了更好数据结构的选择排序：它同样反复选出剩余元素中最大的，但借助二叉堆在 O(log n) 内找到它，而不是 O(n) 的扫描，总复杂度因此降到 O(n log n)。

何时使用选择排序

在实际的 Python 代码中请使用内置的 sorted() 或 list.sort()。选择排序值得了解的场合包括：作为教学示例、在资源受限环境中处理很小的定长数组，以及必须尽量减少写入次数时。它也是常见的考试和面试题，通常的问法是：追踪每一步、数出比较和交换的次数，并解释它为什么不稳定。