4

所以，最近，出于好奇，我买了 CLRS 的《算法简介》一书。当我开始阅读本书时，我注意到书中一些非常典型的算法以非常不同的方式实现。

给定 CLRS 的快速排序的实现与流行的快速排序 Hoare 算法有很大不同。

所以来回答我的问题...

void insertion_sort_by_robertsedgewick(int a[],int n)
{   
    for(int i=0;i<n;i++)
    {
        for(int j=i;j>0;j--)
        {
            if(a[j]<a[j-1])
            {
                swap(a[j],a[j-1]);
            }
        }
    }
}

是 Robert Sedgewick 在他的 Coursera 算法课程中使用的代码。

相比之下，CLRS 中给出的插入排序实现是，

void insertion_sort_CLRS(int a[] , int n)
{
    int key,j;
    for(int i=1; i<n; i++)
    {
        key = a[i];
        j = i - 1;
        while(j>=0 && a[j]>key)
        {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
    }
}

比较奇怪的是运行时间。以下是我运行两种不同实现时的结果：

数组中的元素数：10,000

Robert Sedgewick 的实现耗时：0.235926s

CLRS 实现耗时：0.078608s

有人可以向我解释这些结果吗？该算法几乎相同。只是实现方式不同。实现上的一点点差异怎么会导致运行时间的巨大差异？

4

2 回答 2

3

您显示的 Robert Sedgewick 代码主要用于说明，而不是用于性能。

在他使用相同代码的算法书中引用他自己的话：

通过缩短其内部循环以将较大的条目向右移动一个位置而不是进行完全交换（从而将数组访问次数减少一半），大幅加速插入排序并不难。我们将此改进留作练习

与他在 Coursera 课程中的快速排序代码类似，请参阅QuickSort Dijkstra 3-Way Partitioning：为什么要进行额外的交换？.

于 2014-10-20T06:28:03.510 回答
2

我看到的 CLRS 实现的轻微效率是它不会立即交换元素，而只是向上复制元素并等待直到获得键的位置。然后它将密钥复制到正确的位置。

如果在任何迭代中，数组是：

1 2 3 6 7 8 5
            ^

并且指针位于 5，那么在第一个版本中，步骤将是：

1 2 3 6 7 5 8
1 2 3 6 5 7 8
1 2 3 5 6 7 8

而在下一个版本中，步骤将是：

1 2 3 6 7 8 8
1 2 3 6 7 7 8
1 2 3 6 6 7 8
1 2 3 5 6 7 8
于 2014-10-20T06:28:51.307 回答