如何分步推导选择排序的时间复杂度？附实现代码

第一步：拆解代码核心逻辑 #

先聚焦selectionSort方法的核心执行结构：

static void selectionSort(int[] arr) {
    // 外层循环：划分已排序/未排序区间
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i; // 初始化未排序区间的最小值索引
        // 内层循环：在未排序区间中查找最小值索引
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[min] > arr[j]) {
                min = j; // 更新最小值索引
            }
        }
        // 交换当前位置与最小值位置的元素
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

分析时间复杂度时，我们只关注执行次数随输入规模n（数组长度）变化的核心操作，这里的核心是内层循环里的arr[min] > arr[j]比较操作（交换操作是固定次数，不影响量级）。

第二步：统计循环执行次数 #

设数组长度为n，逐层统计循环的执行次数：

• 外层循环：条件为i < n - 1，i从0取到n-2，总共执行n-1次。
• 内层循环（对应每轮外层循环）：
  • 当i=0时，j从1到n-1，执行n-1次
  • 当i=1时，j从2到n-1，执行n-2次
  • 当i=2时，j从3到n-1，执行n-3次
  • ...
  • 当i=n-2时，j从n-1到n-1，执行1次

第三步：计算核心操作总执行次数 #

把每轮内层循环的执行次数相加，得到总比较次数T(n)：
$$
T(n) = (n-1) + (n-2) + (n-3) + ... + 2 + 1
$$
这是首项为1、末项为n-1、项数为n-1的等差数列，用求和公式计算：
$$
T(n) = \frac{(首项 + 末项) \times 项数}{2} = \frac{(1 + n-1) \times (n-1)}{2} = \frac{n(n-1)}{2}
$$
展开后得到：
$$
T(n) = \frac{1}{2}n^2 - \frac{1}{2}n
$$

第四步：用大O表示法简化 #

大O表示法只关注n趋近于无穷大时的最高量级项，忽略低阶项和常数系数：

• 当n足够大时，$\frac{1}{2}n^2$是主导项，$\frac{1}{2}n$的影响可以忽略
• 同时去掉常数系数$\frac{1}{2}$

最终推导得出选择排序的时间复杂度为：
$$
T(n) = O(n^2)
$$

补充说明 #

每轮外层循环后的交换操作总共执行n-1次，属于O(n)量级，和主导的O(n²)相比可以忽略，不影响最终结论。

内容的提问来源于stack exchange，提问作者Sara Hamzah