插入排序比shell排序快得多

Question

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

但是我的笔记本电脑上有以下乘法器(几乎不随数组大小的增加而改变):

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

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

我想,我的shellort实现有问题.但我几乎从书中复制了它:

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以获得良好的实现和良好的步骤顺序。