前言
上文写到了快速排序的前置知识：荷兰旗问题，这里开始正式学习快速排序。
😊初始快速排序👇
假设我有这样一个数组，以数组的末尾值X作为划分的值，小于X的放在数组的左边，大于X的放在数组的右边。这样的话X处于中间位置对于整个数组来说X有序了，X就不用动了，然后继续这样操作左组和右组，每次操作，都会有固定的值处于中间位置排好序，这样只要完成这个递归就可以完成对数组的排序了。
image.png
这样的话基于荷兰旗问题，每次排序之后，我只要得到等于X的左右下标，就可以基于这个下标，继续递归操作左右数组。
image.png
🤔代码思路👇
我需要一个荷兰旗操作的方法，返回等于X的下标数组dx
-
我需要一个递归方法
- 左组以L到dx[0]-1
- 右组以dx[1]+1到R
- 注意递归结束条件，L>=R
❤️代码实现👇
/**
* 快速排序入口
* @param arr
*/
public static void kspxrk(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
kspx(arr, 0, arr.length - 1);
}
/**
* 递归实现
* @param arr
* @param L
* @param R
*/
public static void kspx(int[]arr,int L,int R) {
//考虑递归结束条件
if(L>=R) {
return;
}
int[] dx = hlqcz(arr, L, R);
kspx(arr, L, dx[0]-1);
kspx(arr, dx[1]+1, R);
}
/**
* 荷兰旗问题操作
* @param arr
* @param L
* @param R
* @return
*/
public static int[] hlqcz(int[] arr , int L ,int R ) {
// L大于R 的时候，越界了
if(L>R) {
return new int[] {-1,-1};
}
//L == R 的时候，左边结束，右边也结束了
if(L==R) {
return new int[] {L,R};
}
//左边界
int less = L - 1;
//右边界
int more = R;
//当前下标,从左开始
int index = L;
//当前下标，碰触右边界结束
while (index<more) {
if(arr[index]==arr[R]) {
//如果当前值 和 最右位置值相等，最右位置值作为划分值，当前下标+1，数据不动
index++;
}else if(arr[index]<arr[R]) {
//如果当前值 小于 划分值，当前值和左边界+1的值交换，然后左边界+1，当前下标+1
swap(arr, index++, ++less);
}else {
//如果当前值 大于 划分值，当前值和右边界-1的值交换，然后有边界-1，当前下标不动
swap(arr, index, --more);
}
}
//当前下标碰到右边界了
//当前位置的值和R位置的值进行交换，R位置的值是划分值，也就是说它一定在中间
swap(arr, more, R);
//返回中间的值的下标
return new int[] {less+1,more};
}
/**
* 数组的l位置的数 和 R位置的数，交换
* @param arr
* @param l
* @param r
*/
public static void swap (int[] arr,int l ,int r) {
int t = arr[l];
arr[l] = arr[r];
arr[r] = t;
}
🤔快速排序进阶--随机快排👇
上面我们用到的数组，用最右侧的数作为划分值，那么就有极端值，最右侧值最大或最小，以及刚好是中间，复杂度分别是O(N^2) 和O（N*logN）,那么为了减少复杂度，就有了随机快排，也就是我随机选一个值，放在最右侧作为划分值。
❤️代码实现👇
/**
* 随机快排
* @param arr
* @param L
* @param R
*/
public static void kspxrk2(int[] arr, int L, int R) {
if (L >= R) {
return;
}
//L-R区间随机一个位置的数和R位置的数交换
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = hlqcz(arr, L, R);
kspx(arr, L, equalArea[0] - 1);
kspx(arr, equalArea[1] + 1, R);
}
