快速排序是从冒泡排序演变而来的算法，但是比冒泡排序要高效得多，所以叫做快速排序

快速排序采用了分治法

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序是在每一轮只把一个元素冒泡的数列的一端，而快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分

这种思路就叫做分治法。

每次把数列分成两部分，究竟有什么好处呢？

假如给定8个元素的数列，一般情况下冒泡排序需要比较8轮，每轮把一个元素移动到数列一端，时间复杂度是O（n^2）。

而快速排序的流程是什么样子呢？

如图所示，在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。

这样一共需要多少轮呢？平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是 O（nlogn）。

基准元素的选择

基准元素，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。

那么基准元素如何选择呢？

最简单的方式是选择数列的第一个元素：

这种选择在绝大多数情况是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？


我们该怎么避免这种情况发生呢？

其实很简单，我们可以不选择数列的第一个元素，而是随机选择一个元素作为基准元素。

这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。

当然，即使是随机选择基准元素，每一次也有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果。

所以，快速排序的平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）。

元素的移动

选定了基准元素以后，我们要做的就是把其他元素当中小于基准元素的都移动到基准元素一边，大于基准元素的都移动到基准元素另一边。

具体如何实现呢？有两种方法：

• 挖坑法
• 指针交换法

挖坑法

https://www.jianshu.com/p/a68f72278f8f
https://www.sohu.com/a/246785807_684445