Java深入浅出理解快速排序以及优化方式
作者:飞人01_01 时间:2023-01-17 13:50:44
可能经常看面经的同学都知道,面试所遇到的排序算法,快速排序
占主要位置,热度只增不减啊,其次就是归并和堆排序
。
其实以前写过一篇排序的文章,写的比较简单,只是轻描淡写。今天我再次重新拿起笔,将快速排序
的几大优化,再次一一讲述一遍。各位同学,读完这篇文章,如若对你能够带来一些感悟,记得给个大大的赞哦!!!
前言
快速排序是在冒泡排序的基础之上,再次进行优化得来的。具体的步骤如下:
在待排序的序列中,选取一个数值,将大于它的数放到数组的右边,小于它的数放到数组的左边,等于它的数就放到数组的中间。
此时,相对于上一步挑选出来的数值而言,此时数组的左部分都小于它,右部分都大于它。达到“相对有序”。
然后,递归左部分和右部分,重复以上操作即可。
流程知道后,问题就在于如何选取这个基准值?我们有以下几种选取基准值和优化的方法:
挖坑法
随机取值法
三数取中法
荷兰国旗问题优化
以上四种,笔试最容易考到的代码题就是挖坑法,可能最难理解的就是荷兰国旗问题带来的优化。要想拿到一个好的offer,以上必须全部掌握,并且还得学会写非递归版本的代码(非递归比较简单)。
本期文章源码:GitHub
以下所有讲解,可能会频繁用到如下交换数值的方法,这里提前写了:
public void swap(int[] array, int L, int R) {
int tmp = array[L];
array[L] = array[R];
array[R] = tmp;
}
一、挖坑法
挖坑法:默认将数组的第一个数值作为基准值。然后做以下步骤:
第一、从数组的最后开始遍历(下标R),找到第一个小于基准值的数值。然后将小于的这个数值放入上次空出来的位置(第一次就是基准值的位置)
第二、上一步将小于的数值交换位置后,空出来的位置用于:在数组的前面找到第一个大于基准值的数值(下标L),放到这个空出来的位置。
循环以上两个步骤,直到遍历到L==R时,循环停止
看如下长图:
挖坑法,就类似于,我先拿出基准值,此时基准值的位置就空出来了,需要从后面的数值拿一个数来补这个空位置;补完之后,后面的位置又空出来了,此时再从前面的数组找一个数去补后面的空位置,循环往复,知道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从左开始遍历,每遍历一个数,进行判断,小于基准值,就划分到
less区域
;大于基准值就划分到more区域
;等于的话,不交换,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++;
}
}
//返回等于区的开始和结束下标即可。
}
来源:https://blog.csdn.net/x0919/article/details/120972997