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

答案：登入後查看
統計： A(6), B(120), C(45), D(11), E(0) #1263452

詳解 (共 2 筆)

#4351053
最差的狀況指的是要比較最多次B 剛好是由...
(共 45 字，隱藏中）
前往觀看
0
0
#4867788
下方有連結有動圖, 建議可以點進去看, 會更容易了解
  • 插入排序作法：
    • 將資料分成已排序、未排序兩部份
    • 依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置
      • 插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入
      • 比較時，若遇到的值比正處理的值大或相等，則將值往右移
  • 時間複雜度(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

0
0