插入排序比希尔排序快得多。

Question

我正在阅读Sedgewick的《算法》中有关排序的章节。在此过程中，我编写了三个基本的排序算法：选择排序、插入排序和希尔排序。书中指出，尽管这三种算法的最坏情况时间复杂度都为二次方级别，但在随机数据上，希尔排序应该比插入排序快得多。书中给出了600倍的性能提升。

但是在我的笔记本电脑上，我得到了以下的乘数（几乎不随数组大小增加而改变）：

- 选择排序：5.5倍 - 插入排序：1倍 - 希尔排序：1.8倍！

我困扰的问题是：为什么希尔排序几乎比插入排序慢两倍？

我猜测，可能是我的希尔排序实现有问题。但我几乎是从书中抄袭的。

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));

插入排序和排序类：

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;
    }
}

- Oroboros102

---

在将太多重量放入您的结果之前，遵循这里的准则[如何正确编写Java微基准？]（https://dev59.com/hHRB5IYBdhLWcg3wz6UK）是个好主意。 - Bernhard Barker

在你证明它们具有**统计学意义**之前，永远不要试图解释实证结果。 - amit

我在更复杂的基准测试中使用JVM "热身"来运行了所有代码，并得到了相同的结果。原因是 - 内部循环很快就被JIT编译，而且没有引入任何显著的GC开销。 - Oroboros102

为了使测试更具统计学意义，我使用指数数组大小增长（N = 2 ^ k，k = 1、2、3 ...）进行测试。结果相同。 - Oroboros102

不确定它对结果有多大影响，但书上说是100,000个随机Double而不是int。此外，为确保不进行任何优化，请尝试使用C编写算法，并使用gcc进行编译而不进行优化。 - Déjà vu

@ring0 越多越好（更精确的乘数）。我会把重写 C 作为最后的选择。 - Oroboros102

Answer 1

你的实现有问题，仅因最后一步大小为1，而当步长大于1时，你的两个内部循环除了对数组进行排序外，不做任何事情。因此你的实现在每次外层循环迭代中都会打乱数组，并在最后一次外层循环中进行插入排序。当然，这比只进行一次插入排序要花费更长的时间。

正确的希尔排序实现应该像这样重复使用你的序列:

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 );
            }
        }
    }
}

本实现与您的实现有两个主要区别：

• 两个内部循环的初始索引正确
• 中间循环的索引增量正确（在您的代码中为+step，而应为+1）

此外，请查看http://algs4.cs.princeton.edu/21elementary/Shell.java.html以获取一个好的实现和良好的步骤序列。

- Oleg Estekhin

---

哈哈，我开始计算缓存未命中而不是理解算法。 - Oroboros102

Answer 2

从一眼看去，你可以看到希尔排序通过更多的循环看起来比较慢。如果采用暴力方法，可以在最内层循环中放置一个system.out.println来查看有多少次比较。

希尔排序的3个循环

• for(int seqi = seqLen - 1; seqi >= 0; seqi--)
• for(int n = 0; n < length; n+=nth)
• while(j > 0 && a[j] < a[j - nth])

插入排序的2个循环

• for(int i = 1; i < length; i++)
• while(j > 0 && x < a[j-1])

- jcalloway

---

希尔排序的循环次数约为插入排序的0.8倍。但仍然比较慢，而且不像书中所说的那样快600倍。 - Oroboros102

自我修复：“仍然较慢，但不是快600倍”。 - Oroboros102

@Oroboros102，我再看看你的代码。我可能不会计算构造函数调用的时间。不确定静态初始化程序何时运行。另外，请尝试在插入排序之前计时希尔排序。看看是否仍然产生相同的效果。 - jcalloway

Answer 3

我认为原因可能是缓存。希尔排序有很多（有点）随机访问，因此会有更多的缓存未命中。我相信在新硬件上它会表现得更差。插入排序几乎总是在同一内存区域上工作，因此它的性能更好。

- user1097048

---

你的假设看起来更像是真实的。我该如何验证它？ - Oroboros102

看起来 perf stat ./a.out 应该可以工作。但我不确定它对于Java应用程序是否同样有效。 - user1097048

看起来缓存未命中不是问题。插入排序：161M 引用和 230K 未命中，希尔排序分别为 167M 和 300K。 - Oroboros102

更有趣的是，希尔排序具有更多（约2倍）的“循环”和“分支”。这似乎是算法问题，但我在我的代码中找不到它。 - Oroboros102

Answer 4

你的希尔排序实现不正确。你没有将每个元素与数组中给定步长进行比较。你应该只在中等大小的数组上使用插入排序和希尔排序，以获得最佳效果。你可以使用泛型来消除所有警告。你还可以参考这个增量序列来获得更好的结果。

下面是相同功能的希尔排序代码：

public class ShellSort<T> {

    //Knuth's function for shell sort
    //0(n^3/2) in practice much better
    public static List<Integer> shellSortIncrementSeqFunction(int length) {
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < length; i++)
                res.add(3 * i + 1);
        return res;
    }

    //Good function tough to compete
    private List<Integer> shellSortIncrementSeqFunctionGood(int length) {
        int argForFunction1 = 0;
        int argForFunction2 = 2;
        List<Integer> res = new ArrayList<>();
        while(true) {
            int val1 = shellSortArgFunction1(argForFunction1);
            int val2 = shellSortArgFunction2(argForFunction2);
            if(val1 < val2) {
                if(val1 >= length)
                    break;
                res.add(val1);
                argForFunction1++;
            } else {
                if(val2 >= length)
                    break;
                res.add(val2);
                argForFunction2++;
            }
        }
        return res;
    }

    private int shellSortArgFunction1(int arg) {
        return (int)(9 * Math.pow(4, arg) - 9 * Math.pow(2, arg) + 1);
    }

    private int shellSortArgFunction2(int arg) {
        return (int)(Math.pow(4, arg) - 3 * Math.pow(2, arg) + 1);
    }


    @SuppressWarnings("unchecked")
    private boolean less(Comparable<T> thisComparable, Comparable<T> thatComparable) {
        return thisComparable.compareTo((T) thatComparable) < 0;
    }

    private void exchange(Object[] comparableArray, int thisIndex, int thatIndex) {
        Object temp = comparableArray[thisIndex];
        comparableArray[thisIndex] = comparableArray[thatIndex];
        comparableArray[thatIndex] = temp;
    }

    public boolean isSorted(Comparable<T>[] comparableArray) {
        boolean res = true;
        int len = comparableArray.length;
        for(int i = 1; i < len; i++)
            res &= !less(comparableArray[i], comparableArray[i - 1]);
        return res;
    }

    public void shellSort(Comparable<T>[] comparableArray) {
        int len = comparableArray.length;
        List<Integer> incrementSequence = shellSortIncrementSeqFunctionGood(len);
        int seqLen = incrementSequence.size() - 1;
        for(int i = seqLen; i >= 0; i--) {
            int step = incrementSequence.get(i);
            //h-sorting the array
            for(int j = step; j < len; j++)
                for(int k = j; k >= step && less(comparableArray[k], comparableArray[k-step]); k -= step)
                    exchange(comparableArray, k, k-step);
        }
        assert isSorted(comparableArray);
    }

    private void show(Comparable<T>[] comparableArray) {
        Arrays.stream(comparableArray).forEach(x -> System.out.print(x + ", "));
        System.out.println();
    } 

}

您可以在这里查看此帖子的源代码。

- The Flash