LeetCode排序数组问题：Quicksort实现报错，求排查（O(nlogn)要求）

我在解决LeetCode的「排序数组」问题，题目要求时间复杂度为O(n*logn)。我用快速排序实现，但在18个测试用例里第17个运行失败，代码如下：

class Solution(object):
    def sortArray(self, nums):
        self.quickSort(nums, 0, len(nums)-1) #=> [arr, low, high] it's for binary search
        return nums


    def quickSort(self, arr, low, high):
        mid = (low + high) // 2
        arr[mid], arr[high] = arr[high], arr[mid] # pick the mid as pivot every time
        if low < high:
            pivot = self.partition(arr, low, high)
            self.quickSort(arr, low, pivot-1)
            self.quickSort(arr, pivot+1, high)

    def partition(self, arr, low, high):
        i = low
        pivot = arr[high]
        for n in range(low, high):
            if arr[n] < pivot:
                arr[i], arr[n] = arr[n], arr[i]
                i += 1
        arr[high], arr[i] = arr[i], arr[high]
    return i 

错误原因与修正 #

你的代码核心问题是**partition函数里的return i缩进错误**——它现在位于函数外部，属于类的顶级代码，导致partition函数没有返回值。当quickSort调用partition时，pivot会被赋值为None，后续执行self.quickSort(arr, low, pivot-1)时会触发类型错误，这就是测试用例失败的直接原因。

修正后的partition函数：

def partition(self, arr, low, high):
    i = low
    pivot = arr[high]
    for n in range(low, high):
        if arr[n] < pivot:
            arr[i], arr[n] = arr[n], arr[i]
            i += 1
    arr[high], arr[i] = arr[i], arr[high]
    return i  # 缩进回到函数内部

另外提一句：你注释里提到的「Binary Search」并没有在代码中用到，快速排序本身的平均时间复杂度就是O(nlogn)，完全符合题目要求，修正缩进后即可正常通过测试。

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