1、普通快速排序
思想：
该方法运用了分治的思想，它将一个数组分成两个子数组，将两部分独立地排序，当两个子数组都有序时，整个数组也就自然有序了，其重点在于对数组进行切分。
图示：
切分轨迹
快速排序
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61public class Quick {
public static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private 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];//切分元素
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);
}
exch(a,lo,j);//将v=a[j]放入正确的位置
return j;
}
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
StdOut.print(a[i]+” “);
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a){
for(int i=1;i
if(less(a[i],a[i-1]))
return false;
}
return true;
}
public static void main(String[] args) {
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
说明：主要是对partition函数进行分析，两个while循环用于对下标进行控制，以切分点为分割，一个从左向右，一个从右向左，其中有3个break条件，一个是左边走完，一个是右边走完，一个是左边部分的下标超过右边部分，最后就对满足要求的值进行交换，循环结束之后将切分的值进行交换完成整个排序。
时间复杂度：平均情况O(nlog2n)，最坏O(n2)，最好O(nlog2n)
空间复杂度：O(nlog2n)
稳定性：不稳定，可能会随着前后部分数值的调换而使两个相同数值的位置进行调换。
2、三向切分快速排序
思想：
它与快排的主要区别在于它适合处理重复元素较多的情况。这样就可以减少在已经选定切分元素的情况下，仍然将多个与切分元素相同的值放入子数组中进行排序。它维护了三个指针，lt指针使得a[lo…lt-1]中的元素都小于v(v为选定的切分元素)，gt指针使得a[gt+1…hi]中的元素都大于v，而指针i使得a[lt…i-1]中的元素都等于v。
总共处理3种情况：
a[i]
a[i]>v，将a[gt]和a[i]交换，将gt减一
a[i]等于v，将i加一。
图示：
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51public class Quick3way {
public static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a,int lo,int hi){
if(hi<=lo)
return;
int lt=lo,i=lo+1,gt=hi;
Comparable v =a[lo];
while(i<=gt){
int cmp = a[i].compareTo(v);
if(cmp<0)
exch(a,lt++,i++);
else if(cmp>0)
exch(a,i,gt–);
else
i++;
}
sort(a,lo,lt-1);
sort(a,gt+1,hi);
}
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
StdOut.print(a[i]+” “);
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a){
for(int i=1;i
if(less(a[i],a[i-1]))
return false;
}
return true;
}
public static void main(String[] args) {
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
时间复杂度：平均情况O(nlog2n)，最坏O(n2)，最好O(nlog2n)
空间复杂度：O(nlog2n)
稳定性：不稳定，可能会随着前后部分数值的调换而使两个相同数值的位置进行调换。
这其中的StdOut、StdRandom以及StdIn库使用自algs4这个jar包，下载地址：
https://algs4.cs.princeton.edu/code/algs4.jar