快速排序(QuickSort)实践

算法简介

快速排序(Quicksort)是对冒泡排序的一种改进算法。由C. A. R. Hoare在1960年提出。该算法使用广泛、效率很高,是最重要的排序算法之一。

该算法的实现基本可分为以下几步:

  1. 在数组中选一个基准数(通常为数组第一个)。
  2. 将数组中小于基准数的数据移到基准数左边,大于基准数的移到右边
  3. 对于基准数左、右两边的数组,不断重复以上两个过程,直到每个子集只有一个元素,即为全部有序。

示例有一数组为4 1 8 3 7 5,依上面的思路排序过程为

  1. 选第一个基准元素

    4 1 3 6 7 5

  2. 以基准元素为中心将数组分成两个子集

    3 1 4 6 7 5

  3. 将两个子集重复以上操作,直到全部有序

    1 3

    5 6 7

  4. 得到有序的集合

    1 3 4 5 6 7

以上是快速排序的基本思路,这里比较重要的是第2点,如何将一个数组以基准数为中心分为两部分呢?

快排是这样解决的,假设做正序排序:

在数组的头部和尾部分别设置一个哨兵,同时向对方走去。尾部的哨兵如发现有比基准数小的数,停下。头部的哨兵如发现有比基准数大的数,停下。交换两个数。再重新走重复前面的交换过程。直到两个哨兵相遇,交换基准数和尾哨兵。

有一数组为6 1 2 7 9 3 4 5 10 8,带着这样做为什么可以的态度来看一下演示。

  1. 6为基准数,设i,j为两哨兵,目前指向首尾两个数(第一个数6即是基准数,又是哨兵i)。

    6 1 2 7 9 3 4 5 10 8

  2. 两哨兵分别走向对方,直到遇到交换条件,并做交换。

    6 1 2 7 9 3 4 5 10 8

    6 1 2 5 9 3 4 7 10 8

  3. 此时来观察交换后的队列,除去基准数,是不是哨兵走过的位置都已部分有序了呢? 左边1 2 5都比基准数小,右边7 10 8都比基准数大。

    1 2 5 9 3 4 7 10 8

  4. 继续走直到相遇,基准数复位。

    6 1 2 5 9 3 4 7 10 8

    6 1 2 5 4 3 9 7 10 8

    6 1 2 5 4 3 9 7 10 8

    3 1 2 5 4 6 9 7 10 8

这样就完美地将一个数组以一个基准数为中心分为两个子集。然后重复这个过程即可实现快速排序。

有一点需特别注意:若以第一个元素为基准数(就如上面的示例),在哨兵互走过程需右边的哨兵先走。 原因很好理解,看上面过程解析就会明白:哨兵互走交换的过程就是不断排序的过程。若右边的哨兵先走,不管走多少次,最后相遇时的那个数是小于基准数的。这时与基准数交换,正好分为两个序列。可若是左边的先走,相遇在大于基准数上就不好办了。

算法实践

以java演示一遍

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
public void quickSort(int[] arr, int low, int high) {
// low,high 为每次处理数组时的首、尾元素索引

//当low==high是表示该序列只有一个元素,不必排序了
if (low >= high) {
return;
}
// 选出哨兵元素和基准元素。这里左边的哨兵元素为第1个元素(也为基准元素)
int i = low, j = high, base = arr[low];
while (i < j) {
//右边哨兵从后向前找
while (arr[j] >= base && i < j) {
j--;
}
//左边哨兵从前向后找
while (arr[i] <= base && i < j) {
i++;
}
swap(arr,i,j); //交换元素
}
swap(arr,low,j); //基准元素与右哨兵交换

//递归调用,排序左子集合和右子集合
quickSort(arr,low,j-1);
quickSort(arr,j+1,high);

}

private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

非递归实现快速排序

有时我们考虑递归的性能及可能的调用栈溢出的情况,会考虑使用非递归的形式处理问题。这时可以添加一个栈结构(先进后出)来代替递归的实现。

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
 public void quickSortNotR(int[] arr) {
int low = 0;
int high = arr.length - 1;
Stack<Integer> stack = new Stack<>();
stack.push(low);
stack.push(high);
while (!stack.empty()) {
int j = stack.pop();
int i = stack.pop();
int k = partSort(arr, i, j);
if (i < k - 1) {
stack.push(i);
stack.push(k - 1);
}
if (j > k + 1) {
stack.push(k + 1);
stack.push(high);
}
}
}

public int partSort(int[] arr, int low, int high) {
int base = arr[low];
int i = low;
int j = high;
while (i < j) {
while (arr[j] >= base && i < j) {
j--;
}
while (arr[i] <= base && i < j) {
i++;
}
swap(arr, i, j);
}
swap(arr, low, j);
return j;
}

这里将一次排序过程抽象成一个方法partSort()。主要实现quickSortNotR()思路依旧和递归类似。只是将每次分成的小数组存入栈中(与递归压入方法栈类似效果),添加了一个辅助存储空间,但避免了方法栈溢出等问题。

ForkJoinTask与快速排序

Fork/Join框架是Java7提供了的一个用于并行执行任务的框架。它可以充分利用多核CPU的优势,将一个大任务切割成多个足够小的任务并行执行(fork),等所有子任务执行完毕后合并结果(join),流程图类似下面:

这里写图片描述

图片来自文章聊聊并发(八)——Fork/Join框架介绍

这样来看,fork/join的处理模式与quickSort算法
倒很相似,都是不断分割任务以进行处理。而事实上,两者都是分治算法的实践者。我们可以将上述排序改成并发版的快速排序。

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
class SortTask extends RecursiveAction{

private int[] arr;

private int low;

private int high;

public SortTask(int[] arr,int low,int high) {
this.arr = arr;
this.high = high;
this.low = low;
}

@Override
protected void compute() {
if(low<high){
int i=low,j=high,base = arr[low];
while (i<j){
while (arr[j]>=base && i<j){
j--;
}
while (arr[i] <= base && i < j) {
i++;
}
swap(arr,i,j);
}
swap(arr,low,j);
SortTask leftTask =new SortTask(arr,low,j-1);
SortTask rightTask =new SortTask(arr,j+1,high);
//分割成子任务并执行,join()方法会再次调用compute()方法。
leftTask.fork();
rightTask.fork();
leftTask.join();
leftTask.join();
}
}

private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}

测试结果

1
2
3
4
5
6
7
8
9
10
@Test
public void test()throws Exception {
ForkJoinPool forkJoinPool = new ForkJoinPool();
int[] arr = {4, 1, 8, 6, 7, 9, 3, 2};
SortTask sortTask = new SortTask(arr,0,arr.length-1);
ForkJoinTask<Void> task = forkJoinPool.submit(sortTask);
task.get();
Arrays.stream(arr).forEach(e->System.out.print(e+" "));
// 1 2 3 4 6 7 8 9
}

参考

  1. 坐在马桶上看算法:快速排序
  2. 快速排序(三种算法实现和非递归实现)
分享到:
0%