《算法导论》第7章 快速排序

        快速排序是一种非常快，但是不太稳定的排序，期望时间复杂度是nlgn，而且nlgn前面隐含的常数因子很小，然而在最坏的情况下，时间复杂度会到n^2（例如整体呈现逆序排列）。但是快速排序仍然是当前使用非常广泛的。

        快速排序的基本理解：分治思想（参见算法导论第4章），特点是原址性。

        思想：选中数列中某一个数字，把比它大的放在它的一侧，比它小的放在另一侧。这样会把数列分成两份，之后再对剩下的两份重复上述过程，直到数列的长度只有该元素本身即可。

        因为快速排序实在是非常常见，即使是在初高中生的信息学竞赛中也是必须掌握的内容，所以就不过多地介绍了，直接上源码：

def quick_sort(a, start, end):
    """
    快速排序的算法，递归
    :param a: 输入的数组
    :param start: 排序开始位置的索引
    :param end: 排序结束位置的索引
    :return: no return，但是return是递归过程回归所必要的
    """
    print(a, start, end)
    if start >= end:
        return
    tmp, i, j = a[start], start, end
    while i < j:
        print(a)
        while a[j] >= tmp and i < j:
            j -= 1
        else:
            a[i] = a[j]
        while a[i] < tmp and i < j:
            i += 1
        else:
            a[j] = a[i]
    a[i] = tmp
    quick_sort(a, start, i - 1)
    quick_sort(a, i + 1, end)


if __name__ == '__main__':
    # a = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
    a = [16, 14, 10, 9, 8, 7, 4, 3, 2, 1]
    quick_sort(a, 0, len(a) - 1)

        另：随机化的快速排序。一般认为我们需要排序的数组，在任何时候都是无序且各种序列的出现概率相等，但是事实上并不是这样（比如总有人喜欢看看快排到底有多慢，非要给一个反过来的数列让你排）。在这样的情况下，如果我们再采用选取第一个元素为分界值的方法，就会达到快速排序的最坏情况。

        可能读者会说：那我选最后一个。事实上这也不能解决问题，如果测试者预先知道你的flag的选择方式，无论你是选择第一个、最后一个，还是二等分点甚至三等分点黄金分割点各种奇怪的选择方式，都可以找到一个相对较差的数列让排序过程实现接近最坏情况。因此，采用的方法是直接将这个过程随机化，让选取分界flag的方式是随机产生，这样就可以从统计学上使得排序所需要的时间走向统计平均值。

        当然，随机的快速排序仍然会有可能走到最坏的n平方情况，但是从可以从数学原理上杜绝人为因素和排序数列的伪随机等对于算法所需时间造成的影响。