这是C.a.R.霍尔快速排序算法的通用版本。
public class Main{/** nowjava - 时代Java 提 供 **/ /** * This is a generic version of C.A.R Hoare's Quick Sort * algorithm. This will handle arrays that are already * sorted, and arrays with duplicate keys.<BR> * <p/> * If you think of a one dimensional array as going from * the lowest index on the left to the highest index on the right * then the parameters to this function are lowest index or * left and highest index or right. The first time you call * this function it will be with the parameters 0, a.length - 1. * (taken out of a code by James Gosling and Kevin A. Smith provided * with Sun's JDK 1.1.7) * * @param a an integer array * @param lo0 left boundary of array partition (inclusive). * @param hi0 right boundary of array partition (inclusive). */ private static void quickSortMaxToMin(int a[], int lo0, int hi0) { int lo = lo0; int hi = hi0; int mid; if (hi0 > lo0) { /* Arbitrarily establishing partition element as the midpoint of * the array. */ mid = a[(int) Math.round((lo0 + hi0) / 2.0)]; // loop through the array until indices cross//NowJava.com - 时 代 Java while (lo <= hi) { /* find the first element that is greater than or equal to * the partition element starting from the left Index. */ while ((lo < hi0) && (a[lo] > mid)) ++lo; /* find an element that is smaller than or equal to * the partition element starting from the right Index. */ while ((hi > lo0) && (a[hi] < mid)) --hi; // if the indexes have not crossed, swap if (lo <= hi) { swap(a, lo, hi); ++lo; --hi; } } /* If the right index has not reached the left side of array * must now sort the left partition. */ if (lo0 < hi) quickSortMaxToMin(a, lo0, hi); /* If the left index has not reached the right side of array * must now sort the right partition. */ if (lo < hi0) quickSortMaxToMin(a, lo, hi0); } } /** * This is a generic version of C.A.R Hoare's Quick Sort * algorithm. This will handle arrays that are already * sorted, and arrays with duplicate keys.<BR> * <p/> * If you think of a one dimensional array as going from * the lowest index on the left to the highest index on the right * then the parameters to this function are lowest index or * left and highest index or right. The first time you call * this function it will be with the parameters 0, a.length - 1. * (taken out of a code by James Gosling and Kevin A. Smith provided * with Sun's JDK 1.1.7) * * @param a a double array * @param lo0 left boundary of array partition (inclusive). * @param hi0 right boundary of array partition (inclusive). */ private static void quickSortMaxToMin(double a[], int lo0, int hi0) { int lo = lo0; int hi = hi0; double mid; if (hi0 > lo0) { /* Arbitrarily establishing partition element as the midpoint of * the array. */ mid = a[(int) Math.round((lo0 + hi0) / 2.0)]; // loop through the array until indices cross while (lo <= hi) { /* find the first element that is greater than or equal to * the partition element starting from the left Index. */ while ((lo < hi0) && (a[lo] > mid)) ++lo; /* find an element that is smaller than or equal to * the partition element starting from the right Index. */ while ((hi > lo0) && (a[hi] < mid)) --hi; // if the indexes have not crossed, swap if (lo <= hi) { swap(a, lo, hi); ++lo; --hi; } } /* If the right index has not reached the left side of array * must now sort the left partition. */ if (lo0 < hi) quickSortMaxToMin(a, lo0, hi); /* If the left index has not reached the right side of array * must now sort the right partition. */ if (lo < hi0) quickSortMaxToMin(a, lo, hi0);