快速排序（重点）

前言

快排是一种比较重要的排序算法，他的思想有时候会作用到个别算法提上，公司招聘的笔试上有时候也有他的过程推导题，所以搞懂快排势在必行！！！

快速排序

基本思想： 根据基准，将数据分成两个部分，一部分小于基准，另一部分大于基准，然后在通过分治是思想，将每个部分在进行上述操作，最终合并结果
时间复杂度： 最好情况O(nlogn)，最坏情况O(n^2)；
排序稳定性： 不稳定；

现在主流上，快排有两种实现方式，一种是单边循环，一种是双边循环，我个人认为双边循环比较容易理解记忆，而且效率更高一点，所以我还是推荐学习后者即可。

详细介绍（双边）

1. 选择最左元素作为基准点元素
2. j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素 ()，一旦找到二者交换，直至i，j相交
3. 最后基准点与i(此时i与i相等)交换，i即为分区位置

图示：

准备工作： i、j指针分别执行数组首尾，而我们的基准pv选择首
i的任务： 从左往右找比基准大的值
j的任务： 从右往左找比基准小的值
交换： 当 i 和 j 的任务都完成后，就将二者的值进行swap，
停止： 当左右指针相遇的时候，停止并且，pv指针的值和i指针进行交换
结果： 这个时候就做到了以基准为分界线，左右两边被分成了两个部分的目的，记录pv当前所在位置

因为上面只是一轮的比较，为了完全排序，我们还需要对两个部分的数据进行递归

快速排序代码实现：

public class QuickSort {public static void main(String[] args) {int[] arr = new int[]{5, 8, 6, 1, 12, 13, 14};quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int l, int r) {// 大于：说明后面两个部分都已经排好了// 等于：同一个数之间没有排序意义if (l >= r) {return;}int pv = partition(arr, l, r);quickSort(arr, l, pv - 1);quickSort(arr, pv + 1, r);}// 对于将头设置为pv的情况，我们必须先找右再找左，否则会出现错误// 举个例子（反例）：// pv指向头的情况下，我们先往左寻找，那么i和j相遇的地点一定是在j的位置上（i<j，i就会比j多走一步），// 在j的位置的值是比pv的值大的，当将 i 和 pv 进行交换的时候，就会将大的值置换到基准的左边从而导致排序出现问题//// 那么反过来，我们先找的j，由于i<j，那么j就会多走一步，在i的位置上相遇，而i位置上的值又是比pv小的，// 所以二者交换pv两边符合一小一大的排序规则。//// 如果说，你实在是要先走左边，那么你的基准指针pv应该自信数组末尾！！！private static int partition(int[] arr, int l, int r) {int pv = arr[l];int i = l;int j = r;// 当l == r就会退出while (i < j) {// 从右往左找大while (i < j && arr[j] > pv) {j--;}// 从左往右找小// 遇到相等就继续往右走while (i < j && arr[i] <= pv) {i++;}// 当i和j都在一个位置的时候没有交换的意义if(i != j){swap(arr, i, j);}}// 循环出来后交换i和pv的值swap(arr, l, j);return i;}private static void swap(int[] arr, int i, int j) {int temp = arr[j];arr[j] = arr[i];arr[i] = temp;}
}

排序结果：

[1, 5, 6, 8, 12]

部分细节说明，已经写在代码中，请详细阅读

以上是本文全部内容，感谢阅读