- package exercise.chap2.c3.test;
- import java.util.Random;
- import edu.princeton.cs.introcs.StdRandom;
- public class QuickSort3W {
- public static void sort(Comparable[] a) {
- // 先打乱顺序,使得第一个元素不至于太小和太大
- StdRandom.shuffle(a);
- sort(a, 0, a.length - 1);
- }
- private static void sort(Comparable[] a, int lo, int hi) {
- if (hi <= lo)
- return;
- int m = lo, i = lo, n = hi;
- Comparable v = a[lo];
- while (i <= n) {
- if (a[i].compareTo(v) < 0) {
- exch(a, m++, i++);
- } else if (a[i].compareTo(v) > 0) {
- exch(a, i, n--);
- } else
- i++;
- }
- sort(a, lo, n - 1);
- sort(a, m + 1, hi);
- }
- private static boolean less(Comparable u, Comparable v) {
- return u.compareTo(v) < 0;
- }
- private static void exch(Comparable[] a, int i, int j) {
- Comparable temp;
- temp = a[i];
- a[i] = a[j];
- a[j] = temp;
- }
- public static void main(String[] args) {
- int N = 10;
- Comparable[] c = new Comparable[N];
- System.out.println("随机产生" + N + "个数:");
- for (int i = 0; i < N; i++) {
- c[i] = new Random().nextInt(100);
- System.out.print(c[i] + " ");
- }
- System.out.println("\\n----------------------------------------");
- QuickSort3W.sort(c);
- System.out.println("\\n---------------------------------------\\n排序之后:");
- // 输出排序后的数组:
- for (int m = 0; m < c.length; m++)
- System.out.print(c[m] + " ");
- System.out.println();
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/2808201513568.html
来源: http://www.codesnippet.cn/detail/2808201513568.html