使用Python内置sort()一行代码解决仅两元素交换的有序数组排序是否正确？

一、结果正确性：完全没问题 #

你的一行代码解法（比如调用arr.sort()直接修改原数组，或者用sorted(arr)返回新数组）确实能输出符合要求的正确结果。针对题目给出的所有输入示例：

• 输入[3,8,6,7,5,9]，输出[3,5,6,7,8,9]
• 输入[3,5,6,9,8,7]，输出[3,5,6,7,8,9]
• 输入[3,5,7,6,8,9]，输出[3,5,6,7,8,9]
  都能准确得到排序后的目标数组。

二、时间复杂度：不符合题目要求 #

题目明确要求**在线性时间（O(n)）**内完成排序，但Python内置的sort()函数实现的是Timsort算法，它的时间复杂度是O(n log n)（不管是平均情况还是最坏情况）——哪怕数组只有两个元素位置错误，它也达不到线性时间的要求。

如果要满足题目中的线性时间约束，你需要定位到那两个被交换的元素并直接交换它们，具体思路可以是：

• 遍历数组，找到第一个满足arr[i] > arr[i+1]的位置i
• 从数组末尾往前遍历，找到第一个满足arr[j-1] > arr[j]的位置j
• 交换arr[i]和arr[j]，整个过程只需要O(n)的时间就能完成排序

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