算法专题：Quick Sort

快速排序是冒泡排序的一种改良，它是一种不稳定排序，即时间复杂度从O（n）~O（n^2），平均O（nlgn）。不过在很多算法题里面，如果要求的是O（n）时间复杂度，貌似也可以用快排。
快排和核心思想是分而治之，以及大小分到两边。也就是说，进行多趟排序，每一次拿一个值出来，比它小的放左边，比它大的放右边，然后对左右两个区间迭代。
这里主要有几个问题：怎么选那个值？怎么实现根据大小分堆？相等怎么办？
首先看怎么选择的问题，其实没有规定，简单的就选第一个，高级一点的就取范围内一个随机下标。
然后是怎么分堆，一般都通过双指针实现。当然如果不在意空间复杂度，也可以用两个新数组一遍扫描下来装。这里主要讲双指针实现。假设区间范围是0~n-1，left=0,right=n-1,选择的划分下标是p。具体做法：

1. 先把n[p]值和最右端的换一个位置，这样就相当于把p拿出去了。即nums[p], nums[right] = nums[right], nums[p]
2. 两个ij指针初始均指向最左边。i每一次向后一步，遍历整个区间。j只在i发现比n[p]小的元素时，交换元素后j+1
3. 最后再把最右边的n[p]放回来，此时和j指向的元素交换
4. 对j的左右递归

极端情况：假设其余元素都大于p指向的元素，那么j动不了，最后递归nums[1:]，相当于这一次只排序了一个元素；若其余所有元素都小于n[p]，最后j指向最右端，还是只相当于排序了一个元素。最理想的情况就是最后j指向中间，一次排序了一半元素。所以说快排是不稳定的。
关于取等号，这其实也是很纠结的事情，比如对一个全部相等的序列快排，无论是相等放左边也好不放也好，最后一次都只能排1个元素。不过即使这样，对于相等的数排序效率也是O（n）。
代码：

from random import randint
def quickSort2(L, low, high):
    if low >= high:
        return L
    p = randint(low, high)
    key = L[p]
    L[p], L[high] = L[high], L[p]
    j = low
    for i in range(low, high):
        if L[i] < key:
            L[i], L[j] = L[j], L[i]
            j += 1
    L[j], L[high] = L[high], L[j]
    quickSort2(L, low, j - 1)
    quickSort2(L, j + 1, high)
    return L

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSort2(alist, 0, len(alist) - 1)
print(alist)  

变形1：假如要排逆序呢？当然可以先排正序然后逆序，不过其实在这里把L[i]<key改成大于就行了。
变形2：部分排序。假设只需要其中的正序前k个数，如何实现？当然可以全部排序然后取出前k个，不过那样效率就不是最优了。
考虑一次快排，把整个数组分成左边假设n1个元素，右边n2个元素，则n1+n2+1=n。
1.假如n1+1>=k，也就是说需要的区间全部在左边，或者再加上中间这个已经排好的元素，迭代转到左半区的排序；
2.否则，说明左右半区都需要排，其中左边都需要排，右边也需要迭代，只不过右边只需要找出前k-n1-1个元素即可。
代码如下：

def quickSortK(L, low, high, k):
    if low >= high:
        return L
    p = randint(low, high)
    key = L[p]
    L[p], L[high] = L[high], L[p]
    j = low
    for i in (range(low, high)):
        if L[i] < key:
            L[i], L[j] = L[j], L[i]
            j += 1
    L[j], L[high] = L[high], L[j]
    if j - low >= k:
        quickSortK(L, low, j - 1, k)
    elif j - low + 1 == k:
        quickSortK(L, low, j - 1, k - 1)
    else:
        quickSortK(L, low, j - 1, j - low + 1)
        quickSortK(L, j+1, high, k - (j - low + 1))
    return L

alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
quickSortK(alist, 0, len(alist) - 1, 9)
print(alist)

同样，如果是想要找到前k大个元素，变一下比较符号即可。