MATLAB中排序函數(Sort)為什麼在數據量巨大時運算時間依然很短？

01-05

用MATLAB對長為100000的一維數組排序，顯示運算時間為0.003s左右，而我自己嘗試寫出的快速排序程序卻要運行6s左右，為什麼會差這麼多？
---------------------------
查閱資料我稍微優化了一下程序，對於100000的數據量等達到5s左右，附上快排函數：
function y=qs1(x,p,q) y=x; if p&>=q return else key=y(p); i=p; j=q; while i~=j while i&=y(i) i=i+1; end y(j)=y(i); end y(i)=key; y=qs1(y,p,i-1); y=qs1(y,i+1,q); end end

目前版本的 MATLAB 的 sort 不是用 MATLAB 語言實現的，具體的演算法可以看這篇文章介紹：

An Adventure of Sorts

不過你這裡寫的快排能比內置的 sort 慢 200 倍，應該在實現方面也有改進的餘地，但看不到你的代碼也沒法具體討論

---------------------------

@李昊鵬看到你更新了代碼，測試了一下：

&>&> x = rand(1,1e5); &>&> tic, a = qs1(x,1,numel(x)); toc 時間已過 4.082604 秒。

將前兩行：

function y=qs1(x,p,q) y=x;

改為一行：

function y=qs1(y,p,q) % 下一行刪除，即只保留這一行

重新測試：

&>&> tic, b = qs1(x,1,numel(x)); toc 時間已過 0.052448 秒。

後面演算法的具體過程也有一些改進餘地，不過應該沒有上述改動明顯。

不過這種影響應該在 2015b 及之後的版本中才會體現。

對於老版本，由於手頭沒有，所以在

Anycodes - MATLAB - R2013B

試了下

julia/perf.m at master · JuliaLang/julia · GitHub

中的 qsort 代碼，對比你的代碼大概快 4 倍左右，當然這個代碼在新版本也會比上邊修改過前兩行的代碼要快一些

1. matlab 寫的快排比 C 寫的慢大概 20 倍

2. 默認的 sort 不是純粹的快排，它包括了

2.1 數據量比較小的時候用貓泡排序

[圖片：貓泡排序示意圖]

2.2 pivot 不能很好的分割兩邊的時候，使用堆排序3. 不是特別重要的一個：默認的 sort 的 pivot 不僅僅是首尾，我記得是首尾和中間取一個

4. 我不知道是否重要：你試著用 -nodesktop 運行一下？

我記得你可以參考 GCC 或者 Borland 默認的 CPP STL 的 sort，現在 VS 的 sort 怎樣我不清楚

題主用的快排是教科書上的版本

這個版本比較基準點選擇的是端點 key=y(p);

在數據有序的情況話時間會退化到n^2

為了保證每次都能把數據儘可能的分成等大的兩部分

一般都是選隨機點最為比較基準點

大部分的 Matlab built in 都只是用 C/C++ 實現後封裝個 API 的。很多時候還會多核甚至用上 GPU。

寫 Matlab 代碼的精髓在於時刻牢記它是 Interpretive Language，所以能用 built in 的不要自己寫，同時還要用 Functional 的思維，能 map reduce accumulate 的不要用循環，因為循環不夠 parallelisation friendly，當然說不定以後他會走 OpenMP 那一套搞出個能並行化循環的語法。

所以你看網上大部分的 Matlab 代碼都是一行一行的調調函數存存結果，沒什麼 nested structure。配合上 Matlab 醜陋的函數命名，真正實現了媲美正則表達式的 write once and unreadable everywhere。當然 Numpy 為了照顧那幫非 CS 的科學家們，不甘示弱地做了一套同樣丑的 API 命名。

會不會是每次遞歸到下一個函數都傳遞了很長很長的一個變數過去所以就慢了？但是嘗試了 global 很慢，用 persistent 連用都用不了。

當遞歸改為 y = [ qs3(y(y &< y(1))) y(y == y(1)) qs3(y((y &> y(1)))) ];時好像快了很多，它往下傳遞的數組越來越小了，雖然會存在拼接很多個數組的情況，但是拼接數組的時間看起來比傳遞數組的時間要小一些。

--------qs3：

function y=qs3(y)

if numel(y)&<2

return

elseif numel(y)==2

if y(1)&>y(2)

y=[y(2) y(1)];

end

return

else

y=[qs3(y(y&y(1))))];

end

----------

感謝Falccm 的回答，打開了新世界的大門。

用時(這樣計時不曉得對不對)：

qs1:題主 qs2: Falccm的改進 qs3: 上面的那個 qs4:加了一個key=median(y(1:3)),後續對key作比較 qs5:直接令 key=median(y);後續對key作比較。

回答總結：

1.遞歸傳遞的變數每次都一樣大，導致傳遞變數用時較長。

2.通過循環數組索引來進行比較導致定址時間太長， y(y&&>&>&>Untitled3:

clear all

x = rand(1,1e5);

a = qs1(x,1,numel(x));

a1 = qs2(x,1,numel(x));

a2=qs3(x);

a3=qs4(x);

a4=qs5(x);

a5=sort(x);

上面的 profile Summary 里沒有出現 sort &>&>&>&>&>&>這個新世界的大門的門把手看來要先去一樓的網址里找一下。。。

一般情況下，單純應用一種排序法並不是最優的，你可以先用快速排序法把數組分類，然後再用用別的排序法，比如插入排序法，但是我也不敢確定就快，這個估計應用演算法的時間複雜度分析，如何把各種排序法混合到一起，達到一個最快的排序法。

用matlab寫肯定慢。

1，快排需要for循環

2，快排需要在for循環遞歸

這兩個東西都是matlab做的比較慢的事情。

題主用自己寫的c快排和matlab系統的來比較合適嗎……

同樣演算法，不同人寫性能可以是雲泥之別啊……雖然一般只是係數的區別。

你用c寫一個快排對比一下就知道了

你的快速排序是用matlab寫的嗎？肯定是因為就應該那麼快，matlab的循環故意拖延時間，好讓內置函數顯得快一些

-------------------------------------------------------------------------------------------------

另一個回答是你寫的函數定址花了太長的時間。試試下邊幾鍾寫法的運行時間，就像回字有四種寫法一樣是不是？

x=rand(1e4);

tic

x=x.^2;

toc

tic

for i=1:1e8

x(i)=x(i)^2;

end

toc

tic

for i=1:1e4

for j=1:1e4

x(j,i)=x(j,i)^2;

end

toc

tic

for i=1:1e4

for j=1:1e4

x(i,j)=x(i,j)^2;

end

toc