为什么我的排序算法比 H.Cormen 书中 "Introduction to Algorithms" 中的排序算法快？

Question

我从昨天开始学习这本书，在我理解并应用了第一个算法之后，我尝试着自己去换个角度看。这是 Java 中显示的算法：

public static int[] sort(int[] array)
{
    for(int i = 1; i < array.length; i++){
        int value = array[i];
        int j = i - 1;

        while(j >= 0 && array[j] > value){
            array[j + 1] = array[j];
            j--;
        }
        array[j+1] = value;
    }

    return array;
}

这是我的：

public static int[] sortb(int[] array)
{
    for(int i = 0; i < array.length; i++){
        int value = array[i];
        int j = i;

        while(j < array.length && value > array[j]){
            array[j] = array[j + 1];
            j++;
        }

        array[j] = value;
    }

    return array;
}

对于每个函数调用 100 万次，我第一次得到 32 毫秒，第二次得到 25 毫秒。我还在从算法开始，所以我不知道什么意思。

Answer 1

以我的经验（阅读学生的经验）这种不同的值意义不大。

也许你有一个后台进程从一个到另一个占用/释放了更多的资源。

也许您尝试安排的特定案例对于其中一种算法比另一种算法更好。

也许，如果您使用不同的随机数组，其中一个比另一个更接近排序..

要有好的措施，你通常要做很多测试，而不是只有一个。例如，生成 1k 个数组，每个数组包含 10k 个元素，并使用两种算法对该数组中的每个数组进行排序..

无论如何，有时某种语言或编译器的特定特性可以为理论上具有完全相同复杂度的算法生成不同的结果（一个例子：有一次我在 C++ 中注意到，如果你遍历一个二维数组，首先按列然后按行，你的速度将与你反过来做的速度大不相同；但我不记得哪个更快 tbh)。

Answer 2

我发现为什么你的排序比原来的排序快得多：因为你根本没有做排序。

在你的代码中

    int value = array[i];
    int j = i;

    while(j < array.length && value > array[j]) { ... }

因为j = i，所以value == array[j]在你进入while循环之前，因此你的while循环体永远不会执行。您的排序结果将是错误的。这就是您的代码速度极快的主要原因。

为什么我的排序算法比 H.Cormen 书中 "Introduction to Algorithms" 中的排序算法快？

Why is my sorting algorithm faster than the one in "Introduction to Algorithms" by H.Cormen book?

java

algorithm

insertion-sort