你們用排序演算法排序八百萬個數的最快時間是多少？

01-01

1，機器就是普通的個人電腦。
2，演算法不限，
3，所選數使用random()產生。
4，我用的C語言，你們隨意，
我的方法;

使用的是自己寫的快排，遞歸的排序（是否有影響？），用random()產生的待測數據，總共八百萬個。測試方法： time ./a.out &< test_numbers &> /dev/null
該方法測試出來的時間是：4.478秒左右，也不知道是快還是慢，後來又用bublesort測試了一遍，時間太長了就放棄了，
問題1：我的整個方法是否正確？有哪些階段可以改進，虛心求教。
問題2：各位感興趣的話可以貼上自己的代碼，測試方法，優化手段和運行時間，供分享和學習。
感激不盡！

怒答這題，前一陣正好在複習數據結構，於是整理了很多排序演算法。

以下是測試結果：

單位都是毫秒。

顯示「沒有測試」的是因為慢到沒朋友，所以直接跳過了。

Release模式下，開的o2優化：

如果數據元素都不小於0，而且變化範圍不那麼大的話，就可以用各種分散式排序。

對，可以秒殺stdsort，O(n)的演算法不是鬧著玩的。

值得一提的是，debug模式和release模式差別巨大，編譯器的優化非常兇殘：

有的能縮減到原來是不到十分之一也是跪了，stdsort為什麼優化幅度這麼大，這是怎麼樣的黑魔法？

樓主說明一下：像這樣的數據量，如果在最差情況下，標準快排貌似會棧溢出的，所以圖中的「快速排序」是進行過限制遞歸深度的，然後退化成插排（區別於圖中「快排插排混合」，此演算法不僅是混合，還有多種小優化）。

快速演算法的優化可以參考這個：

怎樣讓快速排序更快？_silverbullettt_新浪博客

你這寫法光 IO 的時間就夠嚇人了。。

Jeff Dean教你用O(1/n)演算法在隨機數生成之前將它們排好序。

用猴子排序，憑藉彩票中獎的運氣，只用了0.0000099秒，比PHP哥還快噢

var data = []; var num = 800 * 10000; for(i = 0; i &< num; i++){ data [i] = Math.round(Math.random() * num); } var before = new Date().getTime(); data.sort(function(a,b){return a-b;}); var after = new Date().getTime(); console.log(after - before);

JavaScript，i7 2760QM, Firebug 直接跑的，用時 2133 ms ……

update: 感謝 @賀師俊，默認的 Array.sort() 不是按數值大小順序排的……

有趣的是指定了比較器之後用時比默認的還縮短了……

軟體是MATLAB

我是來抖機靈的，不要打我，求摺疊

看了一下基本都是qsort，其實基數排序很快的。

試了一下用Rust

#[bench] fn test_sort(b: mut test::Bencher) { let mut v = range(0, 800_0000) .map(|_| rand::random::&()) .collect::&&>();

b.iter(|| { v.sort(); }) }

結果是

test test::test_sort ... bench: 571436668 ns/iter (+/- 42809520)

大概是0.5s

是int么？是的話小排無敵

不是的話應該是快排或者堆排序的天下吧

機器不同，這種比較有什麼意義嗎.

數字的可取值數太少，用空間換時間的方式，可以做到O(1)

import time


array = [x for x in range(10000 * 800, 0, -1)]

def fuck(fuckArray):

    start = time.time()

    fuckArray.sort()

    end = time.time()

    return end - start

print fuck(array)

i3+4G 耗時154ms

inline void MySwap(int l, int r) { int t = l; l = r; r = t; }


void MySort(int left, int right, int* data)

{

    if (left + 1 == right) {

        if (data[left] &> data[right]) {

            MySwap(data[left], data[right]);

        }

        return;

    }
    int val = data[right];

int pos = left - 1; for (int i = left; i &< right; i++) { if (data[i] &< val) { MySwap(data[++pos], data[i]); } } MySwap(data[++pos], data[right]); if (left &< pos - 1) { MySort(left, pos - 1, data); } if (pos + 1 &< right) { MySort(pos + 1, right, data); } }

用C++寫的沒有任何優化的版本，其實就是C語言。

Release模式i7跑一秒左右。

==================================================

這樣寫在輸入為逆序時是有問題的。

為了穩妥，關鍵的分割部分要謹慎處理。

Sort Benchmark Home Page

800萬全逆序是360毫秒左右

800萬隨機亂序如圖

感覺歸併還不錯啊

來一個C#的單線程基數排序( 首頁 - C# 高性能自動化服務端框架 - 凹凸架構 )，CPU i5-4570，平均耗時在100ms左右

static unsafe void Main(string[] args) { AutoCSer.Random random = AutoCSer.Random.Default; int[] values = new int[800 * 10000]; do { for (int index = values.Length; index != 0; values[--index] = random.Next()) ; Stopwatch time = new Stopwatch(); time.Start(); AutoCSer.Extension.FixedArraySort.sort(values); time.Stop(); Console.WriteLine(time.ElapsedMilliseconds + "ms"); } while (Console.ReadLine() != "quit"); }

聽說並行基數排序是最快的演算法。

我大PHP 只要0.00001秒

看了這個標題就受不了了，忍不住發個言

話題應該改成：你自己寫的排序演算法能比qsort快多少？

內存足夠，基數排序桶排序等所有時間複雜度為O(n)的演算法挨個上吧…