请问我自行实现的排序代码，时间复杂度计算是否正确？

首先要纠正一个概念：你描述并实现的是插入排序，不是选择排序——选择排序的核心是在未排序区间找出最值，交换到已排序区间的末尾；而你写的逻辑是将未排序元素逐个插入到已排序区间的正确位置，这是插入排序的典型逻辑。

我今天学习时，把插入排序的逻辑理解为：将新元素加入已排序数组，然后检查该元素是否处于正确位置。未参考任何伪代码或代码，自行编写了如下代码：

vector<int> arr = {6, 5, 4, 3, 2, 1};
int arrayLength = arr.size();
for(int i = 0; i < arrayLength; i++){
    for(int j = i; j > 0; j--){
            bool flag = true;
            if(arr[j] < arr[j - 1]){
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                    flag = false;
            }
            if(flag == true) break;
    }
}
// output: 1, 2, 3, 4, 5, 6

其中flag的作用是：若新加入的元素已处于正确位置，则终止内层循环，无需继续迭代。

我看到大家多采用while循环实现插入排序：

for (int i = 0; i <= n - 1; i++) {
        int j = i;
        while (j > 0 && arr[j - 1] > arr[j]) {
            int temp = arr[j - 1];
            arr[j - 1] = arr[j];
            arr[j] = temp;
            j--;
        }
    }
// output: 1, 2,3 ,4 5, 6

我认为两种实现的最好时间复杂度（TC）为O(n)，最坏为O(n²)，但不确定该计算是否正确。我尝试了各类输入，代码在GFG上运行结果正确，但仍疑惑我的实现在时间复杂度方面是否存在问题。

解答 #

你的时间复杂度判断完全正确，两种实现的时间复杂度没有差异：

• 最好情况（数组完全有序）：你的代码中每个内层循环仅执行1次判断——arr[j] < arr[j-1]不成立，flag为true直接跳出循环；while实现则是第一次判断arr[j-1] > arr[j]就不成立，循环直接终止。两者外层循环都执行n次，总操作次数为O(n)。
• 最坏情况（数组完全逆序）：你的代码中每个内层循环会从j=i迭代到j=1，每次都要执行交换操作，内层循环执行i次；外层循环从0到n-1，总操作次数为1+2+...+(n-1) = n(n-1)/2，属于O(n²)，和while实现的最坏情况完全一致。

你的实现和while循环实现本质逻辑完全相同，只是循环结构不同——for循环加break的写法，等价于while循环的条件判断，时间复杂度没有任何问题。

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