python - 如何在快速排序算法中对负数进行排序？

Question

我正在尝试使用快速排序算法对任意数字的随机列表进行排序，但也不知道如何对负数进行排序，我应该处理代码的哪一部分？

不知道该怎么做，注释掉代码更改会有很大帮助。

预期结果:

>>> quickSort([3,5,-3,-1,1,2,4])
[-3, -1, 1, 2, 3, 4, 5]

实际结果:

>>> quickSort([3,5,-3,-1,1,2,4])
[1, 2, -3, -1, 3, 4, 5]

def quickSort(numList):

    n=len(numList)
    if n<=1:
        return numList
    x, left, right = numList[0], 0, n-1
    while left<right:
        if numList[left]<=x:    
            left+=1
        else:
            numList[left], numList[right]  =  numList[right], numList[left]
            right -=1
    numList[0], numList[left] = numList[left], numList[0]
    quickSort(numList[:left])
    quickSort(numList[left+1:])
    return numList

Answer 1

意外的结果不是由负数引起的，而是您的快速排序算法中的几个错误。我已经根据您的版本修复了它们，尽管它不是实现的最佳版本。可以对比修改后的代码，看评论理解。

我想指出的一个 fatal error 是，numList[:left] 将切片并生成一个新数组，当您对其进行排序时，它不会影响原始数组。因此，您应该将 array 和 left、right 索引传递给 quickSort 函数，而不是切片。

def quickSort(numList, left, right):
    # change check condition to left < right
    # n = len(numList)
    # if n <= 1:
    #     return numList
    if left < right:
        # copy left, right, it will used later
        low, high = left, right

        # it is better to abstract this block to a new function, like partition
        # pick a pivot number
        x = numList[left]
        while left < right:
            # you should use two-pointer to swap
            while left < right and numList[right] >= x:
                right -= 1
            numList[left] = numList[right]

            while left < right and numList[left] <= x:
                left += 1
            numList[right] = numList[left]
            # if numList[left] <= x:
            #     left += 1
            # else:
            #     numList[left], numList[right] = numList[right], numList[left]
            #     right -= 1

        # assign back the pivot number
        numList[left] = x
        # numList[0], numList[left] = numList[left], numList[0]

        # use origin arr and index, not slice 
        quickSort(numList, low, left-1)
        quickSort(numList, left+1, high)
        # quickSort(numList[:left])
        # quickSort(numList[left + 1:])
    return numList

测试与输出

arr = [3, 5, -3, -1, 1, 2, 4]
print(quickSort(arr, 0, len(arr)-1))
# [-3, -1, 1, 2, 3, 4, 5]

希望对您有所帮助，如果您还有其他问题，请发表评论。 :)