C++中的快速排序很慢

我有9個以矩陣形式存在的值，需要根據這些值計算中值作爲模擬過程的一部分。C++中的快速排序很慢

我在C++中使用快速排序（即qsort（）），這會導致進程運行緩慢（因爲此進程會重複執行幾次）。

有沒有更好的排序算法，我可以使用？

來源

2009-07-30 Bi.

你不需要完全排序值以找到中值：http://en.wikipedia.org/wiki/Selection_algorithm – 2009-07-30 19:27:37

所以你認爲std :: sort會更好。我的樣本量是9或30。 – 2009-07-30 19:49:59

有多離奇。我對什麼樣的數據集總是9和30感興趣。:)對不起，我很討厭。 – 2009-07-30 19:53:24

排序得到的中位數是非常低效的，您可以使用STL nth_element來代替：。

#include <algorithm> 

// Assuming you keep the elements in a vector v of size len 

std::nth_element(v.begin(), v.begin()+len/2, v.end()); 
median = v[len/2]; 

//... or, if the elements are in a simple array v[len], then 

std::nth_element(v, v+len/2, v+len); 
median = v[len/2];

注：nth_element將修改矢量/ array v。Make ac opy首先如果你需要保留原件。

來源

2009-07-30 19:39:00

插入排序..

在小數據集可以使用不同的算法來獲得最佳性能。一旦數據集增長，QuickSort就會閃耀。

有不同的方法。您可以在插入時對數據結構進行排序，並且有對整個數據集進行排序的地方。你只需要找到你的最佳算法。

來源

2009-07-30 19:29:36 Makach

插入排序應該是一個更快的隨機數據smidge，不是嗎？ – 2009-07-30 19:32:30

實際上，當分區或列表的大小變得非常小時，一些快速排序會自動使用選擇排序。 – 2009-07-30 19:34:33

@Jeremy也許這是插入排序... – 2009-07-30 19:35:23

就像一個人提到的那樣，沒有必要完全排序以獲得中位數。
STL有排序算法通常可以執行比較內聯。它還具有比由qsort保證的更智能的算法，其中O（NlgN）的最壞情況爲。

來源

2009-07-30 19:29:42 EFraim

嗨，謝謝。所以我不需要完全排序來獲得中位數？在那種情況下，是否有更好的方法來獲得結果？謝謝。 – 2009-07-30 19:32:51

RE點2：雖然可能在空間上有所折衷。（如二叉樹排序） – 2009-07-30 19:33:11

@Bi：有一個線性算法的中位數 - 請參閱單個評論的鏈接。 – EFraim 2009-07-30 19:35:04

只有9個值？ Quicksort是矯枉過正。

當處理較小的數據集時，可能使用插入排序，冒泡排序或其他更簡單的排序算法。

性能

冒泡排序有最壞情況和平均複雜度都О（N²），其中n是要排序的項目數。存在許多排序算法，其中O（n log n）的最壞情況或平均複雜度明顯更好。甚至其他的О（n²）排序算法，例如插入排序，往往比氣泡排序具有更好的性能。因此，當n很大時，冒泡排序並不是一種實用的排序算法。

但是，您不必按照其他人的建議排序來獲得中位數。

來源

2009-07-30 19:30:07

僅使用快速排序9個值將是相當低效的。對於如此小的樣本量，使用選擇排序或替換排序更好......這些排序方法的開銷很小。

一旦您的樣本量達到閾值（也許是50+），Quicksort和Mergesort會真正發光。

在這些情況下，我會編寫自己的代碼而不是使用內置函數。

來源

2009-07-30 19:30:25

請不要推薦冒泡排序，除了對受虐狂！

對於小數值，插入排序是最好的，它對其他應用程序（幾乎排序的任何長度的數據）有好處。

編輯：清理格式，強調建議的答案。

來源

2009-07-30 19:32:00 agorenst

我知道一位曾經管理大家都知道的軟件公司的大型開發團隊的教授。他告訴我們，他必須去澳大利亞旅行，以解決客戶的表現問題，當他到達那裏時，有一種泡泡式的評論「最終應該改變爲更好的東西」。他說，那天他解僱了這傢伙，爲該公司花費了數千美元的支持。 – 2009-07-30 19:40:33

@jeremy - 我認爲經理和QA應該被解僱 - 而不是開發人員...... – Tim 2009-07-30 19:48:04

@時間是的，我同意。但至少它的威懾力足以讓人知道那裏有人可能會因此而解僱你。 – 2009-07-30 19:51:32

你沒有足夠的值與快速排序的工作，你應該少用先進的算法（例如：冒泡排序，插入排序，... explanation here

有關聯的快速排序的設置，當成本。你沒有足夠的價值，也沒用使用此獸

來源

2009-07-30 19:32:37 Jodi

叫Quicksort一頭野獸是......呃......我不知道。單線算法不能成爲野獸。 – EFraim 2009-07-30 19:38:04

Err，當我谷歌「單行快速排序」是一噸Haskell點擊（和這個問題：P）時唯一得到的。你可以給我一個簡單的快速排序在c + +？ :) – 2009-07-30 19:49:09

std :: sort（）算法幾乎總是比qsort（）更可取。它通常更容易使用，運行速度更快。

如果您想詳細瞭解，實際上有一系列排序算法。 Stroustrup寫入C++編程語言 std :: sort通常不是正確的使用方法。在這種情況下，std :: nth_element（）可能是你想要的。

來源

2009-07-30 19:45:47

C++中的快速排序很慢

回答

相關問題