使用 Python 快速排序

Quicksort with Python

提问by user2687481

I am totally new to python and I am trying to implement quicksort in it. Could someone please help me complete my code?

我对 python 完全陌生，我正在尝试在其中实现快速排序。有人可以帮我完成我的代码吗？

I do not know how to concatenate the three arrays and printing them.

我不知道如何连接三个数组并打印它们。

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)

采纳答案by Brionius

def sort(array=[12,4,5,6,7,3,1,15]):
    """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

回答by zangw

There is another concise and beautiful version

还有一个简洁漂亮的版本

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]])

# this comment is just to improve readability due to horizontal scroll!!!

Let me explain the above codes for details

让我解释一下上面的代码的详细信息

1. pick the first element of array arr[0]as pivot

   [arr[0]]

2. qsortthose elements of array which are less than pivot with List Comprehension

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

3. qsortthose elements of array which are larger than pivot with List Comprehension

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

1. 选择数组的第一个元素arr[0]作为枢轴

   [arr[0]]

2. qsort那些小于枢轴的数组元素 List Comprehension

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

3. qsort那些大于枢轴的数组元素 List Comprehension

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

回答by FedeN

I think both answers here works ok for the list provided (which answer the original question), but would breaks if an array containing non unique values is passed. So for completeness, I would just point out the small error in each and explain how to fix them.

我认为这里的两个答案都适用于提供的列表（它回答了原始问题），但是如果传递了包含非唯一值的数组，则会中断。因此，为了完整起见，我只会指出每个错误中的小错误并解释如何修复它们。

For example trying to sort the following array [12,4,5,6,7,3,1,15,1] (Note that 1 appears twice) with Brioniusalgorithm .. at some point will end up with the lessarray empty and the equalarray with a pair of values (1,1) that can not be separated in the next iteration and the len() > 1...hence you'll end up with an infinite loop

例如试图以下数组进行排序[12,4,5,6,7,3,1,15,1]（需要注意的是两次1次出现）与Brionius算法..在某一时刻将结束与所述较少阵列空和带有一对值 (1,1)的相等数组，在下一次迭代中不能分开，并且len() > 1...因此你最终会得到一个无限循环

You can fix it by either returning array if lessis empty or better by notcalling sort in your equal array, as in zangwanswer

您可以通过在less为空时返回数组或通过不在相等数组中调用 sort更好来修复它，如zangwanswer

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)

        # 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 hande the part at the end of the recursion - when you only have one element in your array, just return the array.
        return array

The fancier solution also breaks, but for a different cause, it is missing the returnclause in the recursion line, which will cause at some point to return None and try to append it to a list ....

更高级的解决方案也会中断，但出于不同的原因，它在递归行中缺少return子句，这将导致在某些时候返回 None 并尝试将其附加到列表中......

To fix it just add a return to that line

要修复它，只需向该行添加一个返回

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]])

回答by Birger

def quick_sort(list):
    if len(list) ==0:
        return []

    return  quick_sort(filter( lambda item: item < list[0],list)) + [v for v in list if v==list[0] ]  +  quick_sort( filter( lambda item: item > list[0], list))

回答by Bruce Lucas

Or if you prefer a one-liner that also illustrates the Python equivalent of C/C++ varags, lambda expressions, and if expressions:

或者，如果您更喜欢单行代码，它也说明了 C/C++ varags、lambda 表达式和 if 表达式的 Python 等价物：

qsort = lambda x=None, *xs: [] if x is None else qsort(*[a for a in xs if a<x]) + [x] + qsort(*[a for a in xs if a>=x])

回答by akarca

functional approach:

功能方法：

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

    pivot = list.pop()
    left = filter(lambda x: x <= pivot, list)
    right = filter(lambda x: x > pivot, list)

    return qsort(left) + [pivot] + qsort(right)

回答by Sebastian Dahlgren

There are many answers to this already, but I think this approach is the most clean implementation:

对此已经有很多答案，但我认为这种方法是最干净的实现：

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

You can of course skip storing everything in variables and return them straight away like this:

您当然可以跳过将所有内容存储在变量中并直接返回它们，如下所示：

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]])

回答by Boubakr

def quicksort(items):
    if not len(items) > 1:
        return items
    items, pivot = partition(items)
    return quicksort(items[:pivot]) + [items[pivot]] + quicksort(items[pivot + 1:])


def partition(items):
    i = 1
    pivot = 0
    for j in range(1, len(items)):
        if items[j] <= items[pivot]:
            items[i], items[j] = items[j], items[i]
            i += 1
    items[i - 1], items[pivot] = items[pivot], items[i - 1]
    return items, i - 1

回答by suquant

Quick sort without additional memory (in place)

无需额外内存的快速排序（就地）

Usage:

用法：

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

def partition(array, begin, end):
    pivot = begin
    for i in xrange(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)

回答by dapangmao

def quick_sort(array):
    return quick_sort([x for x in array[1:] if x < array[0]]) + [array[0]] \
        + quick_sort([x for x in array[1:] if x >= array[0]]) if array else []