插入排序作法：
將資料分成已排序、未排序兩部份
依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置
插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入
比較時，若遇到的值比正處理的值大或相等，則將值往右移
時間複雜度(Time Complexity)
Best Case：Ο(1)
當資料的順序恰好為由小到大時，每回合只需比較1次
Worst Case：Ο(n^2)
當資料的順序恰好為由大到小時，第i回合需比i次
Average Case：Ο(n^2)
第n筆資料，平均比較n/2次
來源：http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php
阿摩線上測驗
登入