墨墨喵喵喵

程式碼懶得打了((欸

反正課本p.21就有

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置後
6. 重複步驟2~5

(取自維基)

Best Case:

已排序好(小到大)

就是拿n-1次,所以是O(n),

第2項比第1項大,往下拿第3項,第3項比第2項大,接著拿第4項....然後一直到第n項,結束

共計是n-1項(2~n)

因為要抓放,所以是2(n-1)

所以是O(n)

Worst Case:

已排序好(相反:大到小)

每次拿n時.都要比n-1次,從2拿到n (拿第2項比1次,拿3項比2次...一直到n項)

共計是

(n-1) * (1+ (n-1) ) / 2

高=n-1, 從1 (2比1次) 比到n-1 (n比n-1次)

再加上抓,放次數 2 (n-1)

所以是O(n^2)

Averge Case:

EX: 5個數字

第2項有 1/2機率移1次 1/2機率移0次(不移動)

第3項有 1/3機率移2次 1/3機率移1次 1/3機率移0次

第4項有 1/4機率移3次 1/4機率移2次 1/4機率移1次 1/4機率移0次

第5項有 1/5機率移4次 1/5機率移3次 1/5機率移2次 1/5機率移1次 1/5機率移0次

每項還要再加上抓,放兩個動作(前面那大串是比較)

還要加上抓放2(n-1)

所以是 

  +2(n-1)

時間複雜度是O(n^2)