1

在实现对快速排序分区的改进时，我尝试使用 Tukey 的 ninther 来找到枢轴（几乎从 sedgewick 在QuickX.java中的实现中借用了所有内容）

每次对整数数组进行洗牌时，下面的代码都会给出不同的结果。

import java.util.Random;
public class TukeysNintherDemo{    
    public static int tukeysNinther(Comparable[] a,int lo,int hi){
        int N = hi - lo + 1;
        int mid = lo + N/2;
        int delta = N/8;
        int m1 = median3a(a,lo,lo+delta,lo+2*delta);
        int m2 = median3a(a,mid-delta,mid,mid+delta);
        int m3 = median3a(a,hi-2*delta,hi-delta,hi);
        int tn = median3a(a,m1,m2,m3);
        return tn;
    }

    // return the index of the median element among a[i], a[j], and a[k]
    private static int median3a(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));
    }

    private static boolean less(Comparable x,Comparable y){
        return x.compareTo(y) < 0;
    }
    public static void shuffle(Object[] a) {
    Random random = new Random(System.currentTimeMillis());
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int r = i + random.nextInt(N-i);     // between i and N-1
            Object temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }
    public static void show(Comparable[] a){    
        int N = a.length;
        if(N > 20){
            System.out.format("a[0]= %d\n", a[0]);
            System.out.format("a[%d]= %d\n",N-1, a[N-1]);
        }else{
            for(int i=0;i<N;i++){
                System.out.print(a[i]+",");
            }
        }
        System.out.println();

    }
    public static void main(String[] args) {
        Integer[] a = new Integer[]{17,15,14,13,19,12,11,16,18};
        System.out.print("data= ");
        show(a);
        int tn = tukeysNinther(a,0,a.length-1);
        System.out.println("ninther="+a[tn]);
    }
}

Running this a cuople of times gives

data= 11,14,12,16,18,19,17,15,13,
ninther=15

data= 14,13,17,16,18,19,11,15,12,
ninther=14

data= 16,17,12,19,18,13,14,11,15,
ninther=16

tukey's ninther 会为同一数据集的不同改组提供不同的值吗？当我试图手动找到中位数的中位数时，我发现代码中的上述计算是正确的。这意味着同一个数据集产生的结果与数据集的中位数不同。这是正确的行为吗？有更多统计知识的人可以发表评论吗？

4

1 回答 1

2

Tukey's ninther 检查 9 个项目并仅使用这些项目计算中位数。

对于不同的随机洗牌，您很可能会得到不同的 Tukey's ninther，因为可能会检查不同的项目。毕竟，您总是检查相同的数组槽，但不同的 shuffle 可能会在这些槽中放入不同的项目。

这里的关键是 Tukey 的 ninther不是给定数组的中位数。这是对中位数的一种尝试性近似，几乎不费吹灰之力：我们只需要阅读 9 个项目并进行 12 次比较即可得到它。这比获得实际中位数要快得多，并且与“三的中位数”相比，导致不良枢轴的可能性更小。请注意，机会仍然存在。

这能回答你的问题吗？

顺便说一句，有人知道使用 Tukey 的 ninther 的快速排序是否仍然需要改组？我假设是的，但我不确定。

于 2013-10-04T12:23:03.633 回答