使用CLRS代碼和Robert Sedgewick代碼的插入排序的運行時間差異

Question

因此，最近，出於好奇，我購買了CLRS的「Introduction to Algorithms」一書。在我開始閱讀本書時，我注意到本書中一些非常典型的算法以非常不同的方式實現。

給定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

有人可以向我解釋這些結果嗎？ 算法幾乎相同。只有實施是不同的。實施過程中的一些小差異如何在運行時間上造成如此巨大的差異？

Answer 1

您展示的羅伯特Sedgewick代碼主要用於說明，而不是表現。

在他算法從自己報價書使用相同的代碼：

這不難排序大幅加快插入，通過縮短其內環較大條目向右移動一個而不是進行全面交換（因此 將數組訪問次數減半）。我們將此改進留作練習

與他在Coursera課程中的快速排序代碼類似，請參閱QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?。

Answer 2

我看到的CLRS實現的輕微效率是它不會立即交換元素，而只是向上複製元素並等待直到獲得密鑰的位置。然後它將密鑰複製到正確的位置。

如果在任何迭代中，該陣列是：

​​3210

和指針是在如圖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