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

Question

在过去的三个星期里，我一直在尝试使用 python 实现快速排序功能，但我总是会遇到这种情况，而且大部分情况下它都会排序，但有一些项目不合适。

我认为我没有正确理解快速排序，所以如果您能从我的代码中看出原因，请解释一下。

我已选择枢轴作为列表中的第一个对象，"low"，然后将其与列表的其余部分进行比较。如果列表索引 "low" 处的对象大于列表索引 "i" （在我的 for 循环中），那么我将 "i" 切换为 "E" （最初索引到项目 "low + 1")，如果确实切换，则 "E" 递增。即使不切换，"i" 也会递增（因为 for 循环）。

循环完成后，我递减 "E"（将其索引到列表中低于我的主元的最高数字），然后将其切换为 "low"（主元索引）

然后，我使用 "E" 对列表的左右两半进行快速排序，以确定列表的拆分位置。 - 这似乎是代码无法排序的地方。

我相信这就是快速排序的工作原理，但我没能让它工作。如果您知道我遗漏了什么，或者这只是我的台词之一，请告诉我。非常感谢任何对此问题的帮助。

(PS。"main" 函数只是将长度为 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).

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

Python Why is this quicksort not sorting properly?

python

sorting

quicksort