大家好,我是周一。
最近几篇算法,咱们都是聊的归并排序,归并排序也说的差不多了,明天聊聊疾速排序。
一、荷兰国旗问题
1、啥是荷兰国旗问题
荷兰国旗是由红白蓝 3 种颜色的条纹拼接而成,如下图所示:
假如这样的条纹有多条,且各种色彩的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但不仅仅只有这一种状况:
需要是:把这些条纹依照色彩排好,红色的在上半局部,红色的在两头局部,蓝色的在下半局部,咱们把这类问题称作荷兰国旗问题。
2、荷兰国旗问题的形象
咱们 把荷兰国旗问题形象成数组 的模式是上面这样的:
给定一个整数数组和一个值 M(存在于原数组中),要求把数组中小于 M 的元素放到数组的右边,等于 M 的元素放到数组的两头,大于 M 的元素放到数组的左边,最终返回一个整数数组,只有两个值,0 地位是等于 M 的数组局部的左下标值、1 地位是等于 M 的数组局部的右下标值。
进一步 形象为更加通用 的模式是上面这样的:
给定数组 arr,将 [l, r] 范畴内的数(当然默认是 [0 – arr.length – 1]),小于 arr[r](这里间接取数组最左边的值进行比拟)放到数组右边,等于 arr[r]放到数组两头,大于 arr[r]放到数组左边。最初返回等于 arr[r]的左, 右下标值。
3、解决的思路
定义一个小于区,一个大于区;遍历数组,挨个和 arr[r]比拟,
(1)小于 arr[r],与小于区的后一个地位替换,以后地位后移;
(2)等于 arr[r],以后地位间接后移;
(3)大于 arr[r],与大于区的前一个地位替换,以后地位不动(替换到此地位的数还没比拟过,所以不动)。
遍历完后,arr[r]和大于区的最左侧地位替换。
最初返回,此时小于区的后一个地位,大于区的地位,即是最初的等于 arr[r]的左, 右下标值。
4、具体的参考代码
/**
* 荷兰国旗问题
* <p>
* 把数组 arr 中,[l, r]范畴内的数,小于 arr[r]放到数组最右边,等于 arr[r]放到数组两头,大于 arr[r]放到数组最左边
*
* @return 返回等于 arr[r]的左, 右下标值
*/
public static int[] netherlandsFlag(int[] arr, int l, int r) {if (l > r) {return new int[]{-1, -1};
}
if (l == r) {return new int[]{l, r};
}
// 小于 arr[r]的右边界,从 L 的右边一位开始
int less = l - 1;
// 大于 arr[r]的左边界,从 r 开始,即以后右边界里曾经有 arr[r]
int more = r;
// 以后正在比拟的下标
int index = l;
// 不能与 大于 arr[r]的左边界 撞上
while (index < more) {if (arr[index] < arr[r]) {// 小于时,将以后地位的数和小于 arr[r]的右边界的下一个地位替换
// 以后地位后移一位
swap(arr, index++, ++less);
} else if (arr[index] == arr[r]) {
// 等于时,以后地位后移一位即可
index++;
} else {// 大于时,以后地位的数和大于 arr[r]的左边界的前一个地位替换
// 以后地位不动
swap(arr, index, --more);
}
}
// 将 arr[r]地位的数和大于 arr[r]的左边界的数替换
// 此时整个数组就依照 小于、等于、大于 arr[r] 分成了左中右三块
swap(arr, more, r);
// 最初整个数组中,等于 arr[r]的左右边界别离是 less + 1, more
return new int[]{less + 1, more};
}
二、疾速排序
1、啥是快排(排序流程)
首先设定一个分界值,通过该分界值将数组分成左中右三局部。
(1)将小于分界值的数据集中到数组的右边,等于分界值的数据集中到数组的两头,大于分界值的数据集中到数组左边。
(2)而后,右边和左边的数据能够独立排序。对于左侧的数据,又能够取一个分界值,将该局部数据分成左中右三局部,同样在右边放较小值,两头放等于值,左边放较大值。左边数据也做同样的解决。
(3)反复上述过程,能够看出,这是一个递归过程。通过递归将左侧局部排好序后,再递归排好右侧局部的程序。当左、右两个局部各数据排序实现后,整个数组的排序也就实现了。
当看完了快排的流程,是不是发现快排的外围办法就是荷兰国旗问题,所以晓得为啥本文一开始就介绍荷兰国旗问题了吧。
2、形象后的快排流程
(1)随机将数组中的某个数放到比拟地位上(即最右侧地位)
(2)调用荷兰国旗办法,(此时等于区的数即在最初排好序的地位上),拿到等于区的左右下标
(3)小于区和大于区再各自递归调用(1)(2)步即可将小于区和大于区排好序。
3、具体的参考代码
/**
* 随机快排
*/
public static void quickSortRandom(int[] arr) {if (arr == null || arr.length < 2) {return;}
processRandom(arr, 0, arr.length - 1);
}
private static void processRandom(int[] arr, int l, int r) {if (l >= r) {return;}
// 随机将数组中的某个数放到比拟地位上(即数组最左边地位)// 这一步是保障快排工夫复杂度是 O(N*logN)的要害,不然,快排的工夫复杂度是 O(N^2)
swap(arr, l + (int) ((r - l + 1) * Math.random()), r);
// 将数组划分为 小于、等于、大于 arr[r] 的左中右三块
int[] equalArea = netherlandsFlag(arr, l, r);
// 此时等于区域的值曾经处于最初排序后果的地位了
// 递归将左半局部的排好序
processRandom(arr, l, equalArea[0] - 1);
// 递归将右半局部的排好序
processRandom(arr, equalArea[1] + 1, r);
}
public static void swap(int[] arr, int i, int j) {int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}