題組內容

一、簡要說明

⑶ insertion sort 之基本概念及時間複雜度。 （20 分）

詳解 (共 1 筆)

詳解 提供者：000
插入排序作法： 將資料分成已排序、未排序兩部份 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入 比較時，若遇到的值比正處理的值大或相等，則將值往右移 時間複雜度(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