快速排序(QuickSort）算法介绍

算法简介

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

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

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

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

选第一个基准元素

41 3 6 7 5

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

3 146 7 5

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

1 3

5 6 7

得到有序的集合

1 3 4 5 6 7

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

快排是这样解决的，假设做正序排序：

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

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

6为基准数，设i，j为两哨兵，目前指向首尾两个数（加粗部分）。

61 2 7 9 3 4 5 108

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

6 1 279 3 4510 8

6 1 259 3 4710 8

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

1 259 3 4710 8

继续走直到相遇，基准数复位。

6 1 2 59347 10 8

6 1 2 54397 10 8

6 1 2 5 439 7 10 8

31 2 5 469 7 10 8

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

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

算法实践

以java演示一遍

public void quickSort(int[] arr, int low, int high) {// low,high 为每次处理数组时的首、尾元素索引//当low==high是表示该序列只有一个元素，不必排序了if (low >= high) {return;}// 选出哨兵元素和基准元素。这里左边的哨兵元素也是基准元素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;}

ForkJoinTask与快速排序

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

图片来自文章聊聊并发（八）——Fork/Join框架介绍。

这样来看，fork/join的处理模式与quickSort算法

倒很相似，都是不断分割任务以进行处理。而事实上，两者都是分治算法的实践者。我们可以将上述排序改成并发版的快速排序。

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;}@Overrideprotected 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;}}

测试结果

@Testpublic 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}