算法 排序 python 实现快速排序

    主要分为两个子算法，PARTITION(A, p, r)以A[r]为基准对数组进行一个划分，比A[r]小的放在左边，比A[r]大的放在右边。QUICKSORT(A, p, r)是快速排序的子程序，调用划分程序对数组进行划分，然后递归地调用QUICKSORT(A, p, r)，以完成快速排序的过程。快速排序的最差时间复杂度为O(n²)，平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候，平均时间复杂度为数组的数值分布较为平均的时候。在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn)，但是快速排序的常数项较小，所以要优于堆排序。

PARTITION(A, p, r)

x ← A[r]
 i ← p - 1
 for j ← p to r - 1
     do if A[j] ≤ x
         then i ← i + 1
         swap(A[i], A[j])
 swap(A[i + 1], A[r])
 return i + 1

QUICKSORT(A, p, r)

 if p < r
     then q ← PARTITION(A, p, r)
     QUICKSORT(A, p, q - 1)
     QUICKSORT(A, q + 1, r)

实现：

#!/usr/bin/python

import sys

def partion(array, p, r):
    x = array[r]
    i = p - 1
    for j in range(p, r):
        if (array[j] < x):
            i+=1
            array[j], array[i] = array[i], array[j]

    i+=1
    array[i], array[r] = array[r], array[i]
    return i

def quick_sort(array, p, r):
    if p < r:
        q = partion(array, p, r)
        quick_sort(array, p, q - 1)
        quick_sort(array, q + 1, r)

if __name__ == "__main__":
    array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
    quick_sort(array, 0, len(array) - 1)
    
    for a in array:
        sys.stdout.write("%d " % a)