快速排序

参考资料：

代码：

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 array
14      * @param array the array to be sorted
15      * @param low the lower bound (inclusive)
16      * @param high the upper bound (exclusive)
17      * */
18     public static <T extends Comparable<T>>
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 <T extends Comparable<T>> 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 4
35     private static <T extends Comparable<T>> 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 <T> 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     // test
57     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 pivot
10      * 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 <T extends Comparable<T>> 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 position
19         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 <T> 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 }