Блог

кто-нибудь может сказать, в чем ошибка в моем алгоритме быстрой сортировки? Я использую две точки ‘left’ и ‘right’ для сравнения с pivot и меняю местами nums [left] и nums [right], если когда nums [left]> nums [right]. когда левый индекс больше правого, разбейте и поменяйте местами nums [left] и nums [piovt], верните левый индекс.

 nums = [3,2,3,1,2,4,5,5,6]
n = len(nums)

def partition(nums,left,right,pivot):
    while left<right:
        if left<right and nums[left]<=nums[pivot]:
            left  = 1
        if left<right and nums[right]>=nums[pivot]:
            right -= 1
        elif nums[left]>nums[right]:
            nums[left],nums[right] = nums[right],nums[left]
            left  = 1
            right -= 1
    nums[left],nums[pivot] = nums[pivot],nums[left]
    return left

def quicksort(nums,low,high,pivot):
    if low<high:
        pos = partition(nums,low,high,pivot)
        quicksort(nums,low,pos-2,pos-1)
        quicksort(nums,pos 1,high-1,high)
    return nums

quicksort(nums,0,n-2,n-1)

print(nums)
  

ans: [1, 2, 2, 3, 3, 5, 5, 6, 4]

Вот несколько ошибок в вашем коде, и я переписал код для вас. Вы можете обратиться к комментарию и запустить какой-нибудь тест, чтобы выяснить.

 import random

# two pointers solution, choose the last one as pivot
def partition(nums, left, right, pivot):
    while left < right:
        # here should change < to <=, because if pivot is larger than all in nums[left:right 1], should swap nums[left] with nums[pivot]
        # here I change if to while, because you should traverse the pointer to find the place which is invalid in partition
        while left <= right and nums[left] <= nums[pivot]:
            left  = 1
        # here I change if to while, same reason above
        while left < right and nums[right] > nums[pivot]:
            right -= 1
        # you should not use elif here, because you have two ifs, the first if does not work here
        if left < right:
            nums[left], nums[right] = nums[right], nums[left]
    nums[left], nums[pivot] = nums[pivot], nums[left]
    return left


def quicksort(nums, low, high, pivot):
    if low < high:
        pos = partition(nums, low, high, pivot)
        quicksort(nums, low, pos - 2, pos - 1)
        # here is another problem: notice that nums[pivot] is the last element, not the nums[high]
        quicksort(nums, pos   1, high, high   1)
    return nums


if __name__ == '__main__':
    for _ in range(100):
        nums = [random.randrange(1, 100) for _ in range(10000)]
        n = len(nums)
        if sorted(nums) != quicksort(nums, 0, n - 2, n - 1):
            print('incorrect')
    print('success')
  

Я старался изо всех сил, чтобы помочь вам, и надеюсь, вам это понравится.

Чтобы получить средний индекс массива, вы должны установить свой pivot для быстрой сортировки в целое число n / 2.