因此,最近,出於好奇,我購買了CLRS的「Introduction to Algorithms」一書。在我開始閱讀本書時,我注意到本書中一些非常典型的算法以非常不同的方式實現。使用CLRS代碼和Robert Sedgewick代碼的插入排序的運行時間差異
給定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]);
}
}
}
}
是在他的算法當然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
時間採取由羅伯特·塞奇威克的實現:0.235926s
時間採取由CLRS的實現:
數組中元素的個數0.078608s
有人可以向我解釋這些結果嗎? 算法幾乎相同。只有實施是不同的。實施過程中的一些小差異如何在運行時間上造成如此巨大的差異?