java - 插入排序比 shell 排序快得多

Question

我正在阅读 Sedgewick 的“算法”中有关排序的章节。在此过程中，我编写了 3 个基本的排序算法:选择、插入和 shell 排序。书中说，尽管这三者都具有二次最坏情况的复杂性，但 shell 排序应该比随机数据的插入排序快得多。在书中，他们获得了 600 倍的性能提升。

但我在笔记本电脑上得到以下乘法器(几乎不随阵列大小的增加而改变):

• 选择:5.5 倍
• 插入:1x
• 外壳:1.8 倍!

困扰我的问题是 - 为什么 shell 排序比插入排序慢将近两倍？!

我想，我的 shellsort 实现有问题。但我几乎是从书上抄来的:

class ShellSort extends Sort {
    //precalculate sequence: 1, 4, 13, 40, 121, 364, 1093, ...
    //(3^20 - 1)/2 is enough for any array I sort
    private static final int[] SEQUENCE = new int[20];
    static {
        for(int i = 1; i <= SEQUENCE.length; i++)
            SEQUENCE[i - 1] = (int)(Math.pow(3, i) - 1) / 2;
    }

    public void sort(int[] a) {
        int length = a.length;

        int seqLen = SEQUENCE.length;
        int nth;
        int j;

        for(int seqi = seqLen - 1; seqi >= 0; seqi--) {
            if(SEQUENCE[seqi] < length / 3) {
                nth = SEQUENCE[seqi];
                for(int n = 0; n < length; n+=nth) {
                    j = n;
                    while(j > 0 && a[j] < a[j - nth]) {
                        exch(a, j, j-nth);
                        j -= nth;
                    }
                }
            }
        }
    }
}

其余代码供那些想在他们的机器上运行测试的人(使用 JVM 加热将数组大小测试加倍对结果没有显着影响，所以这个简单的测试对 N 来说已经足够了 > ~ 200 000)。

主要内容:

int N = 500_000;
Random rand = new Random();
int[] a = new int[N];
for(int i = 0; i < N; i++)
    a[i] = rand.nextInt();

//insertion sort
int[] aCopy = Arrays.copyOf(a, a.length);
long start = System.nanoTime();
new InsertionSort().sort(aCopy);
System.out.println("insert:\t" + (System.nanoTime() - start));

//shell sort
aCopy = Arrays.copyOf(a, a.length);
start = System.nanoTime();
new ShellSort().sort(aCopy);
System.out.println("shell:\t" + (System.nanoTime() - start));

InsertionSort 和 Sort 类:

class InsertionSort extends Sort {
    public void sort(int[] a) {
        int length = a.length;
        int j;
        int x;
        for(int i = 1; i < length; i++) {
            j = i;
            x = a[i];
            while(j > 0 && x < a[j-1]) {
                a[j] = a[--j];
            }
            a[j] = x;
        }
    }
}
abstract class Sort {
    abstract public void sort(int[] a);

    protected static final void exch(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

Answer 1

您的实现被破坏并仅由于最后一步为 1 并且您的两个内部循环在步为 1 时执行基本插入排序而输出排序数组。当步长大于 1 时，你的实现中的两个内部循环除了对数组进行步进排序外什么都不做，所以你的实现所做的是在外循环的所有迭代中打乱数组，然后在最后一次插入排序外循环的迭代。当然，它会花费更长的时间，然后只需插入排序一次。

重用您的序列，正确的 shell 排序实现应该如下所示:

public void sort( int[] a ) {
    int length = a.length;

    int stepIndex = 0;
    while ( stepIndex < SEQUENCE.length - 1 && SEQUENCE[ stepIndex ] < length / 3 ) {
        stepIndex++;
    }

    while ( stepIndex >= 0 ) {
        int step = SEQUENCE[ stepIndex-- ];
        for ( int i = step; i < length; i++ ) { // DIFF: i++ instead of i+=step
            for ( int j = i; j >= step && a[ j ] < a[ j - step ]; j -= step ) {
                exch( a, j, j - step );
            }
        }
    }
}

此实现与您的实现之间的两个主要区别:

• 两个内部循环的正确初始索引
• 中间循环的适当索引增量(+1 而不是代码中的 +step)

此外，检查 http://algs4.cs.princeton.edu/21elementary/Shell.java.html以获得良好的实现和良好的步骤顺序。