Python 中的快速排序代码

Question

我正在尝试在 Python 中编写快速排序代码，但无法更正错误？我该如何修复所有这些错误？逻辑有问题吗？

Traceback (most recent call last):  
  line 35, in module  
  line 5, in quicksort  
  line 3, in quicksort  
  line 30, in partition  
IndexError: list index out of range

这是我的代码：

def quicksort(a, beg, end):
   if beg < end:
     split = partition(a, beg, end)
     quicksort(a, beg, split-1)
     quicksort(a, split+1, end)

def partition(a, beg, end):
    left = beg
    right = end
    pivot = left
    done = True
    while done:
        while a[pivot] <= a[right] and pivot != right:
            right = right - 1
        if pivot == right:
           done = False
        elif a[pivot] > a[right] :
           temp = a[right]
           a[right] = a[pivot]
           a[pivot] = a[temp]
           pivot = right 

        while a[pivot] >= a[left] and pivot != left:
            left = left + 1
        if pivot == left:
            done = False
        elif a[pivot] < a[left] :
           temp = a[left]
           a[left] = a[pivot]
           a[pivot] = a[temp]
           pivot = left
    return pivot             

a = [4, 5, 7, 3, 6, 22, 45, 82]
quicksort(a, 0, len(a)-1)
print(a)

Answer 1

    elif a[pivot] > a[right] :
       temp = a[right]
       a[right] = a[pivot]
       a[pivot] = a[temp]
       pivot = right

请注意，您将 a[pivot] 设置为 a[temp]。您需要将其设置为 temp.

这里：

   elif a[pivot] < a[left] :
       temp = a[left]
       a[left] = a[pivot]
       # a[pivot] = a[temp]
       a[pivot] = temp
       pivot = left

更好的是，使用元组解包——你不需要临时文件：

    elif a[pivot] > a[right] :
       a[pivot], a[right] = a[right], a[pivot]
       """
       temp = a[right]
       a[right] = a[pivot]
       a[pivot] = a[temp]
       """

Python 中的快速排序代码

quicksort code in Python

python

quicksort