已知統計分佈數據的排序算法？

Question

剛纔我想到，如果您對要分類的數據的分佈（從統計角度來說）有所瞭解，那麼如果將這些信息考慮在內，排序算法的性能可能會受益。

所以我的問題是，有任何排序算法考慮到這種信息？他們有多好？

編輯：一個例子來說明：如果您知道數據的分佈是高斯分佈，那麼您可以在處理數據時快速估計均值和平均值。這會給你估計每個數字的最終位置，你可以使用它們將它們放在最接近他們的最終位置。

編輯＃2：我很驚訝，答案並不是維基鏈接到討論這個問題的討論頁面。這不是一個很常見的情況（例如高斯情況）？

編輯＃3：我給這個問題增加了一個賞金，因爲我在尋找有確切答案的來源，而不是猜測。就像「在高斯分佈式數據的情況下，XYZ算法是平均速度最快的，正如Smith等[1]所證實的那樣」。但是，歡迎任何其他信息。

注意：我會獎勵賞金答案最高的答案。明智地投票！

Answer 1

如果您正在排序的數據具有已知分佈，我將使用Bucket Sort算法。您可以添加一些額外的邏輯，以便根據分佈的屬性計算各個桶的大小和/或位置（例如：對於高斯，您可能每隔（σ/ k）距離均值就有一個桶，其中西格瑪是分佈的標準偏差）。

通過以這種方式進行已知分配並修改標準桶排序算法，您可能會得到算法或其他相近的算法。當然，你的算法在計算上比直方圖排序算法快，因爲你可能不需要做第一遍（在鏈接中描述），因爲你已經知道分佈。

編輯：你的問題的給您的新標準，（雖然我以前關於直方圖排序鏈接到可敬NIST和包含的性能信息的答案），這裏是從並行處理國際會議進行同行評審期刊文章：

Adaptive Data Partition for Sorting Using Probability Distribution

作者聲稱該算法具有更好的性能（更好的高達30％），比流行的快速排序算法。

Answer 2

瞭解數據源分佈，可以構建一個好的散列函數。很好地瞭解分佈，哈希函數可能被證明是一個完美的散列函數，或者接近完美的許多輸入向量。

這樣的函數會將大小爲n的輸入分成n個bin，這樣最小的項目將映射到第1個bin中，最大的項目將映射到最後一個bin。當散列是完美的 - 我們將實現排序只是將所有項目插入箱。

將所有項目插入散列表中，然後按照順序提取它們將是O（n），當散列是完美的時（假設散列函數計算成本是O（1），並且下劃線散列數據結構操作是O（1））。

我會使用斐波那契堆數組來實現哈希表。

對於散列函數不完美（但仍然接近完美）的輸入向量，它仍然會比O（nlogn）好得多。當它完美時 - 它會是O（n）。我不知道如何計算平均複雜度，但如果被迫，我會在O（nloglogn）上下注。

Answer 3

您可以在快速排序中使用該信息來選擇樞軸值。我認爲這會提高算法避免O（N ** 2）最差情況複雜度的可能性。

Answer 4

聽起來像你可能想要讀Self-Improving Algorithms：它們實現了任意輸入分佈的最終最佳期望運行時間。

我們得到這樣的自改進算法 爲兩個問題：（ⅰ）排序號碼 序列和（ii）計算 平面 點集的Delaunay三角剖分。兩種算法均實現最佳期望限制複雜度。該算法開始於訓練 階段，在該階段期間，他們收集關於輸入 分佈的信息，隨後是固定的 機制，其中算法將 設置爲其優化的化身。

如果您已經知道您的輸入分佈近似爲高斯，那麼也許另一種方法在空間複雜性方面會更高效，但就預期運行時間而言，這是一個相當不錯的結果。

Answer 5

計算機排序算法可以分爲 兩類，基於比較的排序和非基於比較的排序 。對於基於比較的 排序，其最佳情況下的排序時間爲 Ω（nlogn），而在其最差情況下的排序時間可能上升到O（n2）。近年來， 已提出一些改進的算法，以 加速比較爲基礎的排序，如高級 根據數據分佈特點快速排序 。然而，這些 算法的平均排序時間僅爲Ω（nlog2n），並且只有在最佳情況下才能達到O（n）的 。 與基於比較的排序不同， 非基於比較的排序（如計數排序， 桶排序和基數排序主要取決於密鑰 和地址計算。當密鑰的值爲 有限範圍從1到m時，非基於比較的排序的計算複雜度爲O（m + n）。特別是，當m = O（n）時，排序時間 可以達到O（n）。但是，當m = n2，n3，...時，不能獲得線性排序時間的上限。 在非基於比較的排序中，存儲桶排序 將具有相似關鍵字的一組記錄分配到適當的「存儲桶」中，然後將另一個排序算法應用於每個存儲桶中的記錄。使用存儲桶 排序，將記錄劃分爲m個存儲桶的時間較少，而每個存儲桶中只包含幾條記錄，因此「清理排序」算法可以非常快速地應用。因此，與Ω（nlogn）算法相比， 分類排序有可能漸近節省排序時間。 顯然，如何將所有記錄統一分配到桶中，對桶的排序起着至關重要的作用。因此，您需要的是一種根據數據分佈構造散列函數 的方法，用於根據每個記錄的關鍵字將n個記錄均勻分佈到n個桶中。因此，在任何情況下，所提出的桶排序算法的排序時間將達到O（n） 。

檢查本文：http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

Answer 6

桶排序會給你一個線性時間排序算法，只要你可以計算在O（1）每一個時間點的CDF。

的算法，你也可以看看在其他地方，如下：

a = array(0, n - 1, [])   // create an empty list for each bucket 
for x in input: 
    a[floor(n * cdf(x))].append(x) // O(1) time for each x 
input.clear() 
for i in {0,...,n - 1}: 
    // this sorting step costs O(|a[i]|^2) time for each bucket 
    // but most buckets are small and the cost is O(1) per bucket in expectation 
    insertion_sort(a[i]) 
    input.concatenate(a[i]) 

的運行時間是在預期爲O（n），因爲在預期有O（N）對（X，Y ），使得x和y落入同一個桶中，並且插入排序的運行時間恰好是O（n +＃在同一個桶中）。該分析類似於FKS static perfect hashing。編輯：如果你不知道分佈，但你知道它來自哪個家族，你可以通過計算均值和方差來估計O（n）中的分佈，在高斯情況下，然後使用相同的算法（順便說一下，在這種情況下計算cdf是非平凡的）。

Answer 7

我認爲cycle sort屬於這一類。當你知道每個元素最終的確切位置時，就可以使用它。

Cyclesort有一些很好的屬性 - 對於某些限制類型的數據，它可以在線性時間內進行穩定的就地排序，同時保證每個元素最多隻能移動一次。