18 -- 排序算法之快速排序

 从中可以发现：每次以哪个数为基准，哪个数就能被放置在最终拍好顺序的正确位置，示意图中是以每组数中的最后一个数作为基准的，需要指出的是：基准的选择不是确定的，也就是说，我们可以选择任意一个数作为基准，但是这个基准的选择需要遵循一定的规则（如：该组数最后一个，第一个，中间的数...）

示例程序是以每组数中间的索引所代表的数作为索引：

 1 import java.util.Arrays;
 2 
 3 public class QuickSort {
 4 
 5     public static void main(String[] args) {
 6         int[] arr = {9,78,0,23,-567,70};
 7         quickSort(arr, 0, arr.length - 1);
 8         System.out.println(Arrays.toString(arr));
 9     }
10     
11     public static void quickSort(int[] arr,int left, int right) {
12         int l = left;
13         int r = right;
14         int tmp = 0;
15         //pivot中间值
16         int pivot = arr[(l+r)/2];
17         while(l < r) {
18             while(arr[l] < pivot) { //从pivot左边找到一个大于pivot的值
19                 l ++;
20             }
21             
22             while(arr[r] > pivot) { //从右边找到一个小于pivot的值
23                 r --;
24             }
25             
26             //如果l == r说明此时pivot已经待到了最终排好序的正确位置
27             if(l == r) {
28                 break;
29             }
30             
31             //交换
32             tmp = arr[l];
33             arr[l] = arr[r];
34             arr[r] = tmp;
35             
36             //左边已经排好序了
37             if (arr[l] == pivot) {
38                 r --;
39             }
40             //右边已经排好序了
41             if (arr[r] == pivot) {
42                 l ++;
43             }
44         }
45         
46         //防止栈溢出
47         if (l == r) {
48             l ++;
49             r --;
50         }
51         //向左递归
52         if (left < r) {
53             quickSort(arr, left, r);
54         }
55         //向右递归
56         if(right > l) {
57             quickSort(arr, l, right);
58         }
59     }    
60 
61 }

运行结果：

 顾名思义：快速排序是一种速度很快的排序方法，不过从程序中的递归可以看出：快排是一种以空间换取时间的排序方法，因为它使用了递归，众所周知的是递归是比较耗费栈空间的，每一次递归都是一次压栈。