計算機概論、大意(資訊科學概論,電腦常識,電子計算機概論)題庫下載題庫

上一題
17 以插入排序法（Insertion Sort）進行由小到大的排序時，下列那一個起始順序是最壞狀況（worst case）？
(A) 1，2，3，4，5，6，7，8，9
(B) 9，8，7，6，5，4，3，2，1
(C) 9，7，5，3，1，8，6，4，2
(D) 1，3，5，7，9，2，4，6，8

答案：登入後觀看
難度： 簡單
最佳解!
aabb177 國三下 (2020/11/01)
最差的狀況指的是要比較最多次B 剛好是由★...


(內容隱藏中)
查看隱藏文字
2F
鄔承翰 大二上 (2021/07/05)
下方有連結有動圖, 建議可以點進去看, 會更容易了解
  • 插入排序作法：
    • 將資料分成已排序、未排序兩部份
    • 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置
      • 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入
      • 比較時，若遇到的值比正處理的值大或相等，則將值往右移
  • 時間複雜度(Time Complexity)
    • Best Case：Ο(1)
      • 當資料的順序恰好為由小到大時，每回合只需比較1次
    • Worst Case：Ο(n2)
      • 當資料的順序恰好為由大到小時，第i回合需比i次
    • Average Case：Ο(n2)
      • 第n筆資料，平均比較n/2次


資料來源：http://notepad.yehyeh.net/Content/Algorithm/Sort/Insertion/1.php


17 以插入排序法（Insertion Sort）進行由小到大的排序時，下列那一..-阿摩線上測驗