public class QuickSort { private static Comparable median3(Comparable[] data, int left, int right){ int center = (left + right) / 2; if(data[center].compareTo(data[left]) < 0) swapReferences(data, left ,center); if(data[right].compareTo(data[left]) < 0) swapReferences(data, left, right); if(data[right].compareTo(data[center]) < 0) swapReferences(data, center, right); swapReferences(data, center, right - 1); return data[right - 1]; } private static void swapReferences(Comparable[] data, int src, int des){ Comparable tmp; tmp = data[des]; data[des] = data[src]; data[src] = tmp; } private static void quicksort(Comparable[] data, int left, int right){ if(left + CUTOFF <= right){ Comparable pivot = median3(data, left, right); int i = left,j = right - 1; for(;;){ while(data[++i].compareTo(pivot) < 0){} while(data[--j].compareTo(pivot) > 0){} if(i < j) swapReferences(data, i, j); else break; } swapReferences(data, i, right - 1); quicksort(data, left, i - 1); quicksort(data,i + 1, right); } else insertionSort(data, left, right); } private static void insertionSort(Comparable[] data, int left, int right){ int j; for(int p = left; p <= right; p++){ Comparable tmp = data[p]; for(j = p; j > left && tmp.compareTo(data[j-1]) < 0; j--) data[j] = data[j-1]; data[j] = tmp; } } public static void quickSort(Comparable[] data){ quicksort(data, 0, data.length - 1); } public static void main(String[] args){ Comparable[] a = new Comparable[50]; for(int i = 0 ; i < a.length; i++) a[i] = (int)(Math.random() * 1000); for(int i = 0; i < a.length; i++) System.out.print(a[i] + " , "); System.out.println("After: "); quickSort(a); for(int i = 0; i < a.length; i++) System.out.print(a[i] + ", "); } private final static int CUTOFF = 10;}
相关资源：敏捷开发V1.0.pptx
