排序算法的內存速度折衷

只考慮氣泡排序和合並排序。對於冒泡排序，時間複雜度將是O（n）到最壞情況O（n^2）和空間複雜度O（1）。對於合併排序，時間複雜度爲O（nlogn），空間複雜度爲O（n）。如果輸入的大小小於1000，您會選擇哪種類型？爲什麼？ 1000多呢？排序算法的內存速度折衷

這是我的一個面試問題。只是想知道你們會如何回答它。

2013-03-11 ethanjyx

你選擇什麼取決於你用什麼標準來評估。我會選擇「最快的代碼清理」，而且不用考慮任何性能方面的考慮。這聽起來很像作業... – Floris 2013-03-11 17:48:03

取決於大量的東西。例如，你有多少內存？你在內存或文件中排序？數據是否可能接近排序？會並行一個選項？ – Shahbaz 2013-03-11 17:49:32

'輸入小於1000' - 只要使用冒泡排序或任何O（n^2）排序算法，如果編碼更簡單。 '怎麼樣超過1000' Mergesort/Quicksort甚至混合了Quick Sort + Insertion Sort。 – nhahtdh 2013-03-11 18:00:37

只考慮氣泡排序和合並排序。

通過小於1000，這可能意味着RAM對於任何沒有外部存儲的排序算法都足夠了。這也意味着在這種情況下，時間複雜性的理論界限並不重要。您可以選擇任何您喜歡的排序算法，而不會招致任何時間處罰。例如，你可以做冒泡排序，因爲它可能很容易和直觀的實現。合併排序一樣好。

當輸入大小大於1000時，可能假設時間複雜性很重要，即使沒有外部存儲器，RAM可能也不夠大。在這種情況下，如果您必須在兩者之間進行選擇，則合併排序是安全的選擇。這是因爲合併排序在氣泡排序上具有更好的最差情況性能，合併排序是external sort（當輸入大小大於RAM時）的良好候選者。

2013-03-11 19:06:24

10000甚至10^7通常對個人電腦沒有任何問題，並且在我們處理非常有限的資源約束時會成爲問題。快速排序（與插入排序混合）是PC機箱的一種選擇。 – nhahtdh 2013-03-11 19:15:49

@nhahtdh我同意。這通常是我們在實踐中所做的。 – 2013-03-11 19:19:34

回答