所以,最近,出于好奇,我买了 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
有人可以向我解释这些结果吗?该算法几乎相同。只是实现方式不同。实现上的一点点差异怎么会导致运行时间的巨大差异?