下列哪一種排序演算法，在最差狀況下排序N筆資料，其時間複雜度為O(N2)？ (A) 插入排序法(insert sort) (B) 合併排序法(merge sort) (C) 錐形排序法(heap sort) (D) 基數排序法(radix sort)

國營聯招資訊計算機原理、網路概論103 年第 6 題單選題考點：插入排序最差O(N²)考點：Merge Sort恆O(NlogN)

下列哪一種排序演算法，在最差狀況下排序N筆資料，其時間複雜度為O(N2)？

A插入排序法(insert sort)正確答案

B合併排序法(merge sort)

C錐形排序法(heap sort)

D基數排序法(radix sort)

答案與詳解

正確答案

插入排序法(Insertion Sort)最差情況為O(N²)；Merge Sort與Heap Sort保證O(N log N)；Radix Sort為O(Nk)。

A插入排序法(insert sort)插入排序最差O(N²)✓ 正確

插入排序法(Insertion Sort)：最差情況為逆序排列時，每次插入都需比較到底，時間複雜度為O(N²)。最佳情況(已排序)為O(N)。

B合併排序法(merge sort)Merge Sort恆O(NlogN)✕ 錯誤

合併排序法(Merge Sort)：不論最佳、平均、最差情況均為O(N log N)，屬於穩定且效能保證的排序演算法。

C錐形排序法(heap sort)✕ 錯誤

D基數排序法(radix sort)✕ 錯誤

這題的完整詳解,註冊就能看 · 每天 2 題免費

精選詳解