排序数组的平方，为什么Sorted（）方法比O（n）方法快？

Question

我正在研究leetcode算法问题977. Squares of a Sorted Array.

为什么使用内置排序方法的提交要比下面的o（n）遍历方法快？你知道吗

输入是带有整数的排序（非降序）列表。你知道吗

提交样品：

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        return sorted(x*x for x in A)

我的260毫秒提交：

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        start = 0
        end = len(A)-1

        B = []

        while start <= end:
            if abs(A[start]) >= abs(A[end]):
                B.append(A[start] * A[start])
                start += 1
            else:
                B.append(A[end] * A[end])
                end -= 1
        B.reverse()
        return B

Answer 1

您可以对所有内容进行预平方处理（因此不需要abs()，尤其不需要对单个元素重复abs()调用）：

C = [x*x for x in A]

start = 0
end = len(A)-1

B = []

while start <= end:
    if C[start] >= C[end]:
        B.append(C[start])
        start += 1
    else:
        B.append(C[end])
        end -= 1
B.reverse()
return B

但我没量过。例如，就地预平方可能会表现更好。你知道吗