18 若有n個數值，用氣泡排序法（Bubble Sort）進行排序，其時間複雜度何者錯誤？
(A)最好情況為O(n)
(B)最壞情況為O(n2 )
(C)平均情況為O(n2 )
(D)不是穩定排序法

答案：登入後查看
統計： A(78), B(63), C(88), D(295), E(0) #2397207

詳解 (共 5 筆)

#4378185

Bubble sort 總共需要n-1次迭代，每次迭代至少需要執行n-1-i置換，時間複雜度為 O(n2)。

在已排序完成的序列上，只需要迭代序列一次，發現完全沒有置換任何元素，即停止排序，可達到最佳時間複雜度O(n)。

Bubble sort 的特性如下：

  • 又稱為 sinking sort。
  • 穩定排序：相同鍵值的元素，排序後相對位置不改變。
  • 原地排序：不需額外花費儲存空間來排序。

來源

5
0
#4216985
穩定排序法意思是說同樣的數值在一序列不會...
(共 82 字，隱藏中）
前往觀看
4
1
#4682537
穩定排序法：相同元素排序前後的相對位置不...
(共 27 字，隱藏中）
前往觀看
1
0
#5000243

穩定排序：

假設一個序列(1,5)(6,8)(3,6)(4,5)在排序後 

穩定排序：(1,5)(3,6)(4,5)(6,8)  -> (6,8) 直接丟到後面，(3,6)(4,5)往前相對位置不改變。

不穩定排序：(1,5)(4,5)(3,6)(6,8) ->(6,8) 與 (4,5) 交換，相對位置改變。


0
2
#5140067

穩定排序(stable sort):

IBM=>

I:Insertion Sort

B:Bubble Sort

M:Merge Sort

0
0

私人筆記 (共 1 筆)

私人筆記#2983777
未解鎖


(共 0 字，隱藏中）
前往觀看
2
0