使用指定的比较器对指定数组执行优化的快速排序。
//package com.nowjava; import java.util.*; /** N o w J a v a . c o m 提供 **/ public class Main { /** * Performs an optimized quicksort of the specified array, using the specified comparator. * This method used the same algorithm as used by java.lang.Arrays for sorting arrays of * primitive types. The java.lang.Arrays sort methods for objects, use a merge sort, which * is not quite as fast as quicksort. Note that quicksort is NOT a stable sort, but merge sort is. * * @param a * @param c */ public static <T> void quickSort(T[] a, Comparator<? super T> c) { quickSort(a, 0, a.length, c); } /** * Performs an optimized quicksort of the specified array, using the natural ordering of the object. * (They should implement Comparable in order for this method to have any effect.) * This method used the same algorithm as used by java.lang.Arrays for sorting arrays of * primitive types. The java.lang.Arrays sort methods for objects, use a merge sort, which * is not quite as fast as quicksort. Note that quicksort is NOT a stable sort, but merge sort is. * * @param a */ public static <T> void quickSort(T[] a) { quickSort(a, 0, a.length, null);/**时 代 J a v a - nowjava.com**/ } public static <T> void quickSort(T[] arr, int offset, int len, Comparator<? super T> cmp) { final int limit = offset + len; // Use an insertion sort for really small arrays. if (len < 7) { for (int i = offset + 1; i < limit; i++) { T v = arr[i]; int j = i; while (j > offset && compare(arr[j - 1], v, cmp) > 0) { arr[j] = arr[j - 1]; j--; } arr[j] = v; } // Done! return; } // Select a partition element index, m int m = offset + (len >> 1); int left = offset; int right = limit - 1; // For arrays > 40, use the pseudomedian of 9 // if (len > 40) { int eighthLen = len / 8; // Index of median value of the 3 on the left. left = medianOf3(arr, left, left + eighthLen, left + 2 * eighthLen, cmp); // In the middle m = medianOf3(arr, m - eighthLen, m, m + eighthLen, cmp); // On the right right = medianOf3(arr, right - 2 * eighthLen, right - eighthLen, right, cmp); } // Convert to index of the median of the 3. m = medianOf3(arr, left, m, right, cmp); T partitionValue = arr[m]; int a = offset; int b = offset; int c = limit - 1; int d = c; while (true) { int cmpValue = b <= c ? compare(arr[b], partitionValue, cmp) : 0; while (b <= c && cmpValue <= 0) { if (cmpValue == 0) { swap(arr, a++, b); } b++; if (b <= c) { cmpValue = compare(arr[b], partitionValue, cmp); } } cmpValue = c >= b ? compare(arr[c], partitionValue, cmp) : 0; while (c >= b && cmpValue >= 0) { if (cmpValue == 0) { swap(arr, c, d--); } c--; if (c >= b) { cmpValue = compare(arr[c], partitionValue, cmp); } } if (b > c) { break; } swap(arr, b++, c--); } int s = Math.min(a - offset, b - a); vecSwap(arr, offset, b - s, s); s = Math.min(d - c, limit - d - 1); vecSwap(arr, b, limit - s, s); s = b - a; if (s > 1) { quickSort(arr, offset, s, cmp); } s = d - c; if (s > 1) { quickSort(arr, limit - s, s, cmp); } } @SuppressWarnings({ "unchecked", "rawtypes" }) private static <T> int compare(T v1, T v2, Comparator<? super T> c) { if (c != null) { return c.compare(v1, v2); } if (v1 instanceof Comparable) { return ((Comparable) v1).compareTo(v2); } return 0; } private static int compare(double d1, double d2, int n1, int n2, boolean ascending) { int rtn; if (Double.doubleToLongBits(d1) == Double.doubleToLongBits(d2)) { rtn = 0; } else { // NaNs are considered to be > than anything else. boolean d1NaN = Double.isNaN(d1); boolean d2NaN = Double.isNaN(d2); if (d1NaN && !d2NaN) { rtn = 1; } else if (d2NaN && !d1NaN) { rtn = -1; } else { // Neither can possibly be NaN. rtn = d1 < d2 ? -1 : (d1 > d2 ? 1 : 0); } } if (rtn == 0) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } if (!ascending) rtn = -rtn; return rtn; } private static int compare(float d1, float d2, int n1, int n2, boolean ascending) { int rtn; if (Double.doubleToLongBits(d1) == Double.doubleToLongBits(d2)) { rtn = 0; } else { // NaNs are considered to be > than anything else. boolean d1NaN = Double.isNaN(d1); boolean d2NaN = Double.isNaN(d2); if (d1NaN && !d2NaN) { rtn = 1; } else if (d2NaN && !d1NaN) { rtn = -1; } else { // Neither can possibly be NaN. rtn = d1 < d2 ? -1 : (d1 > d2 ? 1 : 0); } } if (rtn == 0) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } if (!ascending) rtn = -rtn; return rtn; } private static int compare(int d1, int d2, int n1, int n2, boolean ascending) { int rtn; if (d1 == d2) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } else { rtn = d1 < d2 ? -1 : (d1 > d2 ? 1 : 0); } if (!ascending) rtn = -rtn; return rtn; } private static int compare(int d1, int d2, double n1, double n2, boolean ascending) { int rtn; if (d1 == d2) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } else { rtn = d1 < d2 ? -1 : (d1 > d2 ? 1 : 0); } if (!ascending) rtn = -rtn; return rtn; } private static int compare(int n1, int n2, boolean ascending) { int rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); if (!ascending) rtn = -rtn; return rtn; } private static <T extends Comparable<? super T>> int compare(T c1, T c2, int n1, int n2, boolean ascending) { int rtn = c1.compareTo((T) c2); if (rtn == 0) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } if (!ascending) rtn = -rtn; return rtn; } private static <T> int compare(T c1, T c2, Comparator<? super T> c, int n1, int n2, boolean ascending) { int rtn = c.compare(c1, c2); if (rtn == 0) { rtn = (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0)); } if (!ascending) rtn = -rtn; return rtn; } private static int compare(int i, int j, int maxDepth, int[]... arrays) { for (int d = 0; d < maxDepth; d++) { int[] array = arrays[d]; if (array[i] < array[j]) return -1; if (array[i] > array[i]) return +1; } return 0; } private static int compare(int i, int maxDepth, int[] colBuffer, int[]... arrays) { for (int d = 0; d < maxDepth; d++) { int[] array = arrays[d]; int bv = colBuffer[d]; int v = array[i]; if (bv > v) return -1; if (bv < v) return +1; } return 0; } public static int medianOf3(int[] values, int a, int b, int c) { int va = values[a]; int vb = values[b]; int vc = values[c]; return va < vb ? (vb < vc ? b : (vc < va ? a : c)) : (va < vc ? a : (vc < vb ? b : c)); } /** * Given three indexes into the specified array, this method returns the index of the * middle element as determined by the supplied comparator. If the comparator is null, * the middle index is determined by the <tt>compareTo</tt> methods of the objects, assuming * they implement comparable. * * @param a * @param x * @param y * @param z * @param c * @return */ public static <T> int medianOf3(T[] a, int x, int y, int z, Comparator<? super T> c) { if (compare(a[x], a[y], c) < 0) { // x < y if (compare(a[y], a[z], c) < 0) { // y < z, so x < y < z // y is the middle return y; } // x < y, but y >= z if (compare(a[x], a[z], c) < 0) { // x < z // x < z <= y return z; } // x >= z // Has to be x. return x; } // x >= y if (compare(a[y], a[z], c) > 1) { // y > z return y; } // y <= z if (compare(a[x], a[z], c) > 0) { // x > z return z; } return x; } private static <T> void swap(T[] arr, int i, int j) { T tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } /** * Swaps x[a] with x[b]. */ private static void swap(int x[], int a, int b) { int t = x[a]; x[a] = x[b]; x[b] = t; } private static void swap(double x[], int[] n, int a, int b) { double t = x[a]; x[a] = x[b]; x[b] = t; int tn = n[a]; n[a] = n[b]; n[b] = tn; } private static void swap(float x[], int[] n, int a, int b) { float t = x[a]; x[a] = x[b]; x[b] = t; int tn = n[a]; n[a] = n[b]; n[b] = tn; } private static void swap(int x[], int[] n, int a, int b) { int t = x[a]; x[a] = x[b]; x[b] = t; t = n[a]; n[a] = n[b]; n[b] = t; } private static <E> void swap(int[] x, E[] n,