排序問題？

堆排序被認爲是「分而治之」排序還是優先排序？排序問題？

此外，什麼類別的排序會適合一個氣泡（除了可怕的）。

我讀過堆排序通常被認爲是「分而治之」排序，但它可以是優先級隊列排序。它是嚴格的一個還是另一個？或者它是如何兩個？我無法找到任何可能考慮泡沫的東西。

2013-03-19 Twisterz

這是兩個不同的問題，應該這樣問。另外請在你的部分展示某種研究。 – 2013-03-19 01:15:35

好吧，我以爲他們都歸入同一類別，所以他們可以一起問。 – Twisterz 2013-03-19 01:16:11

泡泡排序將是一個「天真」 – TravellingGeek 2013-03-19 01:16:46

我不認爲HeapSort被認爲是「分而治之」，因爲在任何時候算法都不會將問題細分爲子問題。要執行HeapSort，算法執行ExtractMin或ExtractMax，直到Heap爲空。這些操作是O(logn)，因爲在每個ExtractMin或ExtractMax之後，Heap必須做Heapify才能保留它的部分順序。最後的成本爲O(nlogn)，因爲它確實是nExtractMin或ExtractMax。

這裏是一個僞代碼

HeapSort() 
heap 
new_ ordered_collection 
while(heap.NotEmpty) 
    new_ ordered_collection.add(heap.ExtractMin)//or ExtractMax 
    heap.Heapify //could be MaxHeapify or MinHeapify 
return new_ ordered_collection

注意ExtractMin和ExtractMax彈出最小或堆的最大元素。

正如你所看到的，我沒有看到「分而治之」的策略。

但heap.Heapify基於堆的部分順序重新排序元素。這一個定義了每個節點和他的兩個孩子之間的關係，因此，heap.Heapify應用了「分而治之」的策略，但這是DataStructre自身沒有的算法。

並且冒泡排序是naive算法。

來源

2013-03-19 01:29:25

完美，這是我需要知道的！ – Twisterz 2013-03-19 01:31:53

很高興知道！我忘了提到創建一個Heap需要'O（n）'操作。但仍然是'O（nlogn）'整個算法。感謝您接受我的回答。 – 2013-03-19 01:52:12

如果你給了一個未排序的數組，那麼你如何構建堆？使用分而治之算法可以在O（n）中完成從未排序數組構建堆。請參閱https://www.ics.uci.edu/~eppstein/161/960118.html – giga 2017-03-08 19:41:11

堆排序具有'分而治之'算法（如快速排序）的時間複雜性，但它不像分而治之算法。

因爲它將數據分成'排序'和'未排序'兩部分，這實際上是一種選擇排序。它利用堆數據結構更有效地從每個步驟的未排序列表中選擇最小元素。我想你可以說這是一個'優先隊列排序'，因爲這個原因，但應該提到整個操作可以在原地完成，而不是建立一個單獨的堆。

堆排序通常優於快速排序，但快速排序的最壞情況下的複雜度爲O(N^2)（與堆排序的最壞情況O(N.logN)相比）。

冒泡排序也是一個就地算法，但它被認爲是'天真'。

來源

2013-03-19 01:34:03 paddy

如上所述，堆排序絕對不是「分而治之」算法。堆排序使用堆數據結構來有效地對其元素進行排序。您可以將堆排序視爲具有優先級隊列的選擇排序。

分治法具有以下特徵：

1）分區任務分成子任務它們是相同的任務 2小實例）遞歸解決子任務 3）適當地組合的結果

正如你可以看到堆排序不符合這種類型的算法。唯一的相似之處是分而治之算法的結構反映了二叉樹的結構（這通常是堆排序用於實現優先級隊列的）。

來源

2013-07-09 20:18:34

回答

相關問題