快速排序也是一种分治算法。主要思想是选取一个切分点，将大于切分点的元素都放置到数组右侧，小于切分点的元素都放置到数组左侧；然后递归，再对切分点左侧和右侧分别排序。
归并排序时递归在前，归并在后，快速排序是切分在前，排序在后。
快速排序的运行时间在1.39nlogn的某个常数因子范围之内，归并排序也能做到这一点，但是快速排序更快，因为它的移动次数更少。
快速排序的关键点在于切分点的选取，对于正好逆序的情况，它的复杂度达到了n2，而且与归并排序相比不稳定。
为了防止最坏情况的出现，一般在排序前先将元素随机打乱。
1 package 排序; 2 3 import edu.princeton.cs.algs4.In; 4 import edu.princeton.cs.algs4.StdOut; 5 import edu.princeton.cs.algs4.StdRandom; 6 /** 7 * @author evasean www.cnblogs.com/evasean/ 8 */ 9 @SuppressWarnings("rawtypes") 10 public class Quick快速排序 { 11 private static int partition(Comparable[] a, int lo, int hi){ 12 int i = lo; 13 int j = hi+1; 14 Comparable v = a[lo];//切分元素 15 while(true){ 16 while(less(a[++i],v)) 17 if(i==hi) break; 18 while(less(v,a[--j])) 19 if(j==lo) break; 20 if(i>=j) break; 21 exch(a,i,j); 22 } 23 exch(a,lo,j);//此时j<=i，且v > a[j]，将切分元素v放入正确位置 24 return j; 25 } 26 public static void sort(Comparable[] a){ 27 StdRandom.shuffle(a); //消除最坏的情况 28 sort(a,0,a.length-1); 29 } 30 private static void sort(Comparable[] a, int lo, int hi){ 31 if(hi <= lo) return; 32 int j = partition(a,lo,hi); 33 sort(a,lo,j-1); 34 sort(a,j+1,hi); 35 } 36 37 @SuppressWarnings("unchecked") 38 private static boolean less(Comparable v, Comparable w){ 39 return v.compareTo(w) < 0; 40 } 41 private static void exch(Comparable[] a, int i, int j){ 42 Comparable t = a[i]; 43 a[i] = a[j]; 44 a[j] = t; 45 } 46 private static void show(Comparable[] a){ 47 for(int i=0; i<a.length; i++) StdOut.print(a[i] + " "); 48 StdOut.println(); 49 } 50 public static boolean isSorted(Comparable[] a){ 51 for(int i = 1; i < a.length; i++){ 52 if(less(a[i],a[i-1])) return false; 53 } 54 return true; 55 } 56 public static void main(String[] args){ 57 String[] a = new In().readAllStrings(); 58 sort(a); 59 assert isSorted(a); 60 show(a); 61 } 62 }
实际应用中经常会出现大量重复元素的排序情况，而快速排序在面对重复元素时排序复杂度并没有降低。Dijkstra提出的三向切分快速排序方法可以迅速降低这种情况下的复杂度，甚至有可能达到线性级别n，如荷兰国旗问题（见我的另一篇文章）。其基本思想就是选取切分点v，从左到右遍历，维护一个从前往后遍历的位置点lt，使得a[0]~a[lt-1]都小于v，维护一个从前往后遍历的位置点i，使得a[lt]~a[i-1]都等于v，维护一个从后往前的位置点，使得a[i]~a[gt]都大于v。
1 /* 2 * 三向切分的快速排序 3 * a[lo...lt-1]中的元素都小于v 4 * a[gt+1....hi]中的元素都大于v 5 * a[lt...i-1]中的元素都等于v 6 * a[i...gt]中的元素都还未确定,通过下面处理 7 * 1. a[i]小于v，将a[lt]和a[i]交换，将lt和i加1 8 * 2. a[i]大于v，将a[gt]和a[i]交换，将gt减1 9 * 3. a[i]等于v，将i加1 10 * 这些操作都会保证数组元素不变且缩小gt-i的值，这样循环才会结束 11 */ 12 private static void sort3way(Comparable[] a, int lo, int hi){ 13 if(hi <= lo) return; 14 int lt = lo; 15 int i = lo+1; 16 int gt = hi; 17 Comparable v = a[lo]; 18 while(i <= gt){ 19 int cmp = a[i].compareTo(v); 20 if(cmp<0) exch(a,lt++,i++); 21 else if(cmp>0) exch(a,i,gt--); 22 else i++; 23 }//现在a[lo...lt-1] < v=a[lt...gt]<a[gt+1...hi] 24 sort3way(a,lo,lt-1); 25 sort3way(a,gt+1,hi); 26 }
用这里的sort3way方法替代快速排序中的sort(Comparable[] a, int lo, int hi)即可。