快速排序

cheun

快速排序是最常用的一种排序，因为它可以取得比较好的平均性能。快速排序是一种递归算法。采用了分而治之的思想。
它的核心步骤是：
1. 把一个序列分成左右两个部分，要求左边的数都比分界点小或相等，右边的数都比分界点的数大。
2. 对步骤1分出来的左右两个部分同样执行1到2的步骤。

那么如何把一个序列分成两个部分呢？设定两个指针i和j，还要设定一个初始比较值x。可以取序列最后的值为x。i左边的都比x小。j是迭代指针，从序列开头到倒数第二个数开始迭代：
1. 如果j指向的值比x大，j下移一位，i不动
2. 如果j指向的值比x小，把i下移一位，再把i和j指向的值交换。然后j下移一位
3. 最后把最后的值和i+1的值交换。

也就是逐步的将比x小的值加到i的队列中来


引用

# python quick sort
def exchange(i, j):
    x = array
    array=array[j]
    array[j]=x
   
def partition(p,r):
    x=array[r]
    i=p-1
    for j in range(p,r-1,1):
        if array[j]<x:
            i=i+1
            exchange(i, j)
    exchange(r,i+1)
    return i+1

def quickSort(p,r):
    if p<r:
        x=partition(p,r)
        quickSort(p,x-1)
        quickSort(x+1,r)

array=[2,5,3,10,8]
quickSort(0,4)
print array