用Python实现快速排序

Question

我完全是Python的新手，正在尝试在其中实现快速排序算法。 请问是否有人能帮我完成我的代码呢？

我不知道如何将这三个数组连接起来并打印出它们。

def sort(array=[12,4,5,6,7,3,1,15]):
    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            if x == pivot:
                equal.append(x)
            if x > pivot:
                greater.append(x)
            sort(less)
            sort(pivot)
            sort(greater)

- user2687481

---

要合并列表，您可以使用加号运算符 my_list = list1 + list2 + ...。或者将列表解包到新列表中 my_list = [*list1, *list2]。 - Mark Mishyn

快速排序算法应该是一种原地算法，但你的代码并不是。此外，追加操作不一定在常数时间内执行。 - user1196549

Answer 1

def sort(array):
    """Sort the array by using quicksort."""

    less = []
    equal = []
    greater = []

    if len(array) > 1:
        pivot = array[0]
        for x in array:
            if x < pivot:
                less.append(x)
            elif x == pivot:
                equal.append(x)
            elif x > pivot:
                greater.append(x)
        # Don't forget to return something!
        return sort(less)+equal+sort(greater)  # Just use the + operator to join lists
    # Note that you want equal ^^^^^ not pivot
    else:  # You need to handle the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

- Brionius

---

你可以在for循环中用elif和else来替换第二个if，以避免进行不必要的比较。 - SlimPDX

这句话听起来更像是归并排序而不是快速排序。 - Emad Mokhtar

这实际上是我在任何地方找到的用于快速排序的最佳且最易读的 Python 代码。 没有索引，没有辅助函数，清晰地展示了算法的主要思路（分治）。（数组的默认值相当不必要） - cmantas

它将使用比原地排序更多的内存，请参见suquant的答案以获取原地快速排序的方法。 - John

非常易读，但这是否违背了快速排序的目的，因为这样做无法实现"原地"排序？@RasmiRanjanNayak 这里的排序是用户定义的函数（一个递归调用），不是任何内置函数。 - Maksood

Answer 2

不使用额外内存的快速排序（原地排序）

用法：

array = [97, 200, 100, 101, 211, 107]
quicksort(array)
print(array)
# array -> [97, 100, 101, 107, 200, 211]

def partition(array, begin, end):
    pivot = begin
    for i in range(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            array[i], array[pivot] = array[pivot], array[i]
    array[pivot], array[begin] = array[begin], array[pivot]
    return pivot



def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)

- suquant

---

if end is None: 这段代码会被频繁检查，但只有一次会是True。你应该将其放在一个封装函数中，这样它就只会被调用一次。 - Gillespie

其实，@mksteve是正确的，这一行是错误的。此外，array[pivot]，array[begin] = array[begin]，array[pivot]应该将begin替换为end。 - Ryan J McCall

虽然原地排序很不错，但是当有大量项目时，它会变得很慢并因递归深度达到最大值而出现错误。请参见https://repl.it/@almenon/quicksorts?language=python3 - Almenon

@mksteve和Ryan，我测试了这些更改，它破坏了排序。 - aljgom

@Almenon 嗯，你这么说不太公平。你用相同的输入运行了100次排序，这意味着就地排序在第二次调用时得到了一个已经排序好的输入。如果你使用 timeit('randomList[:]=qsort(randomList)', ...) 来进行前两次排序以使其公平，那么它们也会达到最大递归深度。 - Kelly Bundy

Answer 3

还有另一个简洁而美丽的版本

def qsort(arr):
    if len(arr) <= 1:
        return arr
    else:
        return qsort([x for x in arr[1:] if x < arr[0]])
        + [arr[0]]
        + qsort([x for x in arr[1:] if x >= arr[0]])

让我详细解释上面的代码

1. 将数组的第一个元素 arr[0] 作为基准值

   [arr[0]]

2. 使用List Comprehension对小于基准值的数组元素进行 qsort

   qsort([x for x in arr[1:] if x < arr[0]])

3. 使用 List Comprehension 对大于基准值的数组元素进行 qsort

   qsort([x for x in arr[1:] if x >= arr[0]])

- zangw

---

可能导致投票反对的原因：1）在已经排序或反转的数组上具有二次运行时间 2）解决方案不是原地执行。因此，实现效果很糟糕，抱歉。 - alisianoi

完全无法阅读，你真的想要减少行数吗？代码由机器解释，但是由人类理解。 - jsmedmar

@AlfredoGallegos，快速排序的整个重点在于它是原地排序，如果你要这样做，就可以实现归并排序。 - Padraic Cunningham

这些评论是真实的吗？如果您想要性能，请使用“sorted”，这显然是为教育目的而设计的。而且它易读性好，比被采纳的答案更易读。 - Nobilis

就我所知，这是最易读的实现方式。它比其他任何答案更好地展示了算法的递归结构。当然，性能可能不会太好。 - Solveit

Answer 4

这个答案 是一个适用于 Python 2.x 的原地快速排序。我的答案是对来自 Rosetta Code 的原地解决方案的解释，同时还适用于 Python 3：

import random

def qsort(xs, fst, lst):
    '''
    Sort the range xs[fst, lst] in-place with vanilla QuickSort

    :param xs:  the list of numbers to sort
    :param fst: the first index from xs to begin sorting from,
                must be in the range [0, len(xs))
    :param lst: the last index from xs to stop sorting at
                must be in the range [fst, len(xs))
    :return:    nothing, the side effect is that xs[fst, lst] is sorted
    '''
    if fst >= lst:
        return

    i, j = fst, lst
    pivot = xs[random.randint(fst, lst)]

    while i <= j:
        while xs[i] < pivot:
            i += 1
        while xs[j] > pivot:
            j -= 1

        if i <= j:
            xs[i], xs[j] = xs[j], xs[i]
            i, j = i + 1, j - 1
    qsort(xs, fst, j)
    qsort(xs, i, lst)

如果您愿意放弃原地排序的特性，下面是另一种更好地说明快速排序基本思想的版本。除了可读性外，它的另一个优点是它是稳定的（相等的元素在排序后的列表中以它们在未排序列表中的顺序出现）。这种稳定性质在上面介绍的 less memory-hungry 的原地实现中不成立。

如果您愿意放弃原地排序的特性，下面是另一种更好地说明快速排序基本思想的版本。除了可读性外，它的另一个优点是它是稳定的（相等的元素在排序后的列表中以它们在未排序列表中的顺序出现）。这种稳定性质在上面介绍的 less memory-hungry 的原地实现中不成立。

def qsort(xs):
    if not xs: return xs # empty sequence case
    pivot = xs[random.choice(range(0, len(xs)))]

    head = qsort([x for x in xs if x < pivot])
    tail = qsort([x for x in xs if x > pivot])
    return head + [x for x in xs if x == pivot] + tail

- alisianoi

---

感谢分享这个解决方案。你能帮我们理解一下时间复杂度吗？我看到递归会调用15次。其中8次是对该函数的有效调用。这是否意味着第一个解决方案的时间复杂度为O(n)，并且空间复杂度为O(1)，因为它是原地排序？ - ForeverLearner

@Tammy，看起来你对大O符号的理解有误。此外，我并不真正理解你的问题。你可以单独提出一个问题吗？最后，快速排序作为一种算法，在O(n logn)时间和O(n)空间内运行。 - alisianoi

我的错。我为什么要数递归次数？ :-) 好吧，15次递归等于[1次调用（第0级）+ 2次调用（第1级分区）+ 4次调用（第2级分区）+ 8次调用（第3级分区或叶节点）]。因此，高度仍然是(lg8 + 1) = lgn。每个级别中的总计算量为c1(某些成本) * n。因此O（n lgn）。空间复杂度，对于一次原地交换= O（1）。因此对于n个元素= O（n）。感谢指针。 - ForeverLearner

这绝对是互联网上最好的Python快速排序算法，但可悲的是它被许多O(n)空间复杂度的解决方案所掩盖。 - Sasha Kondrashov

如果有人想让qsort返回数字列表而不是任意嵌套子列表的列表，请考虑使用此方法将其展平：https://stackoverflow.com/a/53778278/635160 - Gabriel Fair

Answer 5

使用Python进行快速排序

在现实生活中，我们应该始终使用Python提供的内置排序。然而，理解快速排序算法是有益的。

我的目标是将这个主题分解，使读者能够轻松理解并复制它，而不必返回参考材料。

快速排序算法基本上是这样的：

1. 选择一个基准数据点。
2. 将所有小于（下面）基准的数据点移动到基准下方的位置 - 将大于或等于（上面）基准的数据点移动到基准上方的位置。
3. 将算法应用于基准上方和下方的区域

如果数据是随机分布的，则选择第一个数据点作为基准相当于随机选择。

易读的示例：

首先，让我们看一个易读的示例，它使用注释和变量名指向中间值：

def quicksort(xs):
    """Given indexable and slicable iterable, return a sorted list"""
    if xs: # if given list (or tuple) with one ordered item or more: 
        pivot = xs[0]
        # below will be less than:
        below = [i for i in xs[1:] if i < pivot] 
        # above will be greater than or equal to:
        above = [i for i in xs[1:] if i >= pivot]
        return quicksort(below) + [pivot] + quicksort(above)
    else: 
        return xs # empty list

重新陈述这里展示的算法和代码 - 我们将大于基准点的值移到右边，将小于基准点的值移到左边，然后将这些分区传递给同一函数以进一步排序。

精简版:

此可压缩为88字符：

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

为了看到我们是如何达成这一点的，首先需要拿出我们易读的示例，删除注释和文档字符串，并在原地找到枢轴点：

def quicksort(xs):
    if xs: 
        below = [i for i in xs[1:] if i < xs[0]] 
        above = [i for i in xs[1:] if i >= xs[0]]
        return quicksort(below) + [xs[0]] + quicksort(above)
    else: 
        return xs

现在在原地找到下面和上面的内容：

def quicksort(xs):
    if xs: 
        return (quicksort([i for i in xs[1:] if i < xs[0]] )
                + [xs[0]] 
                + quicksort([i for i in xs[1:] if i >= xs[0]]))
    else: 
        return xs

现在，我们知道如果and返回false，则返回前一个元素，否则如果它为true，则评估并返回下一个元素，因此我们有：

def quicksort(xs):
    return xs and (quicksort([i for i in xs[1:] if i < xs[0]] )
                   + [xs[0]] 
                   + quicksort([i for i in xs[1:] if i >= xs[0]]))

由于Lambda表达式返回单个表达式，而我们已经简化为单个表达式（尽管它变得更加难以阅读），因此现在我们可以使用Lambda：

quicksort = lambda xs: (quicksort([i for i in xs[1:] if i < xs[0]] )
                        + [xs[0]] 
                        + quicksort([i for i in xs[1:] if i >= xs[0]]))

为了简化我们的示例，将函数和变量名称缩短为一个字母，并消除不必要的空格。

q=lambda x:x and q([i for i in x[1:]if i<=x[0]])+[x[0]]+q([i for i in x[1:]if i>x[0]])

请注意，这个lambda（像大多数代码高尔夫一样）风格相当糟糕。

使用Hoare分区方案的原地快速排序

先前的实现创建了许多不必要的额外列表。如果我们可以原地完成，就会避免浪费空间。

以下实现使用Hoare分区方案，您可以在维基百科上阅读更多（但我们显然通过使用while循环语义而非do-while以及将缩小步骤移到外部while循环的末尾，每个partition()调用已删除了最多4个冗余计算）。

def quicksort(a_list):
    """Hoare partition scheme, see https://en.wikipedia.org/wiki/Quicksort"""
    def _quicksort(a_list, low, high):
        # must run partition on sections with 2 elements or more
        if low < high: 
            p = partition(a_list, low, high)
            _quicksort(a_list, low, p)
            _quicksort(a_list, p+1, high)
    def partition(a_list, low, high):
        pivot = a_list[low]
        while True:
            while a_list[low] < pivot:
                low += 1
            while a_list[high] > pivot:
                high -= 1
            if low >= high:
                return high
            a_list[low], a_list[high] = a_list[high], a_list[low]
            low += 1
            high -= 1
    _quicksort(a_list, 0, len(a_list)-1)
    return a_list

不确定我是否彻底测试了它：

def main():
    assert quicksort([1]) == [1]
    assert quicksort([1,2]) == [1,2]
    assert quicksort([1,2,3]) == [1,2,3]
    assert quicksort([1,2,3,4]) == [1,2,3,4]
    assert quicksort([2,1,3,4]) == [1,2,3,4]
    assert quicksort([1,3,2,4]) == [1,2,3,4]
    assert quicksort([1,2,4,3]) == [1,2,3,4]
    assert quicksort([2,1,1,1]) == [1,1,1,2]
    assert quicksort([1,2,1,1]) == [1,1,1,2]
    assert quicksort([1,1,2,1]) == [1,1,1,2]
    assert quicksort([1,1,1,2]) == [1,1,1,2]

结论

这个算法经常在计算机科学课程中教授，并在工作面试中被要求。它帮助我们思考递归和分治。

由于Python内置的timsort算法非常高效，并且我们有递归限制，因此快速排序在Python中并不是很实用。我们期望使用list.sort原地对列表进行排序，或使用sorted创建新的排序列表 - 两者都需要key和reverse参数。

- Russia Must Remove Putin

---

你的 partition 函数似乎对于 partition([5,4,3,2,1], 0, 4) 不起作用。期望返回索引为 4，但它返回了 3。 - matino

@matino 这个期望从哪里来的？我相信我在编写答案时简化了算法（如维基百科所述），但我可能是错的，或者效率不高。如果你能找到一个完整的快速排序函数失败的测试用例，那将很有帮助。 - Russia Must Remove Putin

@AaronHall 当我选择 pivot = a_list[high] 时，但我就是想不出如何让它工作。你能帮忙吗？ - Qiulang

@matino 我也有同样的困惑！分区函数没问题，它所满足的不变量比你期望的要弱 - 它不必找到确切的位置将小于和大于枢轴的左右分开。它仅保证了一个非平凡的分割，并且返回索引左侧的所有元素都比返回索引右侧的元素小。 - Dror Speiser

根据维基百科的相关文章，选择枢轴点时必须避开最后一个元素。所以你不应该选择 pivot = a_list[high]，@AaronHall。 - Mokarrom Hossain

Answer 6

已经有很多答案了，但我认为这种方法是最清晰的实现：

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    pivots = [x for x in arr if x == arr[0]]
    lesser = quicksort([x for x in arr if x < arr[0]])
    greater = quicksort([x for x in arr if x > arr[0]])

    return lesser + pivots + greater

当然，您可以跳过将所有内容存储在变量中，直接像这样返回它们：

def quicksort(arr):
    """ Quicksort a list

    :type arr: list
    :param arr: List to sort
    :returns: list -- Sorted list
    """
    if not arr:
        return []

    return quicksort([x for x in arr if x < arr[0]]) \
        + [x for x in arr if x == arr[0]] \
        + quicksort([x for x in arr if x > arr[0]])

- Sebastian Dahlgren

---

O(N!)是一种较慢的排序算法，也被称为“慢速排序”吗？ - Scott 混合理论

我相信第一个代码示例中应该是“lesser”和“greater”，而不是“[lesser]”和“[greater]”，否则你将得到嵌套的列表，而不是一个平面的列表。 - Alice

@Scott混合理论 我还在学习时间复杂度，您能详细说明一下为什么这个实现是O(N!)吗？假设嵌套列表 [lesser] 和 [greater] 是笔误，那么平均时间复杂度不应该是 O(3N logN) 吗？这样就可以降低到期望的平均 O(N logN) 了。当然，这三个列表推导式确实做了一些不必要的工作。 - Chrispy

@Chrispy 如果你对一个倒序列表进行排序，比如5,4,3,2,1，会怎样呢？ - Scott 混合理论

@Scott混合理论，你说得没错，快速排序的最坏运行时间是Θ(n^2)，但根据《算法导论》所述，平均情况下运行时间为Θ(n lg n)。更重要的是，实践中快速排序通常优于堆排序。 - Lungang Fang

Answer 7

功能性方法：

def qsort(lst):
    if len(lst) < 2:
        return lst

    pivot = lst[0]
    left = list(filter(lambda x: x <= pivot, lst[1:]))
    right = list(filter(lambda x: x > pivot, lst[1:]))
    
    return qsort(left) + [pivot] + qsort(right)

- akarca

---

列表在Python 3中是保留的关键字。请查看您代码的修改版本：https://gist.github.com/kunthar/9d8962e1438e93f50dc6dd94d503af3d - Kunthar

akarca和@Kunthar，这两个解决方案在Python2或Python3中每次运行时都会弹出列表中的一个元素，因此破坏了列表。这是一个修复版本：https://gist.github.com/joshuatvernon/634e0d912401899af0fdc4e23c94192b - joshuatvernon

Answer 8

这是一个使用Hoare分区方案的快速排序版本，交换次数较少且使用了较少的局部变量。

def quicksort(array):
    qsort(array, 0, len(array)-1)

def qsort(A, lo, hi):
    if lo < hi:
        p = partition(A, lo, hi)
        qsort(A, lo, p)
        qsort(A, p + 1, hi)

def partition(A, lo, hi):
    pivot = A[lo]
    i, j = lo-1, hi+1
    while True:
      i += 1
      j -= 1
      while(A[i] < pivot): i+= 1
      while(A[j] > pivot ): j-= 1

      if i >= j: 
          return j

      A[i], A[j] = A[j], A[i]


test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)

- Madu Alikor

Answer 9

从算法入门轻松实现

def quicksort(arr):
    if len(arr) < 2:
        return arr #base case
    else:
        pivot = arr[0]
        less = [i for i in arr[1:] if i <= pivot] 
        more = [i for i in arr[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(more)

- Alice

Answer 10

函数式编程方法

smaller = lambda xs, y: filter(lambda x: x <= y, xs)
larger = lambda xs, y: filter(lambda x: x > y, xs)
qsort = lambda xs: qsort(smaller(xs[1:],xs[0])) + [xs[0]] + qsort(larger(xs[1:],xs[0])) if xs != [] else []

print qsort([3,1,4,2,5]) == [1,2,3,4,5]

- Arnaldo P. Figueira Figueira