用python快速排序算法

Question

我把第一个元素作为起始值和枢轴值。当枢轴值小于结束值时，递增起始位置。当中枢值大于结束值时，减少结束位置。另外，当每次传递完成后，交换起始位置和结束位置。如果起始位置与结束位置交叉，那么我将交换枢轴和结束元素。

def partition(arr, lb, ub):
  pivot = arr[lb]  
  start = lb
  print('start', start)
  end = ub
  print('end', end)
  while start <= end:

    while arr[start] <= pivot:
          start += 1
    while arr[end] >= pivot:
          end -= 1
    if start <= end:
      arr[start], arr[end] = arr[end], arr[start]
    else:
      arr[end], arr[lb] = arr[lb], arr[end]
    return end 

def quickSort(arr, lb, ub): 
    if lb >= ub:
      return 0
    loc = partition(arr, lb, ub)
    quickSort(arr, lb, loc-1) 
    quickSort(arr, loc+1, ub) 

arr = [10, 4, 7, 3, 8, 6, 9, 1, 5, 2] 

n = len(arr)
print(n)
quickSort(arr, 0, len(arr) -1) 
print ("Sorted array is:") 
for i in range(n): 
    print("%d" % arr[i])

我得到以下错误。 IndexError

---> quickSort(arr, 0, len(arr) -1)

Error in partition(arr, lb, ub)

---> while arr[start] <= pivot:


IndexError: list index out of range 

谁能告诉我这段代码有什么问题？

Answer 1

这是导致错误的直接原因。

    while arr[start] <= pivot:
          start += 1
    while arr[end] >= pivot:
          end -= 1

你没有检查是否 start 不大于 ub (以及是否 end 不小于 lb). 这是你应该做的。

        while start < ub and arr[start] <= pivot:
            start += 1
        while end > lb and arr[end] >= pivot:
            end -= 1

但是，还有一件事是错误的。

    while start <= end:

应该是

    while start < end:

因为对于弱不等式来说，循环永远不会结束--它达到的状态是 start == end 并在那里无休止地循环。这里的不等式。

       if start <= end:

也应该是一个强烈的不等式，否则对于 start == end 你在交换 arr[end] 与 arr[start] 而不是 arr[lb] (即pivot)。

最后，你发在这里的代码格式化出了问题，所以我冒昧的修正了一下。

Answer 2

不知道你是否还没有解决，但这里有一个修改后的分区函数。

def partition(arr, lb, ub):
  pivot = arr[lb]
  start = lb + 1
  print('start', start)
  end = ub
  print('end', end)
  while start <= end:
    while start <= end and arr[start] <= pivot:
      start += 1
    while end >= start and arr[end] > pivot:
      end -= 1
    if start < end:
      arr[start], arr[end] = arr[end], arr[start]
  if start >= end:
    start -= 1
  arr[start], arr[lb] = arr[lb], arr[start]
  return start

Answer 3

你需要检查是否 start 递增量不超过 end 如：

while arr[start] <= pivot:
    if start<end:
          start += 1