- 基本设计思想
- 代码演示：
- 优化
- 双路快排
- 代码修改：
- 三路快排
- 代码演示
- 三种快排的总结
在《算法》第四版这本书当中有提到：
快速排序可能是现在应用最为广泛的排序算法 基本设计思想
快速排序先选择出一个元素作为标准来作为划分的依据：
一般来说这个元素时随机的选择出这个区间里的某一个元素。
快速排序与归并排序都采用的是分而治之的算法思想来完成排序的。
只不过归并排序我们是不管怎么样，都是将数组一分为二，然后不停地合并两个有序的数据。
而快速排序是在划分数组这件事上下足了文章，但是它没有合并的过程。快速排序这种特殊的分而治之的思想也可以称为减而治之的算法思想。就是将问题的规模进行减少。所以减而治之是分而治之的特列
上面我们了解到了快速排序的大致思想，那么具体的我们应该如何去划分（partition）。
在这里我们要注意到遇到后面的元素初一第一区间时，并不是将第二区间的元素，全部往后移动一位，而是将第二区间的第一个元素和当前要判断的元素做个调换就可以实现了。
可以将这种做法记为：大于切分元素的数字放过去，小于切分元素的数字与黄色部分的第一个元素进行交换
接下来我们通过模拟代码来更加说明理解这个思想。
以力扣上的912题为例：
将一个数组进行排序
/**
* 采用快速排序的思想完成
*/
import java.util.Arrays;
public class Demo912_3 {
public static void main(String[] args) {
int[] nums = {-1, 2, -8, -10}; //给定一个数组
int[] after = sortArray(nums); //的带排序后的数组
System.out.println(Arrays.toString(after)); //打印输出得到数组
}
private static int[] sortArray(int[] nums) {
int len = nums.length; //获得数组长度
quickSort(nums, 0, len - 1); //传递数组、left和right下面的索引位置
return nums; //返回数组
}
/**
* 划分短数组的 *** 作
*
* @param nums 原始数组
* @param left 0
* @param right nums.length - 1
*/
private static void quickSort(int[] nums, int left, int right) {
if (left >= right) { //当左边的索引位置大于等于右边的索引位置，就结束循环
return;
}
int pivotIndex = partition(nums, left, right);
//采用递归获得长的数组中切分元素的索引下标，为下次划分出两个数组做边界
quickSort(nums, left, pivotIndex - 1);//上面长的数组左边的区间，进行排序
quickSort(nums, pivotIndex + 1, right);//上面长的数组右边的区间，进行排序
}
/**
* 对nums[i...j]之间进行快速排序，并且返回切分元素的下标索引
*
* @param nums 原始数组
* @param left *** 作的短数组左边的下标索引
* @param right *** 作的短数组右边的下标索引
* @return
*/
private static int partition(int[] nums, int left, int right) {
int pivot = nums[left]; //选择切分元素，选择的这个切分的元素我们就将它设置为第一个元素
//这里的理解，可以看上面我画的第三幅图，下标位置索引都一样的
int j = left;
for (int i = left + 1; i <= right; i++) {
if (nums[i] <= pivot) {//只对小与切分元素的数字进行 *** 作
j++; //将小区间的索引后移一位，增大一个小区间数组的长度
swap(nums, i, j);//查到小的，将其与j索引位置进行交换
}
}
//排好序，再对切分元素交换到第一区间和第二区间之间来。
swap(nums, left, j);
return j;//最后返回切分元素的下标索引
}
/**
* 交换i和j之间的额元素
*
* @param nums 原始叔叔
* @param index1 交换的元素1
* @param index2 交换的元素2
*/
private static void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
快速排序在我们理想的情况下是这样的：
它当中的元素时越随机越好。所以我们得到的结论是：划分这件事情上在顺序数组和逆序数组上表现是哼差的。这点和插入排序恰好是相反的，插入排序如果数组越有序，它的排序效果越好。
拆分的子问题的规模每次都只别原来的减少1个元素，且每一次划分都只能确定一个元素的位置。所以在顺序和逆序数组上就会导致递归树的高度增加。这个时候快速排序的时间复杂度就会退化成选择排序的时间复杂度了O(N^2)。
现在就要解决这个问题：
其实很简答，随机选择pivot的元素，打破顺序性就可以了。
在获得随机数这件事上，我们是需要声明一个随机数，在Java当中有Random这个类的实例就提供了随机化的方法，并且这个随机我们要传入一个种子，这个种子因为我们想要它每次运行的结果不一样，所以我们传入的是当前的与1970年那个时间的一个毫秒数。（这里不理解问题不大，就知道这样 *** 作，就可以获得0 到指定元素之间的一个数）
加上实例化的代码：
然后将这两次的代码提交给LeetCode912题：可以得到书剑确实快快提示了
很明显的力扣提供给我们测试的数组大多都是有序的或者接近有序的。
其实随机选择切分元素还会遇到一些问题
当一个数组当中，有很多值相等的元素，我们首先选择的是第一个元素，2作为切分的元素，我们可以看到2后面还有4个元素的值是和2相等的。如果我们随机的选择到一个元素和2进行交换，很有可能交换回来的元素还是2，这样的交换就成为了无意义的。如果我们在交换之前做一个判断，如果要叫交换的元素恰好不等于要交换的元素，我们才交换。这个想法虽然好，但是还是有一些问题的，如果我们遇到一个更极端的例子，数组当中全部都是2。这个时候的随机选择pivot的优化显然没有啥意义。
事实上快速排序为什么快，是因为它适应了各种各样的数据的特点，在应对待排序区间里有很多元素的值相等的时候，我们会出现两种处理方式：
-
把与pivot 相等的元素平均的分到数组两侧，这就是：双路快排
-
把与pivot相等的元素挤到中间来。这就是：三路快排
主要思想：我们将切分元素后面的区间划分为l两个部分，这两个部分是分散在切分元素后面这个区间的头和尾。并且这两个部分的元素都是有可能等于切分元素的。
具体做法：
我们在后面的区间，在这个头和尾的部分分别去看元素，我们先在第一个区间里的下一个位置看元素的值。
如果当前看到的元素时小于pivot的，那么它就应该放在第一个区间，这个时候我们什么都不用去做；
直到遇到一个数的大小是大于等于pivot时，就暂时停下来。
然后去看后面区间的前一个位置的元素，如果大于pivot 它就本身属于第二个区间 ，什么都不用去做；
直到遇到小于等于pivot时，暂停下来，交换一二区间刚刚暂停的元素。
接着先开始移动第二区间的前面的索引向前移动。
采取一头一尾的交替方式进行遍历。
左边：遇到严格小于 pivot 的元素纳入左边的区间，否则停下
右边：遇到严格大于 pivot 的元素纳入右边的区间，否则停下
交换，左边区间和右边区间都各增加一个元素
通过这样的方式，我们使得等于pivot的元素，通过交换来平均的来到了数组的两侧。
下来通过一个形式化的例子来进行演示：
主要代码：
全部代码：
import java.util.Arrays;
import java.util.Random;
public class Demo912_4 {
public static void main(String[] args) {
int[] nums = {-1, 2, -8, -10}; //给定一个数组
int[] after = sortArray(nums); //的带排序后的数组
System.out.println(Arrays.toString(after)); //打印输出得到数组
}
private static int[] sortArray(int[] nums) {
int len = nums.length; //获得数组长度
quickSort(nums, 0, len - 1); //传递数组、left和right下面的索引位置
return nums; //返回数组
}
/**
* 划分短数组的 *** 作
*
* @param nums 原始数组
* @param left 0
* @param right nums.length - 1
*/
private static void quickSort(int[] nums, int left, int right) {
if (left >= right) { //当左边的索引位置大于等于右边的索引位置，就结束循环
return;
}
int pivotIndex = partition(nums, left, right);
//采用递归获得长的数组中切分元素的索引下标，为下次划分出两个数组做边界
quickSort(nums, left, pivotIndex - 1);//上面长的数组左边的区间，进行排序
quickSort(nums, pivotIndex + 1, right);//上面长的数组右边的区间，进行排序
}
/**
* 对nums[i...j]之间进行快速排序，并且返回切分元素的下标索引
* @param nums 原始数组
* @param left *** 作的短数组左边的下标索引
* @param right *** 作的短数组右边的下标索引
* @return
*/
private static int partition(int[] nums, int left, int right) {
//使用nextInt(int count)获得count以内的整数，不含count
//所以我们获得的是一个左闭右闭的范围，最后再加上1
int randomIndex = left + random.nextInt(right - left + 1);
swap(nums,randomIndex,left);//然后交换出随机出的数，将它放到开头。这样后面的代码就不用改了
int pivot = nums[left]; //选择切分元素，选择的这个切分的元素我们就将它设置为第一个元素
//这里的理解，可以看上面我画的图，下标位置索引都一样的
//代码执行流程和我画的图中的也都一样
int i = left + 1;
int j = right;
while (true) {
while (i <=j && nums[i] < pivot){
i ++;
}
while (j <= right && nums[j] > pivot) {
j --;
}
if (i >= j){
break;
}
swap(nums,i,j);
i++;
j--;
}
//排好序，再对切分元素交换到第一区间和第二区间之间来。
swap(nums, left, j);
return j;//最后返回切分元素的下标索引
}
/**
* 使用java.util.Random类，创建一个实例，使用nextInt(int count)获得count以内的整数，不含count
*/
private static Random random = new Random(System.currentTimeMillis());
/**
* 交换i和j之间的额元素
*
* @param nums 原始叔叔
* @param index1 交换的元素1
* @param index2 交换的元素2
*/
private static void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
三路快排，就是将我们相同的元素挪到了中间来，也是前两张的快速排序综合版本。
我们使用一个变量i将切分元素后面的所有的元素进行遍历。根据它与切分元素的数值大小关系分为三种情况。小于切分元素和等于切分元素划分到i
的前面，并且在一边遍历一边整理。当看到严格大于6的元素的时候，就将它甩到数组的末尾。
情况1： 当看到的元素 < pivot时，把它交换到 = pivot 这个区间的第一个位置
情况2：当看到的元素 = pivot时，什么都不做，接着看下一个元素就可以了。
情况3：当看到的元素 > pivot时，把它交换到 > pivot 这个区间的前一个位置。
下来通过一个形式化的例子来进行演示：
最后是当k大于j的时候，循环终止。
代码演示主要代码：
全部代码：
/**
* 采用三路快排的思想完成
*/
import java.util.Arrays;
import java.util.Random;
public class Demo912_5 {
public static void main(String[] args) {
int[] nums = {-1, 2, -8, -10}; //给定一个数组
int[] after = sortArray(nums); //的带排序后的数组
System.out.println(Arrays.toString(after)); //打印输出得到数组
}
private static int[] sortArray(int[] nums) {
int len = nums.length; //获得数组长度
quickSort(nums, 0, len - 1); //传递数组、left和right下面的索引位置
return nums; //返回数组
}
/**
* 划分短数组的 *** 作
*
* @param nums 原始数组
* @param left 0
* @param right nums.length - 1
*/
private static void quickSort(int[] nums, int left, int right) {
if (left >= right) { //当左边的索引位置大于等于右边的索引位置，就结束循环
return;
}
//使用nextInt(int count)获得count以内的整数，不含count
//所以我们获得的是一个左闭右闭的范围，最后再加上1
int randomIndex = left + random.nextInt(right - left + 1);
swap(nums, randomIndex, left);//然后交换出随机出的数，将它放到开头。这样后面的代码就不用改了
int pivot = nums[left]; //选择切分元素，选择的这个切分的元素我们就将它设置为第一个元素
//这里的理解，可以看上面我画的图，下标位置索引都一样的
//代码执行流程和我画的图中的也都一样
int i = left;
int j = right;
int k = left + 1;
while (k <= j) {
if (nums[k] < pivot) {
i++;
swap(nums, i, k);
k++;
} else if (nums[k] == pivot) {
k++;
} else {
swap(nums, k, j);
j--;
}
}
//排好序，再对切分元素交换到第二区间的最开始，就是和第一区间的最后一个做一个交换就可以了。
swap(nums, left, i);
//采用递归获得长的数组中切分元素的索引下标，为下次划分出两个数组做边界
quickSort(nums, left, i - 1);//上面长的数组左边的区间，进行排序
quickSort(nums, j + 1, right);//上面长的数组右边的区间，进行排序
}
/**
* 使用java.util.Random类，创建一个实例，使用nextInt(int count)获得count以内的整数，不含count
*/
private static Random random = new Random(System.currentTimeMillis());
/**
* 交换i和j之间的额元素
*
* @param nums 原始叔叔
* @param index1 交换的元素1
* @param index2 交换的元素2
*/
private static void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
第一种：
产生的问题：
对于几乎有序的数组来说，造成了递归树的倾斜，世界复杂度大大提高，到达了O(N^2)。
解决的办法：
就是破幻数组的有序性，所以我们随机的选择一个元素来作为切分的元素。
产生的问题：
随机选择切分元素对于那种拥有大量的重复元素的数组是无效的。
解决的办法：
使用双路快排或者三路快排。
第二种：
把与pivot想等的元素平均的分到数组的两侧。
第三种：
把与pivot相等的元素单独创造出一个区间，放到小于和大于的区间中间去。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）