倒插排序！

Question

這是一個我在Wikipedia網站找到的問題（我想很好地學習排序算法）。無論如何，這是一個問題 - 你能向我解釋我能如何展示它嗎？

練習：假定I爲反轉的在陣列A.

Answer 1

看的this page的Implementation和Analysis部的數量顯示該算法插入排序（A）在時間O（N + I）中運行。

考慮算法提出有：

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

注意，while循環爲v[i]迭代，其中v[i]是由元件i反轉的數目運行。這應該使證明非常容易理解。