快速排序是目前使用最广泛的排序, 同时也是目前最快的排序,它也体现了分治的思想:将数组分成两部分, 并分别独立地进行排序. 和归并排序不同的是, 归并排序是将两个有序的数组合并为一个有序的大数组, 而快排则是当小数组有序时, 大数组就自然有序了

快速排序是用一个数v将数组切分, v左边的数全都小于v, v右边的数全都大于v, 在将小数组继续切分, 直到不能再分为止, 这样数组就有序了:

我们先写排序主体:

1     public static void sort(int[] a, int lo, int hi) {2         if(hi <= lo) return;3         int j =  partition(a, lo, hi);4         sort(a, lo, j-1);5         sort(a, j+1, hi);6     }

 

然后写切分函数partition():

1     private static int partition(int[] a, int lo, int hi) { //普通的快排 2         int i = lo, j = hi + 1; 3         int v = a[lo]; 4         while(true) { 5             while(a[++i] < v)  6                 if(i == hi) break; 7             while(a[--j] > v)  8                 if(j == lo) break; 9             if(i >= j) break;10             int tmp = a[i];11             a[i] = a[j];12             a[j] = tmp;13         }14         int tmp = a[lo];15         a[lo] = a[j];16         a[j] = tmp;17         return j;18     }

当然, 这不是最优的代码, 还有更优的解决方案, 那就是将数组切分为三部分, 大于v, 等于v和小于v的三部分:

1 　　private static void quick3way(int[] a, int lo, int hi) { //三项切分的快速排序 2         if(hi <= lo) 3             return; 4         int lt = lo, i = lo+1, gt = hi; 5         int v = a[lo]; 6         while(i <= gt) { 7             if(a[i] < v) { 8                 int tmp = a[i]; 9                 a[i++] = a[lt];10                 a[lt++] = tmp;11             } else if(a[i] > v) {12                 int tmp = a[i]; 13                 a[i] = a[gt];14                 a[gt--] = tmp;15             } else i++;16         }17         quick3way(a, lo, lt-1);18         quick3way(a, gt+1, hi);19     }

可以预见, 在含有大量相同元素的情况下, 三项切分对快排的性能会有很大提升

普通的快速排序时间复杂度为O(nlogn), 三项快排的时间复杂度在O(n)和O(nlogn)之间, 但他们的空间复杂度都为O(lgn), 他们都频繁的使用了递归调用