是選擇排序一種有效的算法嗎？

我知道這是一個quadratric時間算法，但它是如何比較其他的排序算法，如快速排序或冒泡排序？是選擇排序一種有效的算法嗎？

2009-12-03 Jenny

排序算法一般變化基於數據的性質你。

但是，雖然冒泡排序和選擇排序很容易理解（並實現）排序算法，但它們的運行時間爲O（n^2），即您可能獲得的最差時間。

就快速排序而言，它需要O（n log n）時間，因此它是一個很好的排序。但是，在某些情況下也可能需要O（n^2）。

2009-12-03 23:26:16 anirudhgarg

你總是可以訪問列表的所有排列，並返回碰巧排序的第一個（O（n！））:) –

Wikipedia知道所有。

選擇排序非常糟糕。

2009-12-03 23:23:42 abelenky

非常多的是，但你可以在你的批評中更具描述性:) –

根據數據集的大小，二次算法可能會令人難以置信地變得更慢。

N = 10e78（約原子在宇宙中的數量）

對於二次算法，這是N *（10e78）。對於一個n日誌（n）的算法，如快速排序或歸併，這是N * 262。這是一個巨大的差異。

但是如果你的數據集相對較小（< 1000個項目，說），那麼性能差異可能不會出現明顯的（除非，也許，那種被重複完成）。在這種情況下，通常最好使用最簡單的算法，後來優化，如果它原來是太慢了。

「不成熟的優化是萬惡之源。」 -SiR東尼·霍爾，由高德納

2009-12-03 23:31:50

這是一個愚蠢的例子。沒有人會嘗試對10e78物品進行分類。「640K項目應該是足夠的人」 - 比爾·蓋茨 –

我你的文章的第一部分同意，但我不認爲選擇合適的/快速排序算法是過早的優化。此外，只要系統組件是鬆耦合的，排序算法應該是相當容易在以後的優化來代替。 –

順便說一句，我愛用「宇宙中的原子數」的例子，把一切的角度:) –

推廣如果你有數據僅是你可能想看看桶排序正整數。該算法可以在正確的條件下具有線性運行時間O（n）。

2009-12-03 23:38:49 Greycrow

http://en.wikipedia.org/wiki/Bucket_sort –

回答