Python为什么这个quicksort没有正确排序？

Question

我一直试图在过去的三周里使用python来实现quicksort函数，但是我总是得到这一点，并且它主要是排序的，但是有一些项目不合适。

我不认为我的理解正确快速排序，所以如果你能看到从我的代码为什么请解释。

我所选择的枢轴是在列表中的第一个目的，“低”，然后将其进行比较，以列表的其余部分。如果列表索引“low”处的对象大于列表索引“i”（在我的for循环中），那么我将“i”替换为“E”（最初索引为“low + 1”项）开关，“E”递增。即使它不切换，“我”也会增加（因为for循环）。

一旦我的循环结束后，我递减“E”（索引它在列表中比我的支点低次数最多的），然后用“低”（支点指数）

我那么快速排序其切换列表的左右两半使用“E”来确定列表分割的位置。 - 这似乎是代码无法排序的地方。

我相信这是快速排序是如何工作的，但我一直无法使它发挥作用。如果你知道我错过了什么，或者如果它只是我的一行，请告诉我。任何有关这个问题的帮助将不胜感激。

（PS。“主”功能只是路过20长度0-19值的变量列表到我的快速排序和Python的内置的排序）

import random 


def quick(A, low, high): 
    if high <= low: 
     return 
    elif high > low: 
     E = low+1 
     for i in range(E, high): 
      if A[low] > A[i]: 
       A[i], A[E] = A[E], A[i] 
       E +=1 
     E -= 1 
     A[low], A[E] = A[E], A[low] 
     quick(A, low, E-1) 
     quick(A, E+1, high) 


def main(): 
    listA = [] 
    listB = [] 
    for i in range(20): 
     int = random.randrange(0, 19) 
     listA.append(int) 
    for i in range(len(listA)): 
     listB.append(listA[i]) 
    print("List A (before sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    quick(listA, 0, len(listA)-1) 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (before sort)" + str(listB)) 
    listB.sort() 
    print("\nList A (after sort)" + str(listA)) 
    print("List B (after sort)" + str(listB)) 


main() 

Answer 1

你的问题是你每次拆分都忽略一个数字。 range(min, max)给出了包括min但不max，结束而上max-1

quick(listA, 0, len(listA)-1)

应该

quick(listA, 0, len(listA))，列表

和

quick(A, low, E-1)

应是

quick(A, low, E)。