用Python实现快速排序

def is_sorted(arr): #check if array is sorted
    for i in range(len(arr) - 2):
        if arr[i] > arr[i + 1]:
            return False
    return True

def qsort_in_place(arr, left, right): #arr - given array, #left - first element index, #right - last element index
    if right - left < 1: #if we have empty or one element array - nothing to do
        return
    else:
        left_point = left #set left pointer that points on element that is candidate to swap with element under right pointer or pivot element
        right_point = right - 1 #set right pointer that is candidate to swap with element under left pointer

        while left_point <= right_point: #while we have not checked all elements in the given array
            swap_left = arr[left_point] >= arr[right] #True if we have to move that element after pivot
            swap_right = arr[right_point] < arr[right] #True if we have to move that element before pivot

            if swap_left and swap_right: #if both True we can swap elements under left and right pointers
                arr[right_point], arr[left_point] = arr[left_point], arr[right_point]
                left_point += 1
                right_point -= 1
            else: #if only one True we don`t have place for to swap it
                if not swap_left: #if we dont need to swap it we move to next element
                    left_point += 1
                if not swap_right: #if we dont need to swap it we move to prev element
                    right_point -= 1

        arr[left_point], arr[right] = arr[right], arr[left_point] #swap left element with pivot

        qsort_in_place(arr, left, left_point - 1) #execute qsort for left part of array (elements less than pivot)
        qsort_in_place(arr, left_point + 1, right) #execute qsort for right part of array (elements most than pivot)

def main():
    import random
    arr = random.sample(range(1, 4000), 10) #generate random array
    print(arr)
    print(is_sorted(arr))
    qsort_in_place(arr, 0, len(arr) - 1)
    print(arr)
    print(is_sorted(arr))

if __name__ == "__main__":
    main()

def qs(lst):
  if len(lst) <= 1:
    return lst

  pivot = lst[len(lst)//2]
  sml = [x for x in lst if x < pivot]
  mid = [x for x in lst if x == pivot]
  big = [x for x in lst if x > pivot]

  return qs(sml) + mid + qs(big)

lst = [1, 9, 8, 4, 5, 3, 5, 7]
qs(lst)
>>> [1, 3, 4, 5, 5, 7, 8, 9]

我将使用numpy库完成快速排序。我认为这是一个非常有用的库。他们已经实现了快排算法，但你也可以实现自定义方法。

import numpy
array = [3,4,8,1,2,13,28,11,99,76] #The array what we want to sort

indexes = numpy.argsort( array , None, 'quicksort', None)
index_list = list(indexes)

temp_array = []

for index in index_list:
    temp_array.append( array[index])

array = temp_array

print array #it will show sorted array

不要使用三个不同的数组来存储小于、等于和大于的元素，而是尝试传统的概念（分区方法）：

http://pythonplanet.blogspot.in/2015/08/quick-sort-using-traditional-partition.html

def partitn(alist, left, right):  
 i=left  
 j=right  
 mid=(left+right)/2   

pivot=alist[mid]  
while i <= j:  
    while alist[i] < pivot:  
        i=i+1   

    while alist[j] > pivot:  
        j=j-1   

    if i <= j:  
        temp = alist[i]  
        alist[i] = alist[j]  
        alist[j] = temp  
        i = i + 1   
        j = j - 1   

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

原地排序

def qsort(a, b=0, e=None):
    # partitioning
    def part(a, start, end):
        p = start
        for i in xrange(start+1, end):
            if a[i] < a[p]:
                a[i], a[p+1] = a[p+1], a[i]
                a[p+1], a[p] = a[p], a[p+1]
                p += 1
        return p

    if e is None:
        e = len(a)
    if e-b <= 1: return

    p = part(a, b, e)
    qsort(a, b, p)
    qsort(a, p+1, e)

不使用递归：

deq = collections.deque()
deq.append((b, e))
while len(deq):
    el = deq.pop()
    if el[1] - el[0] > 1:
        p = part(a, el[0], el[1])
        deq.append((el[0], p))
        deq.append((p+1, el[1]))

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