python写一个快速排序

Question

用python写一个快速排序， 要求用到递归， 然后把partition操作分离的写出来， 求帮一下

Answer 1

有用请采纳

class Solution:
    def partition(self, nums, left, right):
        partitionValue = nums[left]
        partitionPos = left

        for i in range(left + 1, right + 1):
            if nums[i] < partitionValue:
                partitionPos += 1
                nums[partitionPos], nums[i] = nums[i], nums[partitionPos]

        nums[partitionPos], nums[left] = nums[left], nums[partitionPos]

        return partitionPos

    def quickSort(self, nums, left, right):
        if left >= right:
            return

        partition = self.partition(nums, left, right)
        self.quickSort(nums, left, partition - 1)
        self.quickSort(nums, partition + 1, right)

    def sort(self, nums):
        self.quickSort(nums, 0, len(nums) - 1)
        return nums


x = Solution()
print(x.sort([5, 3, 9, 4, 2, 7]))
print(x.sort([]))
print(x.sort([5]))
print(x.sort([5, 5, 5, 5]))
print(x.sort([-1, 6, -7, 2]))