插入排序適合於部分有序序列和小規模的數據。其平均時間複雜度為 O(N^2)，空間複雜度為 O(1)，並且為穩定排序。
插入排序將待排序序列分為有序區 (記為 S 區)和無序區(記為 R 區)。以從小到大的順序為例，每次從 R 區彈出一個元素 O，要將元素 O 插入到 S 區中恰當位置。從 S 區最右端開始，依次比較 S 區元素與元素 O 的大小。如果元素O 比 S 區元素小，就將 S 區元素後移一位。如果元素 O 大於 S 區元素，就在該元素右邊一位插入元素 O。
分享到:
閱讀更多 Python高效編程 的文章
