3路快速排序，问题

我想了解3路基数Quicksort，我不明白为什么CUTOFF变量在那里？和插入方法？3路快速排序，问题

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

来源

2010-06-10 Peiska

@peiska：不是答案（因此评论）......八十年代的“优化”有多可爱;）在多核CPU的这个时代，真正的优化是通过并行获得的。我写了自己正确的Java多线程quicksort（现在在数百个系统上生产），并* *是*优化:)我在这里谈了一下：http://stackoverflow.com/questions/2210185看到你'重新询问quicksort，我认为值得一提的是，现在最快的quicksort（对于实际数据量）绝对是多线程的。 – SyntaxT3rr0r 2010-06-10 18:20:03

请注意，CUTOFF的值很可能会从帽子中取出。 – 2010-06-10 18:34:20

@ThorbjørnRavnAndersenDon Knuth的帽子，其实是带着证明。 – EJP 2013-10-17 22:35:57

它似乎为了调用插入排序为足够小（尺寸< = 15）阵列中使用。这很可能会加快排序。

来源

2010-06-10 17:58:28

啊，你只是想打败我。插入排序“对于小列表和大多数排序列表是相对有效的”（[Wikipedia]（http://en.wikipedia.org/wiki/Sorting_algorithm#Insertion_sort）），因此这将是对“正常”三快速排序。 cutoff是一个变量，所以你可以调整你想要切换到插入排序的地方。 +1！ – Pops 2010-06-10 18:02:37

感谢您的解释+1 – Peiska 2010-06-10 18:09:28

插入排序是O（N^2）和快速排序平均O（N日志N），但这些是渐近结果（对于大N）。在一些低N的情况下，从插入排序越快越好到快速排序越好。交叉点是实现和系统相关的。 – 2010-06-10 18:16:00

这是一个简单的快速排序算法优化。在quicksort中递归调用的代价非常高，因此对于小数组插入排序可以更好地工作。所以，这个想法是，如果将子数组的长度排序在某个阈值以下，最好使用插入排序而不是快速排序。在你的例子中，CUTOFF变量定义了该阈值，即如果剩下少于15个元素，则使用插入排序而不是快速排序对它们进行排序。

来源

2010-06-10 18:02:11

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

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

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

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

来源

2013-10-17 20:30:03

这个想法来自罗伯特Sedgewick，谁知道更多关于Quicksort可能比任何人还活着。它在唐纳德·E·Knuth的，计算机程序设计艺术，第三卷，他表示，对于小男，插入排序快于快速排序，所以他建议不选小分区< 中号在所有引用并在最后对整个数据集进行最后一次插入排序。 Knuth给出了计算M（这是你的CUTOFF）的功能，并且对于他的MIX伪计算机是9。

来源

2013-10-17 22:06:04 EJP

3路快速排序，问题

回答

相关问题