Fork me on GitHub

排序算法(八) - 三路快速排序

前言

上篇文章我们讲到了双轴快速排序,今天我们来看下快排的另一种 - 三路快速排序(ThirdWayQuickSort),也称三向切分的快速排序。

正文

简介及原理

三路快速排序(ThirdWayQuickSort)是如何出现的呢?

我们知道,对于待排序数组,其数据是随机的,如果数组中有大量相同元素,无论普通快排还是双轴快排,由于快速排序的判定问题,会导致这些重复数移到一边从而大幅增加算法的运算时间。

为了优化这种数据情况,进而出现了三路快速排序。

三路快速排序也是采用一个轴值pivot,那具体是哪三路呢?

三路指的就是每分割(Partition)一次,三路排序会把数据分为小于pivot、等于pivot和大于pivot的三部分。

三路排序的大致原理如下:

  1. 对于待排序数组,选取第一个元素为中轴pivot;
  2. 每次分割处理将小于pivot的数据放到左边,等于pivot的数据放在中间,大于pivot的数据放在右边;
  3. 对小于pivot和大于pivot的部分重复分割过程。

我们以一个数组为例,来看下它的原理,如下图。

upload successful

其算法描述如下:

  1. 对于待排序数组a,最左索引为left,最右索引为right
  2. 排序过程中,以a[left]最为pivot,用ijk将数组分割为4部分,其中i表示pivot元素的起始index,所有小于pivot的元素下标都应该小于ik表示待扫描的元素索引从i+1开始,到j结束;j表示待扫描元素的最后索引;
  3. 开始时i=leftk=left+1,j=right,此时小于pivot的元素为0个,大于pivot的元素为0个,待扫描的元素为j-k+1个;
  4. k开始扫描,当该元素比pivot小时,交换a[i]a[k],同时i++k++,这样就能把该元素放到pivot的左边了;
  5. 当该元素等于pivot时,略过即可,即k++
  6. 当该元素大于pivot时,需要把它放到右边,先看下a[j]pivot的大小。

    (1) 如果a[j] > pivot,显然它已经在右边了,我们只需j–即可;

    (2) 如果a[j] = pivot,这时候我们需要交换a[k]a[j]的位置,同时k++,j–即可;

    (3) 如果a[j] < pivot,这时候我们除了交换a[k]a[j]位置后,继续交换a[i]a[k]的位置,将这个小元素移到左边,同时i++,j–,k++;

  7. 最后数据会被分为大于pivot、小于pivot、等于pivot的三部分,我们对大于pivot和小于pivot的部分再进行上述逻辑,直到传入的数据长度为1,说明数据全部有序了。

动图演示

upload successful

代码实现

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
61
62
63
64
65
66
67
68
69
70
public class ThirdWayQuickSort {
public static void quickSort3Way(int[] a, int left, int right) {
//递归终止条件,少于等于一个元素的数组已有序
if (left >= right) {
return;
}
int i, j, k, pivot;
//首元素作为中轴
pivot = a[left];
i = left;
k = left + 1;
j = right;

outer:
while (k <= j) {
if (a[k] < pivot) {
swap(a, i, k);
i++;
k++;
} else if (a[k] == pivot) {
k++;
} else {// 遇到A[k]>pivot的情况,j从右向左扫描
//A[j]>pivot的情况,j继续向左扫描
while (a[j] > pivot) {
j--;
if (j < k) {
break outer;
}
}
//A[j]==pivot的情况
if (a[j] == pivot) {
swap(a, k, j);
k++;
j--;
} else {//A[j]<pivot的情况
swap(a, i, j);
swap(a, j, k);
i++;
k++;
j--;
}
}
}
//A[i, j] 等于 pivot 且位置固定,不需要参与排序
// 对小于pivot的部分进行递归
quickSort3Way(a, left, i - 1);
// 对大于pivot的部分进行递归
quickSort3Way(a, j + 1, right);
}

private static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}

public static void main(String[] args) {
int[] a = new int[100000000];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100000);
}
System.out.println("ThirdWayQuickSort排序开始:");
long start = System.currentTimeMillis();
quickSort3Way(a,0,a.length-1);
System.out.println("ThirdWayQuickSort耗时:"+(System.currentTimeMillis()-start)+"ms");
System.out.println("ThirdWayQuickSort排序完成!");
System.out.println("数组是否有序:"+isOrdered(a));
}
}

其他注意事项

三路快排的时间复杂度与快速排序相当:

  • 时间复杂度(最好):O(n * log n)
  • 时间复杂度(平均):O(n * log n)
  • 时间复杂度(最差):O(n^2)

三路快排的空间复杂度为O(n * log n) (递归消耗栈空间,是一种就地排序算法,如果从堆空间角度空间复杂度为O(1))

三路快排也是一种不稳定排序算法。

相比普通快排和双轴快排,我们可以看到三路快排对于有重复数据的数组处理较佳,可以减少元素交换次数。

测试相关

我们来实际测试下,相关代码如下:

我们准备1亿数据,但是数据集范围为[0,10000),这时候相同元素产生的就会比较多,我们分别测试下三路快排、双轴快排和普通快排。

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
public static void main(String[] args) {
int[] a = new int[100000000];
Random r = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(10000);
}
int[] b = a.clone();
int[] c = a.clone();

System.out.println("ThirdWayQuickSort排序开始:");
long start = System.currentTimeMillis();
quickSort3Way(a,0,a.length-1);
System.out.println("ThirdWayQuickSort耗时:"+(System.currentTimeMillis()-start)+"ms");
System.out.println("ThirdWayQuickSort排序完成!");
System.out.println("数组是否有序:"+isOrdered(a));

System.out.println("DualPivotQuickSort排序开始:");
long start1 = System.currentTimeMillis();
DualPivotQuickSort.dualPivotQuickSort(b,0,b.length-1);
System.out.println("DualPivotQuickSort耗时:"+(System.currentTimeMillis()-start1)+"ms");
System.out.println("DualPivotQuickSort排序完成!");
System.out.println("数组是否有序:"+isOrdered(b));

System.out.println("QuickSort排序开始:");
long start2 = System.currentTimeMillis();
QuickSort.quickSort(c,0,c.length-1,true);
System.out.println("QuickSort耗时:"+(System.currentTimeMillis()-start2)+"ms");
System.out.println("QuickSort排序完成!");
System.out.println("数组是否有序:"+isOrdered(c));
}

多次测试结果大致如下:

upload successful

我们可以看到,当数据集重复元素较多时,三路快排确实有着比较优的排序效率。

我们将数据集范围改为[0,100),效果更加明显。

1
2
3
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100);
}

upload successful

我们增大数据集范围,改为[0,100000000),再来测试一下。

1
2
3
for (int i = 0; i < a.length; i++) {
a[i] = r.nextInt(100000000);
}

upload successful

可以看到三路快排效率比不上双轴快排了,因为这种情况下,重复元素较少,三路快排基本退化为普通快排。

总结

通过对三路快排(ThirdWayQuickSort)的介绍,我们大致了解了它的一些原理和排序过程,快速排序主要就有普通快排、三路快排和双轴快排三种。

在数据集元素重复较多的情况下,三路快排有着显著的优势,因此它和双轴快排一起,作为了Java对基本数据类型排序方法实现的一部分。

源码地址

本篇文章提到的所有代码均可见于我的GitHub




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

SakuraTears wechat
扫一扫关注我的公众号
您的支持就是我创作的动力!
0%