常用算法之排序(Java)

@SuppressWarnings("unchecked")
public class Quick
{
// This class should not be instantiated.
private Quick() { } /**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
// 打乱数组，保证随机性。这对预测算法的运行时间很重要
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
} // quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
} // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) { // find item on lo to swap
while (less(a[++i], v)) {
if (i == hi) break;
} // find item on hi to swap
while (less(v, a[--j])) {
if (j == lo) break; // redundant since a[lo] acts as sentinel
} // check if pointers cross
if (i >= j) break; exch(a, i, j);
} // put partitioning item v at a[j]
exch(a, lo, j); // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
} // less()、show()、exch()和main()方法见Selection.java
}

import java.util.Random;
public final class StdRandom { private static Random random; // pseudo-random number generator
private static long seed; // pseudo-random number generator seed // static initializer
static {
// this is how the seed was set in Java 1.4
seed = System.currentTimeMillis();
random = new Random(seed);
} // don't instantiate
private StdRandom() { } /**
* Returns a random real number uniformly in [0, 1).
*
* @return a random real number uniformly in [0, 1)
*/
public static double uniform() {
return random.nextDouble();
} /**
* Returns a random integer uniformly in [0, n).
*
* @param n number of possible integers
* @return a random integer uniformly between 0 (inclusive) and {@code n} (exclusive)
* @throws IllegalArgumentException if {@code n <= 0}
*/
public static int uniform(int n) {
if (n <= 0) throw new IllegalArgumentException("argument must be positive: " + n);
return random.nextInt(n);
} /**
* Returns a random long integer uniformly in [0, n).
*
* @param n number of possible {@code long} integers
* @return a random long integer uniformly between 0 (inclusive) and {@code n} (exclusive)
* @throws IllegalArgumentException if {@code n <= 0}
*/
public static long uniform(long n) {
if (n <= 0L) throw new IllegalArgumentException("argument must be positive: " + n);
long r = random.nextLong();
long m = n - 1; // power of two
if ((n & m) == 0L) {
return r & m;
} // reject over-represented candidates
long u = r >>> 1;
while (u + m - (r = u % n) < 0L) {
u = random.nextLong() >>> 1;
}
return r;
} /**
* Returns a random integer uniformly in [a, b).
*
* @param a the left endpoint
* @param b the right endpoint
* @return a random integer uniformly in [a, b)
* @throws IllegalArgumentException if {@code b <= a}
* @throws IllegalArgumentException if {@code b - a >= Integer.MAX_VALUE}
*/
public static int uniform(int a, int b) {
if ((b <= a) || ((long) b - a >= Integer.MAX_VALUE)) {
throw new IllegalArgumentException("invalid range: [" + a + ", " + b + ")");
}
return a + uniform(b - a);
} /**
* Returns a random real number uniformly in [a, b).
*
* @param a the left endpoint
* @param b the right endpoint
* @return a random real number uniformly in [a, b)
* @throws IllegalArgumentException unless {@code a < b}
*/
public static double uniform(double a, double b) {
if (!(a < b)) {
throw new IllegalArgumentException("invalid range: [" + a + ", " + b + ")");
}
return a + uniform() * (b-a);
} /**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(Object[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n-i); // between i and n-1
Object temp = a[i];
a[i] = a[r];
a[r] = temp;
}
} /**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(double[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n-i); // between i and n-1
double temp = a[i];
a[i] = a[r];
a[r] = temp;
}
} /**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(int[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n-i); // between i and n-1
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
} /**
* Rearranges the elements of the specified array in uniformly random order.
*
* @param a the array to shuffle
* @throws IllegalArgumentException if {@code a} is {@code null}
*/
public static void shuffle(char[] a) {
validateNotNull(a);
int n = a.length;
for (int i = 0; i < n; i++) {
int r = i + uniform(n-i); // between i and n-1
char temp = a[i];
a[i] = a[r];
a[r] = temp;
}
} // throw an IllegalArgumentException if x is null
// (x can be of type Object[], double[], int[], ...)
private static void validateNotNull(Object x) {
if (x == null) {
throw new IllegalArgumentException("argument is null");
}
} /**
* Unit tests the methods in this class.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String[] a = "A B C D E F G".split(" ");
StdRandom.shuffle(a);
for (String s : a){
System.out.print(" "+s);
}
System.out.println("");
}}