什麼是隨機浮點數的最佳排序算法？

我的一位同事剛把這個問題在今天下午提出來，讓我有點好奇。我對排序算法很熟悉，但缺乏正式學位（我不願意承認），但我不能真正將我的指點放在這一點上。：p什麼是隨機浮點數的最佳排序算法？

噢，是的，這在C＃/ .NET實現的環境中是很溫和的......以防萬一有所改變。

謝謝你們。 :)

2010-07-13 Richard Neil Ilagan

有多少浮子？ 3？ 300？ 3百萬？ – 2010-07-13 12:00:23

是什麼讓浮點數與int不同？除了漸近複雜性，您是否正在考慮性能度量？ – Mau 2010-07-13 12:04:22

要回答格雷格，我真的不知道。：D這是一個普遍的問題，這讓我想要尋找一般的答案，而這個答案在大多數時候最可能是最優的。：p用戶mdma提供了一個很好的參數，可以在快速排序和合並排序之間進行選擇，而無需在一定數量的元素上進行錨定。 :) – 2010-07-13 12:21:02

對於固定長度的數字，你不侷限於基於比較的排序算法，所以O(n*log(n))是不極限。 Radix Sort在O(n)中工作，由於IEEE 754浮點數在將其位模式解釋爲整數時正確排序的驚人特性，可以非常方便地使用。

來源

2010-07-13 12:22:12

這是**完全**新對我來說。感謝分享。當我找到時間時，我會閱讀它。 :) – 2010-07-13 12:28:22

偉大的信息！ – 2010-07-13 13:22:17

IEEE浮點數正確地排序爲_sign-magnitude整數，而不是二進制補碼整數。如果你打算對負數進行排序，那麼一種解決方法是補充除高位之外的每一位，而不管後者是否設置。 – user382751 2010-07-13 13:42:00

如果您想排序的算法視覺representetion，看看這個神奇的網站：

Sorting-algorithms.com

你會得到哪些最在不同情況下的感覺，但我最喜歡的是合併排序，儘管它並不比快速排序好。

來源

2010-07-13 12:13:00

理論上來說，你會比較使用big O notation的算法，它可以讓你比較哪種算法對於「幾乎無限」的問題會更快。實際上，在大多數情況下，這是比較算法在現實生活中表現如何的非常好的起點。

兩種最流行的快速排序算法是MergeSort和快速排序。對於任何數據，合併排序保證爲O（n log n），而快速排序的平均時間爲O（n log n）和悲觀時間O（n^2）。在實踐中，大多數人使用快速排序，這是因爲：

這種事幾乎是在自然發生（我想你可以在地方合併排序，但它是單調乏味的，將使其更慢 - 它會增加常量隱藏在O符號） - 對於大數據集，如果數據不適合內存，這是一個問題
在大多數情況下，它在實踐中速度更快
您可以稍微修改它（即取第一，中間和最後的中位數元素進行分區），這樣就很難獲得會使其變慢的數據。

總結我認爲快速排序對於你的隨機浮點數會更快，即使只看O字母看起來更糟 - 因爲你會得到預期的O（n log n），並且它會有比合並更小的常量分類。

來源

2010-07-13 12:15:29 Grzenio

我看到沒有人提到introsort，它通過在遞歸深度超過特定閾值時切換到heapsort來解決快速排序的O(n^2)最壞情況。這意味着快速排序不會有退化的機會，因爲它的遞歸調用次數肯定會受到限制。

只要當前序列中元素的數量很少（比如說16），另一個優化就是切換到insertion sort。

這是內省排序怎麼可能看：

void Introsort(int A[], int N, int left, int right, int depth) 
{ 
    if (left < right) // note: this doesn't switch to insertion sort if right - left is small enough 
    { 
     if ((1 << depth) > N) 
      Heapsort(A, left, right); 
     else 
     { 
      int P = Partition(A, left, right); 
      Introsort(A, N, left, P, depth+1); 
      Introsort(A, N, P+1, right, depth+1); 
     } 
    } 
}

此，具有良好的功能分區組合（只是隨機選擇的支點應該是多數已經足夠了），會給你一個非常快速排序算法。

還有radix sort的選擇，它的效果非常好，尤其是如果你的浮標不太大。不過，從我看到的情況來看，它需要數百萬的基數才能超越內插。

來源

2010-07-13 12:36:26 IVlad

謝謝！我一定會注意到這一點。 :) – 2010-07-13 12:38:51

需要注意的一點是，如果你的任何一個集合都是nan，那麼這個集合不是有序的，而且一些排序算法可能會給出意想不到的結果甚至崩潰。我認爲最好的做法是確保在排序之前，您的數字都不是南。例如（使用gcc 3.4.6）將qsort（升序）應用於{2,1，nan，-1}得到{1,2，nan，-1}。

另一方面，inf和-inf不是問題。

來源

2010-07-13 13:47:13 dmuir

什麼是隨機浮點數的最佳排序算法？

回答

相關問題