快速排序是一种排序执行效率很高的排序算法，它利用分治法来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序。

快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort），通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

实现思路

伪代码

执行结果

• 优化一：对于数据量较小的数组, 使用插入排序的性能反而更快, 所以可以在partition到底层数据量较小的时候, 使用插入排序替换快速排序

• 优化二：因为数组可能是近乎有序的数组, 所以我们可以不每次取队首的元素, 可以采取每次随机取一个元素

• 优化三(三路快排)：对于存在大量重复元素的数组, 我们可以不仅仅将数组分割成两部分, 而是可以将数组分割成小于V, 等于V, 大于V的三部分, 然后对小于V和大于V的两部分在进行递归排序

伪代码

执行结果