Ex2_3_18三取样切分

  1. import edu.princeton.cs.algs4.In;
  2. import edu.princeton.cs.algs4.StdOut;
  3. import edu.princeton.cs.algs4.StdRandom;
  5. public class Ex2_3_18 {
  6.     private 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 + 5) { Insertion(a,lo,hi); return;}//以5为阈值进行插入排序
  13.         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;
  23.         while (true){
  24.             while (less(a[i++],a[midNum(a,lo,hi)]));
  25.             while (less(a[lo],a[j--]));
  26.             if(i >= j) break;
  27.             exch(a,i,j);
  28.         }
  29.         exch(a,lo,j);
  30.         return j;
  31.     }
  33.     //三取样,以中位数为切分元素,并把切分元素移动到末端作为标记
  34.     private static int midNum(Comparable[] a, int lo, int hi){
  35.         if( (a[lo].compareTo(a[lo+1]) * a[lo].compareTo(a[lo+2])) < 0){
  36.             exch(a,lo,a.length-1);
  37.             return lo;
  38.         }
  39.         else if( (a[lo+1].compareTo(a[lo]) * a[lo+1].compareTo(a[lo+2])) < 0){
  40.             exch(a,lo+1,a.length-1);
  41.             return lo+1;
  42.         }
  43.         else{
  44.             exch(a,lo+2,a.length-1);
  45.             return lo+2;
  46.         }
  48.     }
  50.     private static void Insertion(Comparable[] a, int lo, int hi){
  51.         for(int i = lo+1; i <= hi; i++){
  52.             for(int j = i; j>lo && less(a[j],a[j-1]); j--){
  53.                 exch(a,j,j-1);
  54.             }
  55.         }
  56.     }
  58.     private static boolean less(Comparable v, Comparable w){
  59.         return v.compareTo(w) < 0;
  60.     }//比较v是否小于w
  62.     private static void exch(Comparable[] a, int i, int j){
  63.         Comparable t = a[i];
  64.         a[i] = a[j];
  65.         a[j] = t;
  66.     }//元素交换
  68.     private static void show(Comparable[] a){
  69.         for(int i = 0; i < a.length; i++)
  70.             StdOut.print(a[i] + " ");
  71.         StdOut.println();
  72.     }//单行打印
  74.     public static void main(String[] args){
  75.         String[] a = In.readStrings();
  76.         sort(a);
  77.         show(a);
  78.     }
  79. }

要点:

  1. 取样以子数组前三个数的中位值为切分元素: Comparable v = a[midNum(a,lo,hi)];
  2. midNum方法在返回中位元素索引同时,交换其与末尾元素,这样在partition内循环中,右子数组循环 while (less(a[i++],a[midNum(a,lo,hi)]));就无需边界检查,因为最终一定a[hi]==v退出循环;while (less(a[lo],a[j—]));j减为lo时一定a[lo]==v退出循环