hello-algo 选择排序详解：O(n²) 原地排序的原理、多语言实现与稳定性分析

选择排序（Selection Sort）是《Hello 算法》排序篇讲解的最基础排序算法之一：每轮从未排序区间选出最小元素，交换到已排序区间的末尾，经过 n-1 轮即可完成整个数组的排序。本文基于仓库文档 selection_sort.md 的算法流程，结合 codes/python/chapter_sorting/selection_sort.py、codes/java/chapter_sorting/selection_sort.java 等多语言源码实现与 codes/go/chapter_sorting/selection_sort_test.go 测试用例，深入讲解选择排序的完整算法流程、代码细节、时间/空间复杂度与不稳定性成因，帮助读者彻底掌握这一原地排序算法的底层逻辑与适用边界。

算法核心思想：未排序区间逐轮缩小

选择排序的工作原理非常直观：开启一个循环，每轮从未排序区间中挑选出最小的元素，将其放到已排序区间的末尾。设数组长度为 n，整个算法流程分为 5 个阶段：

1. 初始状态：所有元素未排序，即未排序（索引）区间为 [0, n-1]。
2. 第一轮：选取区间 [0, n-1] 中的最小元素，将其与索引 0 处的元素交换。完成后，数组前 1 个元素已排序。
3. 第二轮：选取区间 [1, n-1] 中的最小元素，将其与索引 1 处的元素交换。完成后，数组前 2 个元素已排序。
4. 依此类推：每轮扫描的起点右移一位。经过 n-1 轮选择与交换后，数组前 n-1 个元素已排序。
5. 收尾：仅剩的最后一个元素必定是最大元素，无须排序，因此数组排序完成。

从源码结构看，这一思想在多语言实现中被统一抽象为「外层循环定位已排序区间边界 i、内层循环在未排序区间 [i+1, n-1] 内寻找最小值索引 k、最后交换 nums[i] 与 nums[k]」的固定模式，各语言版本仅交换写法不同（Python/Go 使用元组交换，C/Java 使用临时变量）。

Python 参考实现

仓库中的 Python 参考实现位于 selection_sort.py，共约 26 行，结构清晰、可直接运行：

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


"""Driver Code"""
if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2]
    selection_sort(nums)
    print("选择排序完成后 nums =", nums)

逐行对照算法流程可以确认三个关键细节：

• 外循环边界是 n - 1 而非 n：for i in range(n - 1) 对应流程中的「n-1 轮选择与交换」，最后一轮扫描结束后剩余的唯一元素自然落在正确位置，因此不需要第 n 轮。
• 内循环起点是 i + 1：nums[i] 本身已是未排序区间的候选最小值，所以从 k = i 初始化后只需扫描 [i+1, n-1]，if nums[j] < nums[k] 严格小于的写法保证了相等元素不会被提前记录，为后文分析不稳定性埋下伏笔。
• 每轮至多一次交换：与冒泡排序每轮可能多次交换不同，选择排序在内层循环中只记录索引 k，循环结束后才执行一次 swap，这是其交换次数上界仅为 n-1 的原因。

仓库中 C 语言版本 selection_sort.c 提供了无临时对象的原地实现，可对比查看：

/* 选择排序 */
void selectionSort(int nums[], int n) {
    // 外循环：未排序区间为 [i, n-1]
    for (int i = 0; i < n - 1; i++) {
        // 内循环：找到未排序区间内的最小元素
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (nums[j] < nums[k])
                k = j; // 记录最小元素的索引
        }
        // 将该最小元素与未排序区间的首个元素交换
        int temp = nums[i];
        nums[i] = nums[k];
        nums[k] = temp;
    }
}

C 版本中 main 函数以 {4, 1, 3, 1, 5, 2} 为样例数组调用 selectionSort(nums, n) 并借助 codes/c/utils/print_util.h 中的 printArray 打印结果，与 Python 版本的驱动数据完全一致，便于跨语言对照验证。此外，仓库还完整提供了 C++ 实现、Java 实现、Go 实现、C#、JavaScript、Rust 等十余种语言的参考代码，均遵循同一套「双循环 + 索引 k」的骨架。

测试用例验证：从样例数据看运行结果

Go 语言目录中附带了可执行的测试文件 selection_sort_test.go：

func TestSelectionSort(t *testing.T) {
	nums := []int{4, 1, 3, 1, 5, 2}
	selectionSort(nums)
	fmt.Println("选择排序完成后 nums = ", nums)
}

该测试与各语言 Driver Code 使用同一样例 [4, 1, 3, 1, 5, 2]。按算法流程手动推演：第 1 轮在 [4,1,3,1,5,2] 中选出最小值 1（索引 1）与 nums[0] 交换得到 [1,4,3,1,5,2]；第 2 轮选出 1（索引 3）交换后得到 [1,1,3,4,5,2]；第 3 轮选出 2 交换得到 [1,1,2,4,5,3]；第 4 轮选出 3 交换得到 [1,1,2,3,5,4]；第 5 轮选出 4 交换得到 [1,1,2,3,4,5]。全部 n-1 = 5 轮结束后数组有序，运行 go test 即可在 codes/go 目录下复现该验证过程。注意样例中保留了重复元素 1，恰好可以观察不稳定性（见下文分析）。

算法特性分析

时间复杂度 O(n²)：非自适应排序

外循环共执行 n-1 轮，第一轮内循环执行 n-1 次，最后一轮执行 1 次，即各轮内循环分别执行 n-1、n-2、…、2、1 次，求和为：

$$\frac{n(n-1)}{2}$$

因此时间复杂度恒为 O(n²)。关键在于，内层循环的轮次只取决于数组长度 n，与输入数据的初始分布无关——即使数组已经有序，算法仍会完整执行全部比较。这种「性能不随输入状态变化」的特点，正是非自适应排序的定义，也意味着选择排序无法利用近乎有序的输入数据来降低开销。

空间复杂度 O(1)：原地排序

从 selection_sort.py 的实现结构看，函数体内仅声明了 n、i、j、k 四个循环/索引变量，交换操作直接在原数组上完成，没有引入与 n 相关的额外数据结构。因此额外空间为常数级 O(1)，属于原地排序（in-place sort）。这也是选择排序在内存受限场景下的主要优势。

非稳定排序：交换可能打乱相等元素的相对顺序

稳定性指相等元素在排序后是否保持原有的相对先后顺序。选择排序是非稳定排序，原因可以从源码中 if nums[j] < nums[k] 与「整轮结束后统一交换」这两个细节推导出来：内层循环只更新索引 k 而不提前交换，当最小值出现在未排序区间深处时，它与 nums[i] 的交换会跨越若干元素，其中可能包含与 nums[i] 相等的元素，从而改变它们的相对顺序。

以文档给出的非稳定示例说明：若某轮中 nums[i] 处的 2 需要与更深位置的 2 交换，交换后先出现的 2 反而排到了后出现的 2 右侧，相等元素的相对顺序被破坏。这也解释了为何在对稳定性有要求的场景（例如多关键字排序）中，应选择插入排序等稳定算法，而不是选择排序。

小结：选择排序的适用定位

综合以上分析，选择排序的核心特性可以归纳为：

特性	结论	说明
时间复杂度	O(n²)（最好/最坏/平均）	非自适应，与输入分布无关
空间复杂度	O(1)	原地排序，仅需常数额外空间
稳定性	不稳定	跨区间的单次交换可能打乱相等元素顺序
交换次数	至多 n-1 次	每轮内循环结束后仅执行一次交换

选择排序实现简单、交换次数少，适合小规模数据或对交换操作代价敏感的场景；而对于大规模数据，建议参考同章的 快速排序、归并排序 或 堆排序 等 O(n log n) 算法。完整的跨语言对照实现可在 codes/python/chapter_sorting、codes/java/chapter_sorting、codes/go/chapter_sorting 等目录中按语言目录查阅。