简述
快速排序 是一种排序执行效率很高的排序算法，它利用 分治法 来对待排序序列进行分治排序，它的思想主要是通过一趟排序将待排记录分隔成独立的两部分，其中的一部分比关键字小，后面一部分比关键字大，然后再对这前后的两部分分别采用这种方式进行排序，通过递归的运算最终达到整个序列有序，下面我们简单进行阐述。
快排思路
我们从一个数组来逐步逐步说明快速排序的方法和思路。
- 假设我们对数组{7, 1, 3, 5, 13, 9, 3, 6, 11}进行快速排序。
- 首先在这个序列中找一个数作为 基准数 ，为了方便可以取第一个数。
- 遍历数组， 将小于基准数的放置于基准数左边，大于基准数的放置于基准数右边 。
- 此时得到类似于这种排序的数组{3, 1, 3, 5, 6, 7, 9, 13, 11}。
- 在初始状态下7是第一个位置，现在需要把7挪到中间的某个位置k，也即k位置是两边数的分界点。
- 那如何做到把小于和大于基准数7的值分别放置于两边呢，我们采用 双指针法 ， 从数组的两端分别进行比对 。
- 先从最右位置往左开始找直到找到一个小于基准数的值，记录下该值的位置（记作 i ）。
- 再从最左位置往右找直到找到一个大于基准数的值，记录下该值的位置（记作 j ）。
- 如果位置i<j，则交换i和j两个位置上的值，然后继续从 (j-1)的位置往前 和 (i+1)的位置往后 重复上面比对基准数然后交换的步骤。
- 如果执行到i==j，表示本次比对已经结束，将最后i的位置的值与基准数做交换，此时基准数就找到了临界点的位置k，位置k两边的数组都比当前位置k上的基准值或都更小或都更大。
- 上一次的基准值7已经把数组分为了两半， 基准值7算是已归位（找到排序后的位置） 。
- 通过相同的排序思想，分别对7两边的数组进行快速排序， 左边对[left, k-1]子数组排序，右边则是[k+1, right ]子数组排序 。
- 利用 递归算法 ，对分治后的子数组进行排序。
快速排序之所以比较快，是因为相比 冒泡排序 ，每次的交换都是跳跃式的，每次设置一个基准值，将小于基准值的都交换到左边，大于基准值的都交换到右边，这样不会像冒泡一样每次都只交换相邻的两个数，因此比较和交换的此数都变少了，速度自然更高。当然，也有可能出现最坏的情况，就是仍可能相邻的两个数进行交换。
快速排序基于分治思想，它的时间平均复杂度很容易计算得到为 O( N log N )。
代码实现
1 /**
2 * 快速排序
3 * @param array
4 */
5 public static void quickSort(int[] array) {
6 int len;
7 if(array == null
8 || (len = array.length) == 0
9 || len == 1) {
10 return ;
11 }
12 sort(array, 0, len - 1);
13 }
14
15 /**
16 * 快排核心算法，递归实现
17 * @param array
18 * @param left
19 * @param right
20 */
21 public static void sort(int[] array, int left, int right) {
22 if(left > right) {
23 return;
24 }
25 // base中存放基准数
26 int base = array[left];
27 int i = left, j = right;
28 while(i != j) {
29 // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
30 while(array[j] >= base && i < j) {
31 j--;
32 }
33
34 // 再从左往右边找，直到找到比base值大的数
35 while(array[i] <= base && i < j) {
36 i++;
37 }
38
39 // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
40 if(i < j) {
41 int tmp = array[i];
42 array[i] = array[j];
43 array[j] = tmp;
44 }
45 }
46
47 // 将基准数放到中间的位置（基准数归位）
48 array[left] = array[i];
49 array[i] = base;
50
51 // 递归，继续向基准的左右两边执行和上面同样的操作
52 // i的索引处为上面已确定好的基准值的位置，无需再处理
53 sort(array, left, i - 1);
54 sort(array, i + 1, right);
55 }
欢迎工作一到五年的 Java 工程师朋友们加入Java程序员开发： 721575865
群内提供免费的Java架构学习资料（里面有高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码，MyBatis，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多个知识点的架构资料）合理利用自己每一分每一秒的时间来学习提升自己，不要再用”没有时间“来掩饰自己思想上的懒惰！趁年轻，使劲拼，给未来的自己一个交代！
