使用 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 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 发布，翻译遵循 CC BY-SA 4.0 许可协议