挖坑法，就类似于，我先拿出基准值，此时基准值的位置就空出来了，需要从后面的数值拿一个数来补这个空位置；补完之后，后面的位置又空出来了，此时再从前面的数组找一个数去补后面的空位置，循环往复，知道L和R相遇。再把基准值放入此时的L位置即可。
此时，整个数组，就从基准值位置分为了两部分，分别递归左部分和右部分即可。
//挖坑法-升序
public int partition(int[] array, int L, int R) {
int tmp = array[L]; //保存基准值
while (L < R) {
//先从右边找一个数
while (L < R && array[R] >= tmp) {
R–; //找小于基准值的数
}
array[L] = array[R];
//再从左边找一个数
while (L < R && array[L] <= tmp) {
L++; //找大于基准值的数
}
array[R] = array[L];
}
array[L] = tmp; //将基准值放入中间位置
return L; //返回此时基准值的下标，用于将数组分为两部分
}
特别值得注意的是，在数组左右两边查找一个数的时候，while循环的判断（L<R && array[R] <= tmp）; 此时的等于号，切记不能少了，因为当待排序数组中有相同的数据时，会导致死循环。
主方法调用如下：
public void quick(int[] array, int L, int R) {
if (L >= R) {
return;
}
int p = partition(array, L, R); //返回基准值的下标
quick(array, L, p - 1); //递归左半部分
quick(array, p + 1, R); //递归右半部分
}
二、随机取值法
================================================================
随机取值法：就是在数组范围内，随机抽取一个数值，作为基准值，这里与挖坑法不同的是：挖坑法每次固定以数组的第一个数为基准值，而随机取值法，则是随机的。此时这种优化搭配着挖坑法，有更快的效率。主方法代码如下：
public void quick2(int[] array, int L, int R) {
if (L >= R) {
return;
}
int index = L + (int)((R - L) * Math.random()); //生成L~R之间的随机值
//为了好理解，我将这个随机值放到数组开头。也可以不交换，只需改partition即可
swap(array, L, index);
int p = partition(array, L, R); //调用挖坑法
quick2(array, L, p - 1); //递归左半部分
quick2(array, p + 1, R); //递归右半部分
}
三、三数取中法
================================================================
三数取中法：原意是，随机生成数组范围内的三个数，然后取三者的中间值作为基准值。但是在后序变化中，就没有随机生成，而是直接以数组的第一个数、最后一个数和中间数，这三个位置的数，取中间值，作为基准值。也是搭配着挖坑法来使用的，与随机取值法一样，都是起到优化的作用。
public void quick3(int[] array, int L, int R) {
if (L >= R) {
return;
}
threeNumberMid(array, L, R); //三数取中，并将中间值，放到数组最前面
int p = partition(array, L, R);
quick3(array, L, p - 1);
quick3(array, p + 1, R);
}
private void threeNumberMid(int[] array, int L, int R) {
int mid = L + ((R - L) >> 1); //中间值
if (array[L] > array[R]) {
swap(array, L, R);
}
if (array[L] > array[mid]) {
swap(array, L, mid);
}
if (array[mid] > array[R]) {
swap(array, mid, R);
}
//以上三个if过后，这三个数就是一个升序
//然后将中间值，放到数组的最前面
swap(array, L, mid);
}
四、荷兰国旗问题优化
===================================================================
荷兰国旗问题所带来的优化，有明显是优于挖坑法的。在以后的使用中，可能这种优化可能会多一点。
至于为什么叫荷兰国旗问题所带来的优化。大家去百度查一下这关键字即可，我们这里就不多说了。
原意是：给定一个数组，将这个数组，以某一个基准值，整体分为三个区域（大于区，小于区、等于区）。然后再去递归小于区和大于区的范围。这就是荷兰国旗问题所带来的优化思想，不同于挖坑法的是，这种优化，会将所有等于基准值的数，都聚集在中间，这样的话，分别去递归左右两边的子数组时，范围上就有一定的缩小。
具体步骤：
- 有三个变量（less，more，index）。分别表示小于区的右边界、大于区的左边界，index则表示遍历当前数组的下标值。less左边都是小于基准值的，more右边都是大于基准值的。如下图：暂时先不看more范围内的50，等会说明。
-
index从左开始遍历，每遍历一个数，进行判断，小于基准值，就划分到；大于基准值就划分到；等于的话，不交换，就行。
-
循环上一走即可，直到index和more相遇就停止。
//伪代码
public int[] partition(int[] array, int L, int R) {
int less = L - 1;
int more = R;
int index = L;
while (index < more) { //index和more相遇就停止
if (array[index] > 基准值) {
} else if (array[index] < 基准值) {
} else { //等于基准值时，index后移即可
index++;
}
}
//返回等于区的开始和结束下标即可。
}
以上就是荷兰国旗问题的伪代码，是不是感觉很简单？？？返回的是一个数组，这个数组只有两个元素，第一个元素就是等于区的开始下标，第二个元素就是等于区的结束下标。
具体的思想我们讲了，但是还是会遇到一个问题，那就是基准值的选择。我们只需套用前面讲过的或者即可。
我们前面将随机取值法的时候，是将随机抽取的基准值，放到数组的第一个元素的位置，然后再去调用partition方法，进行挖坑法的。这里我们就换一下，将随机抽取的基准值，放到数组的末尾。这也就是在上一张图中，为什么more范围内的50是红色的原因。因为它就是基准值，只是暂时先放到了数组的最后而已。（当然，也可以像挖坑法一样，放到数组的第一个元素位置，一样的道理，只是partition方法稍微修改一下初始值即可）。
既然我们将基准值放到了数组的末尾，那么在while循环结束后，也就是index遍历完之后，也需要将最后这个基准值放回到等于区的范围。而此时数组状态是这样的：L……less是小于区，less+1 …… more - 1是等于区，more …… R是大于区。
我们将最后这个基准值放到等于区的末尾即可，也就是调用swap(array, more, R)。R是基准值的位置，more是大于区的开始位置。
所以完整的partition代码如下：
//R位置就是基准值
public int[] partition(int[] array, int L, int R) {
if (L > R) {
return new int[] {-1, -1};
}
if (L == R) {
return new int[] {L, L};
}
int less = L - 1; //数组最前面开始为less
int more = R; //数组末尾，包括了最后的基准值
int index = L; //遍历数组
while (index < more) {
if(array[index] > array[R]) { //大于区
swap(array, index, --more);
} else if (array[index] < array[R]) { //小于区
swap(array, index++, ++less);
} else { //等于区
index++;
}
}
swap(array, more, R); //将最后的基准值放回等于区
//此时的范围：L …… less 是小于区。less+1 ……more 是等于区。more + 1 …… R是大于区
return new int[] {less+1, more};
}
特别值得注意的是，循环里第一个if语句，大于基准值的时候，从与数组后面的元素交换。但是从数组后面交换过来的数据，并不知道大小情况，所以此时的index还不能移动，需再次判断交换过来的数据才行。其他的注意地方就是less和more的变化，留意一下是 。
主方法的调用：
自我介绍一下，小编13年上海交大毕业，曾经在小公司待过，也去过华为、OPPO等大厂，18年进入阿里一直到现在。
深知大多数Java工程师，想要提升技能，往往是自己摸索成长或者是报班学习，但对于培训机构动则几千的学费，着实压力不小。自己不成体系的自学效果低效又漫长，而且极易碰到天花板技术停滞不前！
既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，基本涵盖了95%以上Java开发知识点，真正体系化！
由于文件比较大，这里只是将部分目录截图出来，每个节点里面都包含大厂面经、学习笔记、源码讲义、实战项目、讲解视频，并且会持续更新！
《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》，点击传送门即可获取！
mages/e5c14a7895254671a72faed303032d36.jpg" alt=“img” style=“zoom: 33%;” />
包含：JVM，JAVA集合，网络，JAVA多线程并发，JAVA基础，Spring原理，微服务，Zookeeper，Kafka，RabbitMQ，Hbase，MongoDB，Cassandra，设计模式，负载均衡，数据库，一致性哈希，JAVA算法，数据结构，加密算法，分布式缓存等等
[外链图片转存中…(img-K6CD310z-1712485946592)]