Sadece aklıma, eğer bildiğiniz bir şey hakkında dağılımı (istatistiksel anlamda) veri sıralama, performans bir sıralama algoritması olabilir parası alırsın o bilgiyi hesabı.

Benim sorum ise şu, dikkate bu tür bilgiler, herhangi bir sıralama algoritması var mı? Onlar ne kadar iyi?

Edıt : açıklığa kavuşturmak için bir örnek: eğer verilerin dağılımı Gauss biliyorsanız, verileri işlemek gibi. yani tahmin ve anında ortalama edebilirsin Bu onları son konumlarını yakın bir yerde kullanmak her sayının son konumu, tahmini bir fiyat verecek.

Edit #2: cevap thourough bir sayfa bu sorunu tartışmak için wiki bir bağlantı olmadığına şaşırdım oldukça. Bu çok yaygın bir durum (Gaussian durumda, örneğin) değil mi?

Kaynakları ile kesin cevaplar arıyorum çünkü bu soru için bir ödül ekleyerek, ben, spekülasyon değil. Edit #3: Bir şey Smith ve ark tarafından kanıtlandı "olarak bağımsız rassal veri durumunda, XYZ algoritması ortalama en hızlısıdır. [1]". Ancak herhangi bir ek bilgi hoş geldiniz.

Not: Bounty oy en yüksek ödül cevap vereceğim. Akıllıca oy!

Eğer sıralama verileri bilinen bir dağıtım varsa, kullanmak istiyorumBucket Sortalgoritma. Sen-ebil eklemek fazladan mantığı bu şekilde hesaplanan boyutu ve/veya pozisyonların çeşitli kovalar dayalı özelliklerinin dağılımı (ex: Gauss, belki senin de bir kova her (sigma/k) uzak dur demek, nereye sigma standart sapma dağılımı).

Bilinen bir dağıtım olması ve standart Kova Sıralama bu şekilde algoritmasını değiştirerek, muhtemelen olacaktıHistogram Sortalgoritma ya da buna yakın bir şey. Elbette, algoritma olacağını hesaplama daha hızlı daha Histogram Sıralama algoritması çünkü orada ki muhtemelen değil, bir ilk geçiş (açıklanan bağlantı) beri zaten bildiğiniz dağılımı.

Düzenleme:verilen yeni bir ölçüt değil (gerçi benim önceki cevap ile ilgili Histogram Tür bağlantılar için saygın MAKİNE ve performans bilgilerini içeren), burada bir hakemlik journal makalesinden Uluslararası Konferansa Paralel İşleme:

Adaptive Data Partition for Sorting Using Probability Distribution

Yazarlar bu algoritma popüler Hızlı Sıralama Algoritması daha iyi performans (0 daha iyi) iddia ediyor.