使用Python快速排序实现

Question

def partition(lst, low,high, pivot,col):
    lst[high],lst[pivot] = lst[pivot],lst[high]
    pivot = high
    i = low
    while i +1 <pivot:
        if lst[i][col] > lst[pivot][col]:
            lst[pivot], lst[pivot-1] = lst[pivot-1], lst[pivot]
            lst[i],lst[pivot] = lst[pivot],lst[i]
            pivot -= 1
        else:
            i +=1
    if lst[i][col] > lst[pivot][col]:
        lst[i],lst[pivot] = lst[pivot],lst[i]
        pivot -= 1
    return pivot
def quick(lst,low,high,col,ascending):
    if low >= high:
        return
    else:
        #print(low,high)
        pivot = random.randint(low,high)
        #print(pivot)
        part_point = partition(lst,low,high,pivot,col)
        print(part_point,high)
        quick(lst,low,part_point-1,col,ascending)
        quick(lst,part_point+1, high,col, ascending)

我正在使用Python学习算法，这是我对QuickSort的实现。尽管在某些情况下运行良好，但在大多数情况下它都超过了递归深度。我认为我的执行中存在一些错误，我缺少这一点。

Answer 1

我不习惯看到分区方法中的枢轴变化。通常，枢轴将其设置为数组中的左元素。可以选择使用随机元素A [k]切换，其中低＆lt; = k＆lt; =高。通常，分区方法使用两个变量I和j，其中i是计数器，因为分区通过数组向左到右传递，J显示了最大的元素A [J]，因此A [J]＆lt; = Pivot。[j]处的值在分区函数末尾用[低]交换，并且该函数返回j。

Sedgewick和Wayne在其网站上就此主题有一个奇迹章节：https：//algs4.cs.princeton.edu/23quicksort/