1 package sorts; 2  3 import java.util.Arrays; 4 import java.util.Random; 5  6 public class QuickSort { 7     public static <T extends Comparable<T>>  8     void sort(T[] a, int low, int high) { 9         if (low < high) {10             int mid = partition(a, low, high);11             sort(a, low, mid - 1);12             sort(a, mid + 1, high);13         }14     }15     private static <T extends Comparable<T>> 16     int partition(T[] a, int low, int high) {17         median_of_three(a, low, high);18         T pivot = a[low]; // low is the median of three, as the pivot19         int i = low - 1;20         for (int j = low + 1; j <= high; ++j) {21             if (a[j].compareTo(pivot)<0) {22                 ++i;23                 swap(a, i, j);24             }25         }26         a[i+1] = pivot;27         return i+1;28     }29     // set the median of low, high, mid to low30     private static <T extends Comparable<T>> 31     void median_of_three(T[] a, int low, int high) {32         int mid = low + ((high-low)>>1); // (high - low) / 233         if (a[mid].compareTo(a[high])>0) {34             swap(a, mid, high);35         }36         if (a[low].compareTo(a[high])>0) {37             swap(a, low, high);38         }39         if (a[mid].compareTo(a[low])>0) {40             swap(a, mid, low);41         }42         // a[mid] <= a[low] <= a[high], low is the median43     }44     private static <T> void swap(T[] a, int index1, int index2) {45         T tmp = a[index1];46         a[index1] = a[index2];47         a[index2] = tmp;48     }49     50     // test51     public static void main(String[] args) {52         Random random = new Random();53         int num = 10;54         int bound = 100;55         Integer[] a = new Integer[num];56         for (int i = 0; i < num; i++) {57             a[i] = random.nextInt(bound);58         }59         QuickSort.sort(a, 0, a.length-1);60         System.out.println(Arrays.toString(a));61     }62 }