欢迎各位小可爱~ 我们一起学习，共同进步吧~
一、 快排的原理：一般分为三步： 1.从待排序区间选择一个数，作为基准值（一般选最左边的数） 2.Partition：遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的放到（可以包含相等的）放到基准值的右边。 3.采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度<=1，则退出比较。 以数组[3，5，2，7，9，4，8]为例，进行快排的过程： 二、比较的过程就是Partition的过程， java实现快速排序Partition部分有三种方法： 1 Hoare法 2.挖坑法 3.前后遍历法 Hoare法的思想：
挖坑法的思想：基本思路和Hoare法一致，只是不再进行交换，而是直接赋值（挖坑+填坑）
前后遍历的思想：从第二个数开始遍历，找出比第一个数字小（或大）的数字，然后和第一个数字交换，思想也比较简单，大家看代码就能看懂。
三、 性能分析： 时间复杂度：最好O(nlog(n)) 最坏O(n^2) 平均复杂度：O(nlog(n)) 空间复杂度：最好:O(nlog(n)) 最坏:O(n) 平均:O(nlog(n)) 稳定性：不稳定
四、 关于快排的优化方法： 一般面试官问的时候就从这几个方面考虑就行了。 1.paitition部分里的挖坑（小细节优化） 2.当比较的数字比较少的时候，快排不是最快的；（当区间内的个数低于某个阈值（16）时，使用插排） 3.优化选择特殊的数的方式-----现在选最左边的数字为比较值 a.随机选 b.选几个数，挑大小值为中间的（三数取中） 4.把相等的值特殊处理
五、快速排序的代码实现部分：（三种方法）都是实现从小到大的排序
public class Hoare { public static void quickSort(long[] array) { quickSortInternal(array, 0, array.length - 1); } // 区间是 [lowIndex, highIndex] private static void quickSortInternal(long[] array,int lowIndex,int highIndex) { // 由于是闭区间，所以，区间内个个数需要加个 1 int size = highIndex - lowIndex + 1; if (size <= 1) { return; } // 选择其中一个数（选最左边的） —— array[lowIndex] // 执行 partition，小的放左，大的放右 // keyIndex 是经过 partition 之后，选出来的数最终所在下标 int keyIndex = partition(array, lowIndex, highIndex); // 分别对左右区间进行相同的处理 —— 递归方法 quickSortInternal(array, lowIndex, keyIndex - 1); quickSortInternal(array, keyIndex + 1, highIndex); } // 区间是 array[lowIndex, highIndex] // 1. 选择 array[lowIndex] 作为特殊的数 // 2. 需要遍历整个区间（不能遗漏任何的数）和 选出来的数比较 // 3. 保证 小于等于的在左边，大于等于的在右边（但没有顺序要求) private static int partition(long[] array, int lowIndex, int highIndex) { // 选择合适的方法 return partitionHover(array, lowIndex, highIndex); } private static void swap(long[] array, int index1, int index2) { long t = array[index1]; array[index1] = array[index2]; array[index2] = t; } private static int partitionHover(long[] array, int lowIndex, int highIndex) { int leftIndex = lowIndex; int rightIndex = highIndex; // 选择的数是最左边的一个 long key = array[lowIndex]; // 选择了最左边，从右边先走 // 停止条件 leftIndex == rightIndex // 循环的继续的条件 leftIndex < rightIndex while (leftIndex < rightIndex) { while (leftIndex < rightIndex && array[rightIndex] >= key) { rightIndex--; } // 说明 [rightIndex] 遇到了小的了 while (leftIndex < rightIndex && array[leftIndex] <= key) { leftIndex++; } // 说明 [leftIndex] 遇到了大的了 swap(array, leftIndex, rightIndex); } swap(array, lowIndex, leftIndex); return leftIndex; } //挖坑 private static int partitionHoare(long[] array,int lowIndex,int highIndex){ int leftIndex=lowIndex; int rightIndex=highIndex; long key=array[lowIndex]; while(leftIndex<rightIndex){ while(leftIndex<rightIndex&&array[highIndex]>=key){ rightIndex--; } //右边的值 array[leftIndex]=array[rightIndex]; while(leftIndex<rightIndex&&array[leftIndex]<key){ leftIndex++; } array[rightIndex]=array[leftIndex]; } array[leftIndex]=key; return leftIndex; } //前后遍历的方法 private static int partition前后(long[] array,int lowIndex,int highIndex){ int separateIndex=lowIndex+1; for(int i=lowIndex+1;i<=highIndex;i++){ if(array[i]<array[lowIndex]){ swap(array,i,separateIndex); separateIndex++; } } swap(array,lowIndex,separateIndex-1); return separateIndex-1; }