快排算法（单路、双路、三路）
目录
1、优化：它比单路快速排序的不同在于它考虑了等于的情况，它把等于我们选取的值时放在了左边或者右边。
1、优化：当遇到相同的值，排序完成之后一定会连续出现，所以我们就可以减少一些不必要的操作将同一层级的相同的数据都解决了。
一、基本思想
通过一趟排序将待排序记录分隔成独立的两部分，其中左半部分的值比我们选取的数据要小，右半部分比我们选取的数据要大，则可继续对这两部分记录的数据继续进行排序，以达到整个序列有序。
时间复杂度：O（nlogn）
空间复杂度：O(1)
稳定性：不稳定
二、单路快速排序
1、缺点：我们没有过多考虑等于我们选取数据的情况时的处理。
2、目标实现：arr[l~(p-1)]<arr[p]<arr[(p+1)~r]
p:是我们选取的数据
l~(p-1)：表示 l ~(p-1)下标范围内都是小于我们选取数据的情况
(p+1)~r: 表示 (p+1)~r 下标范围内都是大于我们选取数据的情况
3、图画展示
4、代码实现
public class QuickSort {
public static void main(String[] args) {
int arr[]={5,6,2,5,1,3};
quickSortOneWay(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void quickSortOneWay(int[] arr, int l, int r) {
if(l>=r)return;
int p=partitionOneWay(arr,l,r);//把这个数组按照逻辑划分为两个部分
quickSortOneWay(arr,l,p-1);//左区间为1~p-1,进行递归操作
quickSortOneWay(arr,p+1,r);//右区间为p+1~r，进行递归操作
}
private static int partitionOneWay(int[] arr, int l, int r) {
swap(arr,l, (int) (Math.random()*(r-l+1)+l));//随机选取一个数据
int v=arr[l];//将v表示为我们选取的元素
int i=l;//i从l开始
int j=i+1;//j从i+1开始
while (j<=r){//只要满足j小于等于r进行循环
if(arr[j]<v){//如果j下标的值小于我们选取的值i+1跟j交换
swap(arr,i+1,j);
i++;//换完之后进行i++
}
j++;//不管是大于还是小于都需要j++
}
swap(arr,l,i);//循环遍历完之后我们将l和i的值进行交换，然后i左边就是完全小于我们选取的值，右边就是大于我们选取的值
return i;
}
private static void swap(int[] arr, int i, int j) {
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
三、双路快速排序
1、优化：它比单路快速排序的不同在于它考虑了等于的情况，它把等于我们选取的值时放在了左边或者右边。
2、画图展示
3、代码实现
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int arr[]={5,6,2,5,1,3};
quickSortTwoWay(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void quickSortTwoWay(int[] arr, int l, int r) {
if(l>=r)return;
int p= partitionTwoWay(arr,l,r);//把这个数组按照逻辑划分为两个部分
quickSortTwoWay(arr,l,p-1);//左区间为1~p-1,进行递归操作
quickSortTwoWay(arr,p+1,r);//右区间为p+1~r,进行递归操作
}
private static int partitionTwoWay(int[] arr, int l, int r) {
swap(arr,l, (int) (Math.random()*(r-l+1)+l));//随机选取一个数据
int v=arr[l];//v表示我们选取的值
int i=l+1;//i初始值为l+1
int j=r;//j初始值为r
while (true){
if(i<=r&&(arr[i]<v)){//当i再r以内且值小于我们选取的值i++
i++;
}else if(j>=l+1&&(arr[j]>v)){//当j大于l+1且值小于我们选取的值j--
j--;
}
if(i>j)break;
swap(arr,i,j);//交换两者的数据
i++;
j--;
}
swap(arr,l,j);
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
四、三路快速排序
1、优化：当遇到相同的值，排序完成之后一定会连续出现，所以我们就可以减少一些不必要的操作将同一层级的相同的数据都解决了。
2、画图展示：
3、代码展示
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int arr[]={5,6,2,5,1,3};
quickSortThreeWay(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
private static void quickSortThreeWay(int[] arr, int l, int r) {
if(l>=r)return;
swap(arr,l, (int) (Math.random()*(r-l+1)+l));
int v=arr[l];
int lt = l;
int gt = r+1;
int i = lt+1;
while (i<gt){
if(arr[i]<v){
swap(arr,i,lt+1);
lt++;
i++;
}else if(arr[i]>v){
swap(arr,i,gt-1);
gt--;
}else {
i++;
}
}
swap(arr,l,lt);
quickSortThreeWay(arr,l,lt-1);
quickSortThreeWay(arr,gt,r);
}
private static void swap(int[] arr, int i, int j) {
int temp =arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
五、快排模板
/**
* @name:快排(是不稳定的)稳定的意思是：原序列中两个数列的值是相同的排完序后位置不发生变化那么他就是稳定的
* @time:2021/6/7
* @content:
* 1、确定分界点常用的取值q[l]左边界值、q[(l+r)/2]中间值、q[r]右边值
* 2、调整区间，小于x的放左边，大于x的放右边
* 3、递归处理左右两段进行排序
*/
public class QuickSort {
private static void quick_sort(int q[],int l,int r) {
if(l>=r)return;
int x=q[(l+r)/2],i=l-1,j=r+1;
while(i<j) {
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) {
int temp;
temp=q[i];
q[i]=q[j];
q[j]=temp;
}
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
public static void main(String[] args) {
int arr[]={5,6,2,5,1,3};
quick_sort(arr,0,arr.length-1);
for(int i=0;i<n;i++)System.out.print(arr[i]);
}
}版权声明：本文为qq_48241564原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。