猫史档案馆

    话说，快速排序是一种很重要的排序方式（其实是我讲起来不需要图片）。

    很好，我们继续。

    快速排序，是最快的通用内部排序算法。由Hoare于1962年提出。咳！我知道也许会有人说归并排序。但是！相对归并排序来说不仅速度更快，并且不需要辅助空间。按照分治三步法，我对其做如下介绍。

    划分问题：把数组的各个元素重排后分成左右两部分。使得左边所有元素都小于右边所有元素。

    递归求解：把两边分别排序。

    合并问题：其实不用合并，因为此时的数组已经完全有序。

    是不是很简单？（水沝淼㵘）。

    好吧，其实就是这么简单，也许会觉得这样的描述太过笼统，但事实上，快速排序本来就不是只有一种实现方法。“划分过程”有多个不同的版本，导致快速排序也有不同的版本。

    重点来了！你有在听我讲吗？听着的对吧？很好。

    所以快速排序的程序大家可以在互联网上找到。这里我就不在给出代码了。

（提示：快速排序的时间复杂度为：最坏情况O（n【n的平方】），平均情况为O（nlogn）。但实践中几乎不可能达到最低峰。效率非常高。根据快速排序的思想。可以在平均O（n）时间内选出数组中第K大的元素。

 

def QSort(a):
    if len(a) < 2:return a
    mid = a[(len(a)+1)//2]
    return QSort([i for i in a if i < mid]) + [mid] + QSort([i for i in a if i > mid])

sort(n,n+a);