Quick Sort 快速排序
快排大致分为三种: 单路快排, 双路快排 和 三路快排
单路快排
单路快排思想非常简单: 将数组进行partition 操作, 将数组分成 <= partition 和 > partition元素两个部分, 随后对左右子数组执行同样操作.
用代码表示如下:
public class QuickSort {
private QuickSort(){}
private static Random RandomGenerator=new Random();//随机数生成器
public static <E extends Comparable<E>> void sortOneWay(E[] arr){
sortOneWay(arr,0,arr.length-1);//单路快排
}
private static <E extends Comparable<E>> void sortOneWay(E[] arr, int l, int r){
if (l>=r){
return;
}
int p=partition1(arr,l,r);
sortOneWay(arr,l,p-1);
sortOneWay(arr,p+1,r);
}
}partition 操作
partition 操作是快速排序的核心代码.
我们定义了循环不变量 arr[ l+1, i] <= p, arr[ i+1, j-1] > p
当 j >r 时, 索引越界, 说明已经遍历完了 arr [ l, r ] 中的所有元素
最后交换 arr [ l ] 和 arr [ i ], return i 完成partition 操作
用代码表示如下:
//单路快排 partition
private static <E extends Comparable<E>> int partition1(E[] arr, int l ,int r){
//在arr中随机选择一个元素,与arr[l]进行交换,防止对于有序数组,退化成O(n^2)
int randomIdx= l+ RandomGenerator.nextInt(r-l+1);
swap(arr,l,randomIdx);
int i=l;
int j=l+1;
while ( j<=r ){
if (arr[j].compareTo(arr[l])<=0){
swap(arr,i+1,j);
i++;
j++;//时时刻刻都要照顾到循环控制变量
}else {
j++;
}
}
//交换arr[l] arr[j]
swap(arr,l,i);
return i;
}特别的注意: 我们随机的选取了一个 partition 元素 与 arr [ l ] 进行交换
假设不这么做, 数据完全有序, 那么快排的左边子数组将会缺失, 只剩下右边的子数组, 快速排序的二分性质将不复存在! 时间复杂度将退化成O(N^2)
交换数组元素的代码非常简单:
//静态方法只能调用静态方法,若不写static,则调用的时候会报错
private static <E>void swap(E[] arr,int a, int b){
E temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}双路快排
上面的单路快排仍然是有缺陷的. 假设数据全部相等, 那么partition 后右边的子数组将会缺失, 快速排序的二分性质将不复存在! 时间复杂度将退化成O(N^2).
为了解决这一问题,我们使用了双路快排, 其核心思想是将等于 partition的元素平均地分散到数组两端, 维持快速排序的等分性质
接口函数的逻辑和单路快排完全一致, 差别在于partition部分
public static <E extends Comparable<E>> void sortTwoWays(E[] arr){
sortTwoWays(arr,0,arr.length-1);//双路快排
}
private static <E extends Comparable<E>> void sortTwoWays(E[] arr, int l, int r){
if (l>=r){
return;
}
int p=partition2(arr,l,r);
sortTwoWays(arr,l,p-1);
sortTwoWays(arr,p+1,r);
}partition 操作
双路快排的partition操作较为复杂, 我们需要将 等于partition的元素均匀地分散到数组两边, 用到的索引指针非常容易出错!!!
我们定义了循环不变量 arr[ l+1, i-1] <= p, arr[ j+1, r ] >= p
当 i >j 时, 索引越界, 说明已经遍历完了 arr [ l, r ] 中的所有元素
最后交换 arr [ l ] 和 arr [ j ], return j 完成partition 操作
双路快排的 partition 操作的核心是如何更新索引 i 和 j, 这两个索引非常容易出错 !!!
首先判断 arr [ i ] 和 partition 的关系, 若 arr [ i ]< partiotion, i++ 即可. 若 arr [ i ] >= partition, 则将 arr[ i ] 与 arr [ j ] 进行交换, 相当于把一个可能和partition 相等的元素放到了数组的右边, 随后 j - - .
由于我们遍历数组的条件是 i<=j , 所以一旦更新了 i 和 j 就需要判断是否已经完成了遍历, 否则后续判断 arr [ j ] 和 partition 的关系时 会抛出索引越界的异常
接下来再判断arr [ j ] 和 partition 的关系. 若 arr [ j ]> partiotion, j - - 即可. 若 arr [ j ] <= partition, 则将 arr[ i ] 与 arr [ j ] 进行交换, 相当于把一个可能和partition 相等的元素放到了数组的左边边, 随后 i + + .
遍历完数组以后, 将 arr [ l ] 和 arr [ j ] 交换, 而不能和 arr [ i ]交换 因为 arr [ i ]可能比partition要大
最后 return j, 完成 partition 操作.
整个过程代码如下:
//双路快排 partition
private static <E extends Comparable<E>> int partition2(E[] arr, int l ,int r){
int randomIdx= l+ RandomGenerator.nextInt(r-l+1);
swap(arr,l,randomIdx);
int i=l+1,j=r;
while (i<=j){
//先判断 i 这边
if (arr[i].compareTo(arr[l])<0){
i++;
}else{//若 arr[i] 与 partition元素 相等, 放到左边
swap(arr,i,j);
j--;
}
//一个准则: 循环控制量必须要和循环判断条件紧密结合!!!
//一旦改变循环控制量,必须马上进入循环条件判断,否则接下来的执行代码压根不满足在循环内的条件
if (i>j)
break;
//先判断 j 这边
if (arr[j].compareTo(arr[l])>0){
j--;
}else {//若 arr[i] 与 partition元素 相等, 放到右边
swap(arr,i,j);
i++;
}
}
//遍历结束后, j==i-1, arr[l,j]<= partition, arr[i,r]>=partition
//arr[l] 必须要和 arr[j] 交换, 而不能和arr[i]交换 因为arr[i]可能比partition要大
swap(arr,l,j);
return j;
}三路快排
上面的双路快排仍然是有优化空间的. 假设我们在partition中将数组分成三个部分,一部分<= partition元素, 一部分等于partition元素, 一部分大于partition元素, 那么在面对所有数据相等的情况下,只需要进行一次partition操作即可, 时间复杂度进化成O(N).
一句话, 三路快排在双路快排基础上进一步优化了 大量数据重复 情况下的性能
方法接口部分和双路快排逻辑略有不同, partition3返回的不再是一个索引,而是两个索引的数组
public static <E extends Comparable<E>> void sortThreeWays(E[] arr){
sortThreeWays(arr,0,arr.length-1);//三路快排
}
private static <E extends Comparable<E>> void sortThreeWays(E[] arr, int l, int r){
if (l>=r){
return;
}
int[] p=partition3(arr,l,r);
sortThreeWays(arr,l,p[0]-1);
sortThreeWays(arr,p[1]+1,r);
}partition
我们定义了循环不变量 arr[ l+1, it] < p, arr [ lt+1, i-1 ] == p, arr[ gt, r ] > p
当 i >= gt 时, 索引越界, 说明已经遍历完了 arr [ l, r ] 中的所有元素
最后交换 arr [ l ] 和 arr [ it ], return [lt, gt - 1 ] 完成 partition 操作
整个过程代码如下:
//三路快排 partition
private static <E extends Comparable<E>> int[] partition3(E[] arr, int l ,int r){
int randomIdx= l+ RandomGenerator.nextInt(r-l+1);
swap(arr,l,randomIdx);
int lt=l,i=l+1,gt=r+1;
while (i<gt){
if (arr[i].compareTo(arr[l])<0){
swap(arr,i,lt+1);
lt++;
i++;
}else if(arr[i].compareTo(arr[l])==0){
i++;
}else {
swap(arr,i,gt-1);
gt--;
}
}
swap(arr,l,lt);
int[] ret={lt,gt-1};
return ret;
}性能测试与分析
根据上面的分析,我们可以轻易写出不同版本的快速排序时间复杂度
快排版本
完全随机
完全有序
元素完全相等
单路快排(无随机化partition元素)
NlogN
N^2
N^2
单路快排(随机化partition元素)
NlogN
NlogN
N^2
双路快排(随机化partition元素)
NlogN
NlogN
NlogN
三路快排(随机化partition元素)
NlogN
NlogN
N
我们测试一下不同版本的快排:
public static void main(String[] args) {
int n =1000000;
//对于完全随机的数组,归并和单路快排均为O(NlogN)
//但单路快排在分治过程中,避免了频繁的数组复制操作,性能略优
Integer[] arr1=ArrayGenerator.generateRandomArray(n,n);//随机数据
Integer[] arr2= Arrays.copyOf(arr1,arr1.length);
System.out.println("随机数据");
SortingHelper.sortTest("MergeSort",arr1,n);
SortingHelper.sortTest("QuickSortOneWay",arr2,n);
//对于有序数组, 归并排序会进化成O(N)
arr1=ArrayGenerator.generateOrderedArray(n);//有序数据
arr2= Arrays.copyOf(arr1,arr1.length);
System.out.println("有序数据");
SortingHelper.sortTest("MergeSort",arr1,n);
SortingHelper.sortTest("QuickSortOneWay",arr2,n);
//对于全部元素相等的数组,归并排序进化成(logN), 单路快排会退化成O(n^2),双路快排依然是O(NlogN), 三路快排进化成O(N)
arr1=ArrayGenerator.generateRandomArray(n,1);//重复数据
arr2= Arrays.copyOf(arr1,arr1.length);
Integer[] arr3= Arrays.copyOf(arr1,arr1.length);
System.out.println("重复数据");
SortingHelper.sortTest("MergeSort",arr1,n);
//单路直接达到最大递归深度, 栈溢出
SortingHelper.sortTest("QuickSortTwoWays",arr2,n);
SortingHelper.sortTest("QuickSortThreeWays",arr3,n);
}输出结果
随机数据
n=1000000 ,MergeSort花费时间0.6884032秒
n=1000000 ,QuickSortOneWay花费时间0.5798061秒
有序数据
n=1000000 ,MergeSort花费时间0.0128925秒
n=1000000 ,QuickSortOneWay花费时间0.1713661秒
重复数据
n=1000000 ,MergeSort花费时间0.0103178秒
n=1000000 ,QuickSortTwoWays花费时间0.2680609秒
n=1000000 ,QuickSortThreeWays花费时间0.0181259秒
Process finished with exit code 0
可以看出和我们预料的结果完全一样.
Last updated
Was this helpful?