用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)
            elif x == pivot:
                equal.append(x)
            else: # 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

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

def qsort(user, begin, end):

    if begin >= end:
        return

    # partition
    # pivot = begin
    L = begin+1
    R = begin
    while L < end:
        if user[begin] > user[L]:
            R+=1
            user[R], user[L] = user[L], user[R]
        L+= 1
    user[R], user[begin] = user[begin], user[R]

    qsort(user, 0, R)
    qsort(user, R+1, end)

tests = [
    {'sample':[1],'answer':[1]},
    {'sample':[3,9],'answer':[3,9]},
    {'sample':[1,8,1],'answer':[1,1,8]},
    {'sample':[7,5,5,1],'answer':[1,5,5,7]},
    {'sample':[4,10,5,9,3],'answer':[3,4,5,9,10]},
    {'sample':[6,6,3,8,7,7],'answer':[3,6,6,7,7,8]},
    {'sample':[3,6,7,2,4,5,4],'answer':[2,3,4,4,5,6,7]},
    {'sample':[1,5,6,1,9,0,7,4],'answer':[0,1,1,4,5,6,7,9]},
    {'sample':[0,9,5,2,2,5,8,3,8],'answer':[0,2,2,3,5,5,8,8,9]},
    {'sample':[2,5,3,3,2,0,9,0,0,7],'answer':[0,0,0,2,2,3,3,5,7,9]}
]

for test in tests:

    sample = test['sample'][:]
    answer = test['answer']

    qsort(sample,0,len(sample))

    print(sample == answer)

以下是一种真正的原地实现方式 [参考自Michael T. Goodrich和Roberto Tamassia所著《算法设计与应用》中的第8.9章和第8.11章]:

from random import randint

def partition (A, a, b):
    p = randint(a,b)
    # or mid point
    # p = (a + b) / 2

    piv = A[p]

    # swap the pivot with the end of the array
    A[p] = A[b]
    A[b] = piv

    i = a     # left index (right movement ->)
    j = b - 1 # right index (left movement <-)

    while i <= j:
        # move right if smaller/eq than/to piv
        while A[i] <= piv and i <= j:
            i += 1
        # move left if greater/eq than/to piv
        while A[j] >= piv and j >= i:
            j -= 1

        # indices stopped moving:
        if i < j:
            # swap
            t = A[i]
            A[i] = A[j]
            A[j] = t
    # place pivot back in the right place
    # all values < pivot are to its left and 
    # all values > pivot are to its right
    A[b] = A[i]
    A[i] = piv

    return i

def IpQuickSort (A, a, b):

    while a < b:
        p = partition(A, a, b) # p is pivot's location

        #sort the smaller partition
        if p - a < b - p:
            IpQuickSort(A,a,p-1)
            a = p + 1 # partition less than p is sorted
        else:
            IpQuickSort(A,p+1,b)
            b = p - 1 # partition greater than p is sorted


def main():
    A =  [12,3,5,4,7,3,1,3]
    print A
    IpQuickSort(A,0,len(A)-1)
    print A

if __name__ == "__main__": main()

def quick_sort(self, nums):
    def helper(arr):
        if len(arr) <= 1: return arr
        #lwall is the index of the first element euqal to pivot
        #rwall is the index of the first element greater than pivot
        #so arr[lwall:rwall] is exactly the middle part equal to pivot after one round
        lwall, rwall, pivot = 0, 0, 0
        #choose rightmost as pivot
        pivot = arr[-1]
        for i, e in enumerate(arr):
            if e < pivot:
                #when element is less than pivot, shift the whole middle part to the right by 1
                arr[i], arr[lwall] = arr[lwall], arr[i]
                lwall += 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e == pivot:
                #when element equals to pivot, middle part should increase by 1
                arr[i], arr[rwall] = arr[rwall], arr[i]
                rwall += 1
            elif e > pivot: continue
        return helper(arr[:lwall]) + arr[lwall:rwall] + helper(arr[rwall:])
    return helper(nums)

或者，如果您更喜欢一行代码，该代码还演示了Python中等价于C/C++ varags、lambda表达式和if表达式的内容：

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

def quicksort(array):
 if len(array) < 2:
  return array
 else:
  pivot = array[0]

 less = [i for i in array[1:] if i <= pivot]
 greater = [i for i in array[1:] if i > pivot]
 return quicksort(less) + [pivot] + quicksort(greater)

我知道许多人已经正确回答了这个问题，我很喜欢读他们的回答。我的答案与zangw几乎相同，但我认为之前的贡献者没有很好地解释事物实际上是如何工作的...所以这里是我尝试帮助其他可能在将来访问此问题/答案的人提供一个简单的快速排序实现。

它是如何工作的？

1. 我们基本上从我们的列表中选择第一个项目作为我们的枢轴，然后我们创建两个子列表。
2. 我们的第一个子列表包含小于枢轴的项目
3. 我们的第二个子列表包含大于或等于枢轴的项目
4. 然后我们对它们进行快速排序，然后将它们组合成第一组+枢轴+第二组，以获得最终结果。

以下是一个示例及其相关视觉效果... (枢轴)9,11,2,0

平均：n log n

最坏情况：n ^ 2

代码：

def quicksort(data):
if (len(data) < 2):
    return data
else:
    pivot = data[0]  # pivot
    #starting from element 1 to the end
    rest = data[1:]
    low = [each for each in rest if each < pivot]
    high = [each for each in rest if each >= pivot]
    return quicksort(low) + [pivot] + quicksort(high)

items=[9,11,2,0] print(quicksort(items))

def quicksort(sequence, low, high):
    if low < high:    
        pivot = partition(sequence, low, high)
        quicksort(sequence, low, pivot - 1)
        quicksort(sequence, pivot + 1, high)

def partition(sequence, low, high):
    pivot = sequence[low]
    i = low + 1
    for j in range(low + 1, high + 1):
        if sequence[j] < pivot:
            sequence[j], sequence[i] = sequence[i], sequence[j]
            i += 1
    sequence[i-1], sequence[low] = sequence[low], sequence[i-1]
    return i - 1

def main(sequence):
    quicksort(sequence, 0, len(sequence) - 1)
    return sequence

if __name__ == '__main__':
    sequence = [-2, 0, 32, 1, 56, 99, -4]
    print(main(sequence))

选择枢轴

选择一个“好”的枢轴将会导致两个子序列大小大致相等。确定性地，可以通过一种朴素的方式来选择枢轴元素，也可以通过计算序列的中位数来选择。

选择枢轴的朴素实现是选择第一个或最后一个元素。在这种情况下，最坏情况运行时间为输入序列已经排序或反向排序的情况，因为一个子序列将为空，这将导致每个递归调用仅删除一个元素。

当枢轴是序列的中位数时，可以实现完全平衡的拆分。大于枢轴和小于枢轴的元素数量相同。这种方法保证了更好的总体运行时间，但是耗费的时间更多。

随机选择枢轴的一种非确定性/随机方法是均匀随机选择一个元素。这是一种简单轻量级的方法，可以将最坏情况的情况最小化，并且还可以实现大致平衡的拆分。这也提供了在选择枢轴的朴素方法和中位数方法之间取得平衡的方法。

def quicksort(array):
            if len(array) < 2:
                  return array
            else:
                  pivot= array[0]
                  less = [i for i in array[1:] if i <= pivot]

                  greater = [i for i in array[1:] if i > pivot]

                  return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([10, 5, 2, 3]))

def Partition(A,p,q):
    i=p
    x=A[i]
    for j in range(p+1,q+1):
        if A[j]<=x:
            i=i+1
            tmp=A[j]
            A[j]=A[i]
            A[i]=tmp
    l=A[p]
    A[p]=A[i]
    A[i]=l
    return i

def quickSort(A,p,q):
    if p<q:
        r=Partition(A,p,q)
        quickSort(A,p,r-1)
        quickSort(A,r+1,q)
    return A