快速排序是一种常用的Java排序算法，本文会以详细介绍快速排序的基本思想及其代码实现@mikechen
快速排序定义
快速排序，英文名为Quick Sort，是由C.A.R Hoarse 在1960年提出，是一种排序算法。
快速排序是从冒泡排序算法演变而来的，是对冒泡排序的一种改进，比选择排序快的多。
由于快速排序算法元素之间的比较次数较少，速度较快，因而得名快速排序。
在各种内部排序方法中，快速排序被认为是目前最好的一种排序方法。
快速排序原理思想
快速排序的原理：本质是分而治之思想的运用。
快速排序的基本思路，主要分为如下4步：
1）首先：设定一个分界值，通过该分界值将数组分成左右两部分；
2）其次：将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边；
3）然后：左边和右边的数据可以独立排序，对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值，右侧的数组数据也可以做类似处理。
4）最后：重复上述过程。
快速排序图解
上面我们理解了大致的思路，下面通过图解的方式看一个详细的例子，这样会更清楚快速排序的原理。
下面我们来对如下数据进行快速排序：
8，2，5，0，7，4，6，1
第一步：首先，我们随机选择一个基准值。
如下图所示：
第二步：与其他元素依次比较，大的放右边，小的放左边。
如下图所示：
第三步：然后我们以同样的方式排左边的数据，如下图所示:
第四步：继续排 0 和 1，如下图所示 ：
第五步：由于只剩下一个数，所以就不用排了。
现在的数组序列是下图这个样子：
第六步：右边以同样的操作进行，即可排序完成。
看完了上面的图解，我们再综合起来看一个快速排序的全过程。
如下动图所示：
快速排序代码实例
上面我们了解了思路与原理，下面我们具体编程程序来实现。
代码如下：
public class QuickSort {
public static void quickSort(int[] arr,int low,int high) {
int p,i,j,temp;
if(low >= high) {
return;
}
//p就是基准数,这里就是每个数组的第一个
p = arr[low];
i = low;
j = high;
while(i < j) {
//右边当发现小于p的值时停止循环
while(arr[j] >= p && i < j) {
j--;
}
//这里一定是右边开始，上下这两个循环不能调换（下面有解析，可以先想想）
//左边当发现大于p的值时停止循环
while(arr[i] <= p && i < j) {
i++;
}
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
arr[low] = arr[i];//这里的arr[i]一定是停小于p的，经过i、j交换后i处的值一定是小于p的(j先走)
arr[i] = p;
quickSort(arr,low,j-1); //对左边快排
quickSort(arr,j+1,high); //对右边快排
}
public static void main(String[] args) {
int[] arr = new int[] {9,4,6,8,3,10,4,6};
quickSort(arr,0,arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》