-6

我有来自http://algs4.cs.princeton.edu的以下代码，它在 0 到 1 之间的一组随机数上实现快速三向分区的快速排序，但是我想在以下集合上实现它

  1. 有序列表
  2. 倒序列表
  3. 一个包含相同值的列表
  4. 25% 的列表已排序

我如何创建它们以便将它们提供给方法？

这是我当前main()调用测试的方法：

public static void main(String[] args) {

    // generate array of N random reals between 0 and 1
    int N = Integer.parseInt(args[0]);
    Double[] a = new Double[N];
    for (int i = 0; i < N; i++) {
        a[i] = Math.random();
    }

    // sort the array
    sort(a);

    // display results
    for (int i = 0; i < N; i++) {
        System.out.println(a[i]);
    }
    System.out.println("isSorted = " + isSorted(a));

}

其余代码（不太相关）：

public class QuickX {
private static final int CUTOFF = 8;  // cutoff to insertion sort, must be >= 1

public static void sort(Comparable[] a) {
    sort(a, 0, a.length - 1);
}

private static void sort(Comparable[] a, int lo, int hi) { 
    int N = hi - lo + 1;

    // cutoff to insertion sort
    if (N <= CUTOFF) {
        insertionSort(a, lo, hi);
        return;
    }

    // use median-of-3 as partitioning element
    else if (N <= 40) {
        int m = median3(a, lo, lo + N/2, hi);
        exch(a, m, lo);
    }

    // use Tukey ninther as partitioning element
    else  {
        int eps = N/8;
        int mid = lo + N/2;
        int m1 = median3(a, lo, lo + eps, lo + eps + eps);
        int m2 = median3(a, mid - eps, mid, mid + eps);
        int m3 = median3(a, hi - eps - eps, hi - eps, hi); 
        int ninther = median3(a, m1, m2, m3);
        exch(a, ninther, lo);
    }

    // Bentley-McIlroy 3-way partitioning
    int i = lo, j = hi+1;
    int p = lo, q = hi+1;
    while (true) {
        Comparable v = a[lo];
        while (less(a[++i], v))
            if (i == hi) break;
        while (less(v, a[--j]))
            if (j == lo) break;
        if (i >= j) break;
        exch(a, i, j);
        if (eq(a[i], v)) exch(a, ++p, i);
        if (eq(a[j], v)) exch(a, --q, j);
    }
    exch(a, lo, j);

    i = j + 1;
    j = j - 1;
    for (int k = lo+1; k <= p; k++) exch(a, k, j--);
    for (int k = hi  ; k >= q; k--) exch(a, k, i++);

    sort(a, lo, j);
    sort(a, i, hi);
}


// sort from a[lo] to a[hi] using insertion sort
private static void insertionSort(Comparable[] a, int lo, int hi) {
    for (int i = lo; i <= hi; i++)
        for (int j = i; j > lo && less(a[j], a[j-1]); j--)
            exch(a, j, j-1);
}


// return the index of the median element among a[i], a[j], and a[k]
private static int median3(Comparable[] a, int i, int j, int k) {
    return (less(a[i], a[j]) ?
           (less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
           (less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}

// is v < w ?
private static boolean less(Comparable v, Comparable w) {
    return (v.compareTo(w) < 0);
}

// does v == w ?
private static boolean eq(Comparable v, Comparable w) {
    return (v.compareTo(w) == 0);
}

// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}


 private static boolean isSorted(Comparable[] a) {
    for (int i = 1; i < a.length; i++)
        if (less(a[i], a[i-1])) return false;
    return true;
}



// test client
public static void main(String[] args) {

    // generate array of N random reals between 0 and 1
    int N = Integer.parseInt(args[0]);
    Double[] a = new Double[N];
    for (int i = 0; i < N; i++) {
        a[i] = Math.random();
    }

    // sort the array
    sort(a);

    // display results
    for (int i = 0; i < N; i++) {
        System.out.println(a[i]);
    }
    System.out.println("isSorted = " + isSorted(a));

}

}
4

1 回答 1

1

您可以Arrays.sort()在输入数组之前对其进行排序，以下每一项都描述了如何实现您要求的一件事 - 在调用之前尝试在数组上执行每一项（一次一个）sort(a)

要按升序对数组进行排序：

Arrays.sort(a);

要按降序对数组进行排序：

Arrays.sort(a,Collections.reverseOrder());

为数组中的每个元素设置常量值：

for (int i = 0; i < a.length; i++) a[i] = 0.25;

对列表进行部分排序（25% 已排序）：

Arrays.sort(a,0,a.length/4);

奖励：打印数组（通常用于调试目的）：

System.out.println(Arrays.toString(a));
于 2012-12-09T00:31:59.100 回答