快速排序

算法2.5 快速排序

  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.StdOut;
  3. import edu.princeton.cs.algs4.StdRandom;
  5. public class Quick {
  6.     public static void sort(Comparable[] a){
  7.         StdRandom.shuffle(a);
  8.         sort(a,0,a.length-1);
  9.     }
  11.     private static void sort(Comparable[] a, int lo, int hi){
  12.         //if(lo >= hi + M) {Insertion(a,lo,hi); return; }//改进,小数组采用插入排序
  13.         if(lo >= hi) return;
  14.         int j = partition(a,lo,hi);
  15.         sort(a,lo,j-1);
  16.         sort(a,j+1,hi);
  17.     }
  19.     private static int partition(Comparable[] a, int lo, int hi){
  20.         int i = lo;
  21.         int j = hi + 1;
  22.         Comparable v = a[lo];//默认a[lo]为切分元素
  24.         while (true){
  25.             while (less(a[++i],v)) if(i == hi) break;//从左到右直到有大于切分元素的元素
  26.             while (less(v,a[--j])) if(j == lo) break;//从右到左直到有小于切分元素的元素
  27.             if (i >= j) break;
  28.             exch(a,i,j);//只要i，j未相遇，则交换两处元素
  29.         }
  30.         exch(a,lo,j);//最终把切分元素与左子数组最后元素交换位置
  31.         return j;
  33.     }
  35.     //...
  36. }

要点

  1. 快速排序是一种分治的排序算法,和归并互补:归并把数组分成两个子数组分别排序,然后归并两个有序的子数组使整体有序;快排是当两个子数组都有序时整个数组自然也有序了.归并时,递归sort发生在归并merge之前,快排中,归并sort发生在分切partition后
  2. 切分的一般策略:随意取a[lo]作为切分元素,然后从左到右直到找到>=它的元素,再从右到左找到<=它的元素,然后在两个指针未相遇时就可以交换两元素,指针相遇时,只需把a[lo]和左子数组最右侧元素交换,最终切分元素左侧的元素都比它小,右侧元素都比它大,再各自排序.
  3. sort中有StdRandom.shuffle方法,为了保证元素的随机性,避免切分时出现极大子数组和极小子数组的不均衡情况.
  4. 对于有大量重复值的情况,一般的快排不可避免会发生等值元素继续交换位置的现象.

特点

  1. 快排切分的内循环会用一个递增的索引(i++,j++)将数组元素和一个定值(v)比较,没有移动数据,而归并和希尔一般比快排慢,在于它们在内循环中移动数据

算法改进

  1. 小数组使用插入排序
  1. if(lo >= hi + M) {Insertion(a,lo,hi); return; }//改进,小数组采用插入排序
  1. 取消while的边界测试—三取样切分:见Ex2_3_18
  2. 应对大量重复元素—三向切分:如下

三向切分

  1. public class Quick3Way {
  2.     public static void sort(Comparable[] a){
  3.         StdRandom.shuffle(a);
  4.         sort(a,0,a.length-1);
  5.     }
  7.     private static void sort(Comparable[] a, int lo, int hi){
  8.         if(lo >= hi) return;
  9.         int lt = lo, i = lo+1, gt = hi;
  10.         Comparable v = a[lo];
  12.         while (i <= gt){
  13.             int cmp = a[i].compareTo(v);
  14.             if(cmp < 0) exch(a,lt++,i++);
  15.             else if(cmp > 0) exch(a,i,gt--);
  16.             else i++;
  17.         }
  18.         sort(a,lo,lt-1);//[lo,lt-1]间元素都小于v
  19.         sort(a,gt+1,hi);//[gt+1,hi]间元素都大于v
  20.     }
  22.     //...
  23. }

分析

三项切分快速排序:从左到右遍历数组,指针lt使得a[lo…lt-1]中元素v,a[lt,gt]元素都==v,这样只需要为a[lo…lt-1],a[gt+1…hi]两个子数组排序,忽略重复部分

  1. a[i] < v,交换a[lt]和a[i],lt++,i++;
  2. a[i] > v,交换a[gt]和a[i],gt—;
  3. a[i] == v, i++;

Review

  • 一般快速排序：
  1. partition()中i从lo开始,j从hi+1开始,巧妙配合while中的++i和—j,保证从lo+1处开始扫描完全
  2. exch(a,lo,j)最后是j不是i,因为++i和—j的缘故,循环最后一步,i指向右子数组左侧,j指向左子数组右侧
  3. int j = partition(a,lo,hi);j即是分切元素,已经确定好了位置,无需排序,所以sort(a,lo,j-1);sort(a,j+1,hi);
  • 三项切分快排：
  1. 无partition()，切分直接在sort()中完成;
  2. 三个变量,lt是”三项”的中间项起点,gt为中间项终点;
  1. while (i <= gt){
  2.             int cmp = a[i].compareTo(v);
  3.             if(cmp < 0) exch(a,lt++,i++);
  4.             else if(cmp > 0) exch(a,i,gt--);
  5.             else i++;
  6.         }
  1. i与否问题:
    while中,因为每次i都会变化,cmp需要每次重新计算.
    (cmp<0)时,lt且i++,若此处i不变,第一次交换后a[i]=a[lo],cmp=0,依旧i++,所以exch()中直接执行;(cmp>0)时,gt—,i不变,因为第一次交换后,需再次比较换下来的a[gt]否小于v;
  2. while()循环条件之所以为(i<=gt):
    原因与第三点最后相同:
    若换下一个a[gt]后gt—,i == gt,即此时到了中项和右项交界,必须再判断一次换下的元素是否还小于等于v,甚至大于v,当小于等于v后i++,i > gt,跳出循环,当大于v后gt—, gt < i,跳出循环.