判断数组奇偶排序程序时间复杂度为O(n)是否正确？TA认为是O(n²)

嘿，我来帮你理清这个问题！首先要明确：不是所有包含两个循环的代码时间复杂度都是O(n²)——这是很多人容易踩的误区，你的TA大概率也在这里混淆了概念。

核心区别：嵌套循环 vs 线性遍历循环 #

O(n²)的典型场景是嵌套循环：比如外层循环执行n次，每次外层循环都触发内层循环执行n次，总操作次数是n×n，量级为n²。但如果是像你说的，总循环执行次数不超过n+1次，那你的代码大概率是线性遍历的实现（比如双指针法），这种情况时间复杂度就是O(n)。

奇偶排序的O(n)实现逻辑 #

针对“奇数放前端，偶数放后端”的需求，最常见的O(n)实现是双指针法：

• 左指针从数组头部出发，寻找第一个偶数
• 右指针从数组尾部出发，寻找第一个奇数
• 找到后交换两者位置，然后移动指针继续遍历，直到左右指针相遇
• 整个过程中，每个元素最多被左/右指针访问一次，总操作次数和数组长度n成正比，也就是O(n)

举个具体的代码例子（以Python为例）：

def sort_odd_even(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        # 左指针找偶数
        while left < right and arr[left] % 2 == 1:
            left += 1
        # 右指针找奇数
        while left < right and arr[right] % 2 == 0:
            right -= 1
        # 交换奇偶位置
        if left < right:
            arr[left], arr[right] = arr[right], arr[left]
            left += 1
            right -= 1

你看，这里虽然有3个循环，但left和right的总移动次数最多是n次（从两端到中间），所以时间复杂度是O(n)，完全符合你说的“循环执行次数不超过n+1次”的判断。

为什么TA会认为是O(n²)？ #

大概率TA见过的是另一种低效的实现：比如外层循环遍历每个元素，遇到偶数就内层循环往后找奇数交换，类似这样：

def sort_odd_even_bad(arr):
    n = len(arr)
    for i in range(n):
        if arr[i] % 2 == 0:
            # 内层循环找奇数，最坏情况每次都要遍历到末尾
            for j in range(i+1, n):
                if arr[j] % 2 == 1:
                    arr[i], arr[j] = arr[j], arr[i]
                    break

这种写法在最坏场景下（比如数组全是偶数），内层循环每次都要走n-i步，总操作次数是n+(n-1)+...+1 = n(n+1)/2，量级为n²，所以是O(n²)。但这和你的代码显然不是一回事。

结论：你的判断是对的！ #

只要你的代码总操作次数是和n线性相关的（比如双指针法），那时间复杂度就是O(n)。你可以把你的代码拿给TA，解释清楚每个元素只会被处理一次，总执行次数是线性的，就能澄清这个误解啦。

内容的提问来源于stack exchange，提问作者Mr.Mips