本文章只是自我总结，巩固基础之用，如有错误，望大佬不吝赐教。
1.1 快速排序简介
快速排序的实现原理：
1.先选取一个基准值pivotkey;
2.在头尾分别定义两个指针：left，right；
3.两个指针指向的值分别与基准值进行对比，当left指针的数组大于基准值，right指针的数值小于基准值时，两个元素进行交换。
这样就实现了，在基准值左边的都是小于基准值的值，在基准值右边的都大于基准值的值。如下动画，以[6，3，8，2，4，7]数组为例，以6为基准值，介绍了一轮比较的过程：
快速排序
1.2 快速排序&树结构
如果把快速排序与树结构进行联系，是更加方便对它的理解的。还是以上面的这个数组为例。
每一轮比较的过程，我们深入的来理解一下。对于找出基准值这个操作，就相当于在树结构中树立一个根节点。一轮比较就是把其他节点往根节点左右两边来摆放，只是这时左右两颗子树并没有排序好，需要通过下一轮来进行排序。
如下图，第一轮比较后，比节点6小的值到了其的左边，比节点6大的值到了其的右边。接下来第二轮比较后，数组[3，2，4]也已经排序完毕。
image.png
1.3 时间复杂度
所以在这里，我们很容易的得出了该种算法的时间复杂度为(nlogn)级别，n为所有每一轮比较过程比较的次数，logn为比较的轮数，即为树的深度。
但是树的深度和选取的基准值有很大关系，基准值没有选好，会导致树退化成链表，增加了比较的轮数，最差深度会变成n，所以此时时间复杂度为(n*n)级别。
image.png
用小小表格总结一下：
| 平均 | 最坏 | 最好 | 稳定性 |
|---|---|---|---|
| O(nlogn) | O(n^2) | O(nlogn) | 不稳定 |
快速排序java代码如下：
public static void quickSort2(int[] a, int low, int high) {
int pivot;
if (low < high) {
// 找出基准位置的同时，进行元素的交换
pivot = partition(a, low, high);
quickSort2(a, low, pivot - 1);
quickSort2(a, pivot + 1, high);
}
}
public static int partition(int[] a, int low, int high) {
// 因为此处已经记录住了基准，所以low位置的数值可以被覆盖掉。
int pivotKey = a[low];
while (low < high) {
while (high > low && a[high] >= pivotKey) {
high--;
}
//直接覆盖low位置的值，low位置的值已经被pivotKey记录住
a[low] = a[high];
while (high > low && a[low] <= pivotKey) {
low++;
}
//此时的a[high]的值被上面最初low位置的值记录着
a[high] = a[low];
}
//low就是基准值所在的位置
a[low] = pivotKey;
return low;
}
