单路快排

核心思想（partition）

选取一个元素作为基准值，将小于基准值的元素放在基准值左边，将大于或者等于基准值的元素放在基准值右边。经过这样一次操作后数组已经宏观上有序，且基准值已经来到它的最终位置。然后对基准值左边的数组和基准值右边的数组采取同样的方式进行处理，直至数组不能再进行划分,则说明此时数组已经有序。

主体代码：

交换
数组是引用类型，必须通过引用传递将数组本身传过去进而进行交换。

双路快排

核心思想
双路快排其它操作同单路快排，只是在进行数组划分时将小于等于基准值的，放在数组左边，将大于等于基准值的元素放在数组右边，也就是说等于基准值的元素大体上平摊到左右两边，这样就可以避免划分极不均衡的情况。
此时我们设置两个指针i，j，j从尾向前，i从头向尾，进行遍历，当arr[i] 大于等于基准值，arr[j]小于等于基准值时两个索引位置的元素进行交换，否咋i++，j–，直至i>=j.

随机快排

核心思想：在选取基准值的时候，任意选取一个元素，然后将该元素与数组首元素进行交换，然后将交换过来的元素作为基准值。这样第一次选到最大值或者最小值的概率为1 / n，第二次 1 / n -1,第三次 1 / n - 2，以此类推，也就是说每次选取到的基准值都为最大或者最小值的概率为1 / n * n 无限逼近于0.这样就可以避免因为数组有序而导致算法复杂度退化的问题
代码实现：

三路快排

核心思想

将整个数组按照划分值val，分成小于val的区域称为小于区，等于val的区域等于区和大于val的区域大于区三部分，在下一次的递归中就不必再处理等于val的等于区，因为等于区的元素已经到达了最终位置，对于存在大量等于val的数组三路快排大大提升了效率。
代码实现（partition过程）：

测试：

• 时间复杂度：
  最好O（nlogn），最坏O（n*n）。
• 空间复杂度
  递归调用本质在不断压栈，因此快排的空间复杂度与递归的深度有关，最好的情况是 O（logn），最坏O（n）。
• 稳定性：不稳定。