Quicksort

Quicksort是一个分而治之的算法，它根据主元把一个大数组分成2个小数组：其中1个数组的元素要比主元小，另一个要比主元大。Quicksort至今依然是一个常用的排序算法，如果算法实现好的情况下，它的速度要比merge sort 和 heapsort快2到3倍。一个有效实现地Quicksort 并不是一个stable sort，即相等元素的相对顺序不能被保证。Quicksort 也可以在一个数组上进行原址排序。数学分析表明，quicksort排序n个元素平均需要O(nlogn)O(nlogn) 比较，在最坏的情况下，它需要O(n2)O(n2)次比较，虽然这样的行为不常见。

Quicksort的步骤

Quicksort主要包含以下3步：

1. 从数组中取出一个元素，叫做主元（pivot）
2. 重排序数组，使得所有小于pivot的元素在它前面，所有大于pivot的元素在它后面，等于pivot的元素放在哪面都行。这样的划分以后，pivot的位置已经排好了。这个过程叫做partition操作
3. 递归地应用步骤2到小于pivot的子数组和大于pivot的子数组
   在上面的步骤中，递归的base case是数组的大小为0或1，因为这样的数组已经有序，不需要再排序。我们有很多方式来选择pivot，不同地方式会对算法的性能有很大地影响。

def partition(a, l, r):
    i = l
    j = r
    while i < j:
        while a[i] < a[l] and i < j:
            i += 1

        while a[j] > a[l] and i < j:
            j -= 1

        if i < j:
            temp = a[i]
            a[i] = a[j]
            a[j] = temp

    temp = a[l]
    a[l] = a[j]
    a[j] = temp
    return j


 def quick_sort(a, l, r):
    if l < r:
        index = partition(a, l, r)
        sort(a, l, index - 1)
        sort(a, index + 1, r)

    return a


 a = [2, 4, 5, 3, 8]
 quick_sort(a, 0, 4)