1. 快排的思想
通过一趟排序将要排序的数据分割成独立的两部分，前一部分的所有数据都要小于后一部分的所有数据，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据的有序性。
2. 快排实现的核心步骤
①找基准点：一般是数组的第一个元素来充当；
②right：从数组的最后一个元素开始，从右往左，直到找到小于基准点的元素；每次都要right比left先走；
③left：从数组的第一个元素开始，从左往右，直到找到大于基准点的元素；
④交换 left 和 right 所在位置的两个元素；
⑥right 继续往左走，找到小于基准点的元素；left 继续往右走，找到大于基准点的元素；然后 left 和 right 再做交换；循环往复，直到两人相遇；
⑦将相遇点所在位置的元素和基准点所在位置的元素做交换，基准点到了中间位置（此时基准点左边的元素全都小于基准点右边的元素）；
⑧【递归】将基准点左边的所有元素当成一个数组，重复①~⑦步骤；基准点右边的所有元素也是如此；
3. 快排的java代码实现
public class A01QuickSort {
public static void main(String[] args) {
A01QuickSort quickSort = new A01QuickSort();
// 测试快排的效率：
// int number = 1000000;
// int[] array = new int[number];
// for (int i = 0; i < array.length; i++) {
// array[i] = new Random().nextInt(number);
// }
//配合后面的元素输出，测试快排是否排序准确：
int[] array = new int[] {181,181,187,181};
System.out.println("数组准备完毕~");
long start = System.currentTimeMillis();
quickSort.quickSort(array, 0, array.length - 1);
long end = System.currentTimeMillis();
System.out.println("quickSort 用时：" + (end - start));// 测试结果： 元素为5万个时：11毫秒。50万：66毫秒。100万：136毫秒
//遍历输出数组元素：
quickSort.traverseArray(array);
}
/**
* 快排的实现
* @param target
* @param left
* @param right
*/
public void quickSort(int[] target, int left, int right) {
if (left >= right) {
return;
}
int pivot = target[left];// 基准点
int temp;
int i = left;
int j = right;//为什么要声明i和j，因为后面做迭代的时候还需要用到最初的left和right
while (i < j) {//验证array数组至少有2个元素，才要做排序
/**
* 提问：
* 为什么是 while里的判断，为什么是 “target[j] >= pivot”，而不是“target[j] > pivot”？？？
* 答: 数组[181,181,187,181]，分别用上面两种while去测试：
* 如果是">="时，因为 181 >= 181 成立，所以right就会从右往左移；
* 如果是">"时，因为 181 > 181 成立，所以right就不会左移。
* 重点！！！right或left，必须有一方得是移动的！！！否则程序就会进入死循环！！！
*/
// 如果right一直都大于或等于pivot，则继续走，直到找到比pivot小的：
while (target[j] >= pivot && i < j) {
j--;
}
// 如果left一直都小于等于pivot，则继续走，直到找到比pivot大的：
while (target[i] <= pivot && i < j) {
i++;
}
// 此时right < pivot, left > pivot，将i和j做交换：
if (i < j) {//这里做判断是为了right到了left位置时，不用再将执行下面这三行代码了：
temp = target[i];
target[i] = target[j];
target[j] = temp;
}
}
// left和right相遇了：
// ①将相遇点的元素和pivot做交换：
target[left] = target[j];
target[j] = pivot;
// ②基准点两边的元素的分别再做排序：
quickSort(target, left, j - 1);
quickSort(target, j + 1, right);
}
//遍历数组
public void traverseArray(int[] array) {
for(int element : array) {
System.out.println(element);
}
}
}4. 快排的时间复杂度：O（n * log（n))
快排的时间复杂度分析：快排的时间复杂度分析（含图解）