C#数组类型选择排序时间复杂度问题：我的实现为何是O(n³)，如何优化为O(n²)

1. 时间复杂度计算校正 #

你当前的实现实际时间复杂度为O(n²)，并非O(n³)。我们可以直接统计总操作量级：外层循环共执行n次，每次循环内findSmallest遍历当前数组（长度从n递减到1）、pop操作也遍历当前数组（长度同步递减），总遍历次数为 2*(n + (n-1) + ... + 1) = n(n+1)，整体量级就是n²，你算出O(n³)是额外多算了一层不存在的循环开销。

2. 为什么资料没有考虑pop的时间开销 #

标准选择排序采用原地排序的实现逻辑，完全没有删除元素、重建数组的步骤，自然不会有pop相关的开销。
标准实现的核心逻辑是把数组划分为「已排序区间」和「未排序区间」：每次从未排序区间找到最小元素，直接和未排序区间的第一个元素交换位置即可，全程只需要做元素交换，不需要移动大量元素或者重建数组，所以资料里统计时间复杂度的时候自然不会涉及pop的开销。

3. 标准O(n²)选择排序实现方案 #

你可以直接改造为原地排序版本，不需要额外申请结果数组，也不需要自定义pop方法，优化后代码如下：

using System;
public class SortArray
{
    // 原代码方法名拼写错误，补充了缺失的字母e
    public int[] SelectionSort(int[] arr)
    {
        int length = arr.Length;
        // 外层循环：i是未排序区间的起始下标
        for (int i = 0; i < length - 1; i++)
        {
            int smallestIndex = i;
            // 遍历未排序区间找最小元素的下标
            for (int j = i + 1; j < length; j++)
            {
                if (arr[j] < arr[smallestIndex])
                {
                    smallestIndex = j;
                }
            }
            // 交换最小元素和未排序区间第一个元素
            if (smallestIndex != i)
            {
                int temp = arr[i];
                arr[i] = arr[smallestIndex];
                arr[smallestIndex] = temp;
            }
        }
        return arr;
    }
}

该版本仅需要最多n*(n-1)/2次比较、最多n-1次元素交换，没有数组重建、批量移动元素的额外开销，就是资料中给出的标准O(n²)时间复杂度的选择排序实现。

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