时间戳

首页 > 解决方案 > 如何在快速排序算法中对负数进行排序？

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

问题描述

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

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

预期成绩：

>>> 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

标签： pythonpython-3.x

解决方案

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

我想指出的一个致命错误是，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]

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

推荐阅读