快速排序解释

快速排序 Quick Sort 与归并排序一样，也是典型的分治法的应用。 (如果有对 归并排序还不了解的童鞋，可以看看这里哟~ 归并排序)❤❤❤

快速排序的分治模式

1、选取基准值，获取划分位置。将原数组 a[l, r] 划分为两个子数组 a[l, mid - 1] 和 a[mid + 1, r]。在前一个数组中所有元素都小于等于 a[mid]，后一个数组中所有元素都大于等于 a[mid]。而此时的 a[mid] 的值就是我们所取的基准值，mid 就每次划分的位置；

2、递归调用快速排序函数，分别对两个子数组 a[l, mid - 1] 和 a[mid + 1, r] 排序；

3、快速排序我们是在原数组上进行操作的，所以我们并不需要合并，最后 a[l, r] 已经有序。

快速排序的三种写法

快速排序比较普及的有三种写法，分别是 左右指针法 挖坑法 和 前后指针法。主要是取得划分位置实现的方法有所不同。
接下来会逐个介绍这三种快速排序的写法。

左右指针法

左右指针法步骤

1、首先 我们一般选取最左边的元素作为基准值 key。

2、然后我们需要定义两个变量 i 和 j。
其中 i 为左指针(其实不是指针啦，只是为了方便这么叫它