快速排序

步骤：1. 选择其中一个数，假设它是中间值

            2. 遍历一遍，比它小的放一段，大的放另一端，记录其中一段的数目

            3. 在记录的数目的下一位，将中间值插回去

            4. 于此位置，将要排序的数列分成两段，递归做

从上面的步骤可以看出，分治的过程是快排的核心。

一些优化：

1. 选中间值时，若选在最大或者最小，并恰好数列是有序的，都会是噩梦。故最好使用三点定位法

2. 遍历并分置两端时，为了节省空间开销，常用原地分割法。通过交换应置于位置的数，与当前实际位置的数，在同一个数列内部区分大小端。但是此交换存在过多中间操作，一个数可能要被交换多次。使用替换法可以有效缩短时间。替换法首先让中间值等于其中一端的值，然后从两端交替对中间值进行比较，并互相替换。最后多出一位赋回中间值

3. 用迭代替换递归。不过虽说如此，若中间值选择不当，依然还是会发生层数过多的情况。

代码留档：

class sort:
    def quicksort(self, num, start, end):
        while (start < end):                        #迭代改造后的递归
            p = sort().partition(num, start, end)
            #print num
            sort().quicksort(num, start, p)
            start = p + 1
        return num

    def partition(self, num, start, end):           #替换法下的排序过程
        sort().generatePivot(num, start, end)
        target = num[start]
        while( start < end - 1  ):
            while(start < end -1  and num[end-1] > target) :
                end -= 1
            num[start] = num[end - 1]
            while(start < end - 1  and num[start] < target):
                start += 1
            num[end - 1] = num[start]
        num[start] = target
        return start

    def generatePivot(self, num, start, end):       #三点定位，将中间值放到最左侧
        middle = start + (end -1- start)/2
        if num[start] > num[end-1]:
            num[start],num[end-1] = num[end-1],num[start]
        if num[middle] > num[end-1]:
            num[middle],num[end-1] = num[end-1],num[middle]
        if num[middle] > num[start]:
            num[middle],num[start] = num[start],num[middle]

    def sort(self, num):
        return sort().quicksort(num, 0, len(num))

#test case
print sort().sort([2,1,3,7,5,4,6])
print sort().sort(range(20)[::-1])
print sort().sort(range(20))
print sort().sort(range(200000)[::-1])
print sort().sort(range(200000))