4

我试图理解 3 路基数 Quicksort，但我不明白为什么 CUTOFF 变量在那里？和插入方法？

public class Quick3string {

    private static final int CUTOFF =  15;   // cutoff to insertion sort

    // sort the array a[] of strings
    public static void sort(String[] a) {
        // StdRandom.shuffle(a);
        sort(a, 0, a.length-1, 0);
        assert isSorted(a);
    }

    // return the dth character of s, -1 if d = length of s
    private static int charAt(String s, int d) { 
        assert d >= 0 && d <= s.length();
        if (d == s.length()) return -1;
        return s.charAt(d);
    }


    // 3-way string quicksort a[lo..hi] starting at dth character
    private static void sort(String[] a, int lo, int hi, int d) { 

        // cutoff to insertion sort for small subarrays
        if (hi <= lo + CUTOFF) {
            insertion(a, lo, hi, d);
            return;
        }

        int lt = lo, gt = hi;
        int v = charAt(a[lo], d);
        int i = lo + 1;
        while (i <= gt) {
            int t = charAt(a[i], d);
            if      (t < v) exch(a, lt++, i++);
            else if (t > v) exch(a, i, gt--);
            else              i++;
        }

        // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]. 
        sort(a, lo, lt-1, d);
        if (v >= 0) sort(a, lt, gt, d+1);
        sort(a, gt+1, hi, d);
    }

    // sort from a[lo] to a[hi], starting at the dth character
    private static void insertion(String[] a, int lo, int hi, int d) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
                exch(a, j, j-1);
    }

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

    // is v less than w, starting at character d
    private static boolean less(String v, String w, int d) {
        assert v.substring(0, d).equals(w.substring(0, d));
        return v.substring(d).compareTo(w.substring(d)) < 0; 
    }


    // is the array sorted
    private static boolean isSorted(String[] a) {
        for (int i = 1; i < a.length; i++)
            if (a[i].compareTo(a[i-1]) < 0) return false;
        return true;
    }


    public static void main(String[] args) {

        // read in the strings from standard input
        String[] a = StdIn.readAll().split("\\s+");
        int N = a.length;

        // sort the strings
        sort(a);

        // print the results
        for (int i = 0; i < N; i++)
            StdOut.println(a[i]);
    }
}

来自http://www.cs.princeton.edu/algs4/51radix/Quick3string.java.html

4

4 回答 4

8

它似乎用于为足够小的（大小 <= 15）数组调用插入排序。这最有可能加快排序。

于 2010-06-10T17:58:28.957 回答
1

这是对快速排序算法的简单优化。快速排序中递归调用的成本相当高，因此对于小数组，插入排序效果更好。所以，这个想法是，如果要排序的子数组的长度低于某个阈值，那么使用插入排序比快速排序更好。在您的示例中，CUTOFF 变量定义了该阈值，即如果剩下的元素少于 15 个，则使用插入排序而不是快速排序对它们进行排序。

于 2010-06-10T18:02:11.960 回答
1

上面的排序方法是一种递归方法。并且每个递归方法都应该有某种基本情况（否则它将继续调用自己，最终导致堆栈溢出）。

插入部分是该方法中的基本情况，因为在每个递归步骤中，hi-lo 差异不断减小，并且当其小于 CUTOFF 时，最终将触发插入排序，从而迫使递归停止。

if (hi <= lo + CUTOFF) {       // base case
    insertion(a, lo, hi, d);
    return;
}

现在，为什么要插入？因为它适用于小型阵列。更多关于排序的信息：http: //www.sorting-algorithms.com/

于 2013-10-17T20:30:03.743 回答
1

这个想法来自 Robert Sedgewick，他对 Quicksort 的了解可能比任何在世的人都多。它在 Donald E. Knuth, The Art of Computer Programming, Volume III 中被引用，其中他表明对于小M，插入排序比 Quicksort 快，因此他建议根本不要对小于M的小分区进行排序并将其留给最后一个最后对整个数据集进行插入排序。Knuth 给出了一个计算M的函数（即你的CUTOFF），对于他的MIX伪计算机来说是 9。

于 2013-10-17T22:06:04.357 回答