算法2.5.1快速排序（普通）
《算法》笔记导航
《算法》中文第四版P182
2020.7.18
@Stream_
public class Quick
使用快速排序之前请查看:算法2.0排序算法类的模板
快速排序：将一个数组分成两个部分，独立排序。分治思想是相同的，但是和归并实现并不同
递归的调用切分来排序，切分总能排定（到达该数字的最终位置）一个元素
一般比其他排序算法都要快得多
一、算法的排序过程及讲解
1.初始数据
11 1 15 4 2 16 8 13 7 3 10 9 5 12 6 14
2.排序过程
11 1 15 4 2 16 8 13 7 3 10 9 5 12 6 14
13 2 14 4 15 11 6 9 16 10 7 3 8 5 1 12
//为了避免出现低劣的性能，需要在这里进行随机打乱（必要的）
13
13 2 12 4 15 11 6 9 16 10 7 3 8 5 1 14
13 2 12 4 1 11 6 9 16 10 7 3 8 5 15 14
13 2 12 4 1 11 6 9 5 10 7 3 8 16 15 14
8 2 12 4 1 11 6 9 5 10 7 3 13 16 15 14
8
8 2 3 4 1 11 6 9 5 10 7 12 13 16 15 14
8 2 3 4 1 7 6 9 5 10 11 12 13 16 15 14
8 2 3 4 1 7 6 5 9 10 11 12 13 16 15 14
5 2 3 4 1 7 6 8 9 10 11 12 13 16 15 14
5
1 2 3 4 5 7 6 8 9 10 11 12 13 16 15 14
1
1 2 3 4 5 7 6 8 9 10 11 12 13 16 15 14
2
1 2 3 4 5 7 6 8 9 10 11 12 13 16 15 14
3
1 2 3 4 5 7 6 8 9 10 11 12 13 16 15 14
7
1 2 3 4 5 6 7 8 9 10 11 12 13 16 15 14
9
1 2 3 4 5 6 7 8 9 10 11 12 13 16 15 14
10
1 2 3 4 5 6 7 8 9 10 11 12 13 16 15 14
11
1 2 3 4 5 6 7 8 9 10 11 12 13 16 15 14
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
//每行单个数字指的是这次选择哪个数字进行切分。
3.排序讲解
-
11 1 15 4 2 16 8 13 7 3 10 9 5 12 6 14
为了避免出现低劣的性能，需要在这里进行随机打乱，在数学概率上基本能完全避免，除非重复的数据过多（可以选择2.5.2的三向切分的快速排序）。
随机的结果每次都是不同的，大致理解即算法的处理过程即可。 -
13 2 14 4 15 11 6 9 16 10 7 3 8 5 1 12
这是随机乱序的结果。
选择a[0]=11进行切分，让11到达它最终的位置（它左边的比它小，右边的比它大）。
左边的指针（只是标记位置的下标数字而已，习惯称其为指针）i=1,a[i]=2和a[0]=13比较，因为2小于13，继续查询左侧。
i=2,a[j]=14和a[0]=13比较，因为14大于13，所以i不变，从右边开始获得可交换的指针。
j=15,a[j]=12和a[0]=13比较，因为12小于13，所以进行交换。
交换a[i]和a[j]，即a[2]=14和a[15]=12。 -
13 2 12 4 15 11 6 9 16 10 7 3 8 5 1 14
左边的指针i继续查询,i=3,a[i]=4,比a[0]小,查询左侧。
i=4,a[i]=15,比a[0]大，所以从右边找。
右边的指针j继续查询,j=14,a[j]=1,比a[0]小,进行交换。
a[4]=15和a[14]=1交换. -
13 2 12 4 1 11 6 9 16 10 7 3 8 5 15 14
接下来的部分相同 -
13 2 12 4 1 11 6 9 5 10 7 3 8 16 15 14
此时，i=8,j=13。
i=9,a[i]=10,左侧查询;
i=10,a[i]=7,左侧查询;
直到i=13,此时i比j大，因为j之后直到限定的范围（j从哪里开始）都比i大，所以i=13,a[i]=16,停止。
j=12,a[j]=8,停止查询。
因为i>j，所以停止此次循环。
将a[0]和a[j]进行交换。
a[j]=13,a[0]=8。 -
8 2 12 4 1 11 6 9 5 10 7 3 13 16 15 14
首先在此次方法结束之前，递归调用。
a[12]=13是原来的位置，因为这位位置已定，左侧都比它小，右侧都比它大，所以只需对两侧的进行排序。
从a[0]到a[11]调用方法。
从a[13]到a[15]调用方法。
在第一个调用方法中，用a[0]去逐一比较，i从1开始，j从11开始。
在第二个调用方法中，用a[13]去逐一比较，i从14开始，j从15开始。
二、算法的解析
1.打乱数组顺序
public static void shuffle(Comparable[] a)
为了避免出现低劣的性能，需要在这里进行随机打乱（必要的）
需要引用：import java.util.Random;
public static void shuffle(Comparable[] a){//将数组打乱的函数，目的是将最糟糕的情况的可能降到极低
int N=a.length-1;
int j;
Random r=new Random(); //创建一个Random类对象
for(int i=N;i>=0;i--){
j=r.nextInt(i+1); //获得一个从0到i大小的int随机数
exch(a,i,j); //由后向前，先随机交换，然后固定这位数据
}
}
2.快速排序切分
将大数组切分成两个小数组和一个数。
private static int partition(Comparable[] a,int lo,int hi){
int i=lo,j=hi+1;
Comparable v=a[lo]; //用于比较的数
System.out.println(v);
while (true){
while (less(a[++i],v)){ //左侧指针
if(i==hi){
break;
}
}
while(less(v,a[--j])){ //右侧指针
if(j==lo){
break;
}
}
if(i>=j){ //越界
break;
}
exch(a,i,j);
//show(a);
}
exch(a,lo,j); //结束的时候，把用于比较的数放在最终应该在的位置上。
//show(a);
return j;
}
3.排序算法主方法
public static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo){
return; //越界
}
int j=partition(a,lo,hi); //切分大数组
sort(a,lo,j-1); //对小数组进行排序
sort(a,j+1,hi);
}
4.其他方法
请查看:算法2.0排序算法类的模板
三、算法的实现
import java.util.Random;
public class Quick {
public static void sort(Comparable[] a){
shuffle(a);
show(a);
sort(a,0,a.length-1);
}
public static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo){
return;
}
int j=partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(Comparable[] a,int lo,int hi){
int i=lo,j=hi+1;
Comparable v=a[lo];
System.out.println(v);
while (true){
while (less(a[++i],v)){
if(i==hi){
break;
}
}
while(less(v,a[--j])){
if(j==lo){
break;
}
}
if(i>=j){
break;
}
exch(a,i,j);
show(a);
}
exch(a,lo,j);
show(a);
return j;
}
public static void shuffle(Comparable[] a){//将数组打乱的函数，目的是将最糟糕的情况的可能降到极低
int N=a.length-1;
int j;
Random r=new Random(); //创建一个Random类对象
for(int i=N;i>=0;i--){
j=r.nextInt(i+1); //获得一个从0到i大小的int随机数
exch(a,i,j); //由后向前，先随机交换，然后固定这位数据
}
}
//以下程序的解析请查看：算法2.0排序算法类的模板
private static boolean less(Comparable v,Comparable w){
return v.compareTo(w)<0;
}
private static void exch(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
private static void show(Comparable[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
public static boolean isSorted(Comparable[] a){
for(int i=1;i<a.length;i++){
if(less(a[i],a[i-1])){
return false;
}
}
return true;
}
}
四、算法的使用
import java.util.Arrays;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public class test01 {
public static void main(String[] args) {
int[] nums={11,1,15,4,2,16,8,13,7,3,10,9,5,12,6,14};
//先将int数组转换为数值流
IntStream stream = Arrays.stream(nums);
//流中的元素全部装箱，转换为流 ---->int转为Integer
Stream<Integer> integerStream = stream.boxed();
//将流转换为数组
Integer[] integers = integerStream.toArray(Integer[]::new);
Quick.sort(integers);
}
}
四、算法的特点、优劣和使用场景
- 1.适用于各种不同的输入数组且在一般应用比其他排序算法都快得多
- 2.它是原地排序（只需要很小的一个辅助栈）
- 3.缺点是非常脆弱，需要非常小心才能避免低劣的性能
- 4.切分方法只比较，很少移动。快速排序比较次数较少。
- 5.重复很多次的随机问题，能有效减低糟糕切分的可能性
- 6.小数组可以选择插入排序
- 7.可以选择三取样切分改进快排性能（取前三个值的中间值作切分）
- 8.快排对含有大量重复元素的数组排序时用时超过平方级别
//实际使用的代码
public static void quick_sort(int s[], int l, int r)
{
if(l>=r){
return;
}
int i = l, j = r, x = s[l];
while (i < j) {
while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
j--;
if (i < j)
s[i++] = s[j];
while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
i++;
if (i < j)
s[j--] = s[i];
}
s[i] = x;
quick_sort(s, l, i - 1); // 递归调用
quick_sort(s, i + 1, r);
}
渣渣菜鸡，难免错误，请友善讨论
非商用转载需注明作者及文章链接来源，私信告知后无需我回复即可直接转载
