参考资料：

• 算法导论

代码：

QuickSort.java

1 package algorithms; 2  3 import java.util.Arrays; 4 import java.util.Random; 5  6 import sorts.InsertionSort; 7  8 public class QuickSort { 9     10     private static final int SMALL_ARRAY_SIZE = 5;11     12     /**13      * sort the array14      * @param array the array to be sorted15      * @param low the lower bound (inclusive)16      * @param high the upper bound (exclusive)17      * */18     public static 
     
      >19     void sort(T[] array, int low, int high) {20         --high; // right the upper bound (exclusive)21         _sort(array, low, high);22     }23     private static 
      
       > void 24     _sort(T[] array, int low, int high) {25         if (high - low + 1 <= SMALL_ARRAY_SIZE) {26             InsertionSort.sort(array, low, high+1); 27         } else {28             int pivotIndex = medianOf3(array, low, high);29             int partition = Partition.doPartition(array, low, high+1, pivotIndex);30             _sort(array, low, partition-1);31             _sort(array, partition+1, high);32         }33     }34     // medianOf3() requires the array's length to be at least 435     private static 
       
        > int medianOf3(T[] array, int low, int high) {36         int middle = (low + high) / 2;37         if (array[low].compareTo(array[middle]) > 0) {38             swap(array, low, middle);39         }40         if (array[low].compareTo(array[high]) > 0) {41             swap(array, low, high);42         }43         if (array[middle].compareTo(array[high]) > 0) {44             swap(array, middle, high);45         }46         swap(array, middle, high-1);47         return high-1;48     }49     50     private static 
        
          void swap(T[] array, int index1, int index2) {51         T temp = array[index1];52         array[index1] = array[index2];53         array[index2] = temp;54     }55     56     // test57     public static void main(String[] args) {58         Random random = new Random();59         int num = 10;60         Integer[] a = new Integer[num];61         for (int i = 0; i < num; i++) {62             a[i] = random.nextInt(100);63         }64         System.out.println(Arrays.toString(a));65         QuickSort.sort(a, 0, a.length);66         System.out.println(Arrays.toString(a));67     }68     69 }
        
       
      
     

Partition.java

1 package algorithms; 2  3 public class Partition { 4      5     /** 6      *  7      * Partition the array into 2 parts, the index range of the left part is [left, i-1], the index range of 8      * the right part is [i, right], such that all elements smaller  9      * than the pivot are in the left part and all elements no smaller than the pivot10      * are in the right part.11      * @param left left bound (inclusive)12      * @param right right bound (exclusive)13      * @return the index of the left-most element in the right part, that is, i.14      * */15     public static 
     
      > int doPartition(T[] a, int left, int right, int pivotIndex) {16         --right;17         T pivot = a[pivotIndex];18         swap(a, right, pivotIndex); // set the pivot to the rightmost position19         int i = left - 1;20         for (int j = left; j <= right - 1; ++j) {21             if (a[j].compareTo(pivot)<=0) {22                 ++i;23                 swap(a, i, j);24             }25         }26         swap(a, i+1, right);27         return i+1;28     }29     30     private static 
      
        void swap(T[] array, int index1, int index2) {31         T temp = array[index1];32         array[index1] = array[index2];33         array[index2] = temp;34     }35 36 }