試問和直接選擇排序比起來，簡單選擇排序的意義何在？

01-05

理解不了為什麼簡單選擇排序一定要畫蛇添足地多加一個變數，相較之下直接選擇排序就合情合理得多。感謝每一個用真知為我解惑的大佬。。

首先關於題主的問題。說實話，我不知道直接選擇排序和簡單選擇排序有何區別。

但是，在初學階段，有一些疑惑是要人命的。

因此，這篇回答具有普遍意義，希望能解答初學者的疑惑。

〇、一個演算法有多種本質相同的實現形式。

e.g. 以下兩種做法都可以取出最大值：

// Algo 1 for(i=1;i&<=n;i++) if(a[i]&>=maxx) maxx=a[i]; printf("Max = %d ",maxx);

// Algo 2 for(i=1;i&<=n;i++) if(maxx&<=a[i]) { // 搞一些雜七雜八而無關緊要的事情 maxx=a[i]; } printf("Max = %d ",maxx);

我們不會說「這是兩個不同的演算法」，因為它們的本質是相同的。

題目描述的說法是：簡單選擇排序「多加了一個變數」。其實有一點需要澄清：

演算法沒有規定變數要開多少個。「多加了一個變數」是針對某一種實現而言。

演算法只規定了開變數的「規模」。譬如，開n個變數，空間複雜度是 $O(n)$ ；開2n+100個變數，空間複雜度也是 $O(n)$ 。

因此題目描述的問題是不存在的。

題目所述的兩種排序方式，只是「選擇排序」這一演算法的兩種不同實現而已。

一、任何演算法都有其適用範圍、優點和缺點。

譬如，如果您有1000個同事，您需要對他們的月薪排序。那麼此時用快排比較好。

但是，如果您手頭已經有了這1000個人的月薪表格（有序的），此時加入一位新同事，最好使用插入排序。（一次插入是 $O(n)$ 的，快排仍然是 $O(n log n)$ ，浪費複雜度）

如果您的同事總喜歡到處亂跑，以至於天天都有人加入或者離開，您可以考慮用平衡樹：對於每個人的加入或離開，複雜度都是 $O(log n)$ 。

如果您的同事喜歡在一瞬間內跑來跑去，您可能需要支持高並發的平衡樹。這時候跳錶（skiplist）就能派上用場，因為能很好地支持高並發。然而上一個問題我們並不傾向於用跳錶，因為相比起紅黑樹、Treap之類的常規平衡樹，跳錶的速度比較慢。

從上面那一攬子事情可以看出：沒有最好的演算法，只有最合適的演算法。

二、有些問題不需要深究其內涵。

教材中介紹的各種演算法，不要直接相信「這就是最好的」或者「這是合理的」。

實際上，教材可能介紹各種演算法，這些演算法有的您可能天天寫，有的您可能只在這地方見過。

其實題主提這個問題的時候，就應該有了這一個信念：「這玩意肯定有優勢，但是我沒有發現」。

實際上，這種想法是不必要的。

這個問題有點難講清楚，試舉一個例子。基於上述信念，我們也許會提出下面這個問題：

「試問和豎式乘法比起來，格子乘法的意義何在？」

事實上格子乘法相比豎式乘法確實沒什麼優勢，但是我們也可以強行搞一個優勢出來：

「在編程實現高精度乘法的時候，格子乘法的思路更接近演算法的本質。」

自此，所問的問題就解決了：

實用的排序演算法有四種：插入、快速、歸併、堆。

其餘的都不值得深究。

理解不了為什麼要有這些O(n^2)的排序演算法，相比較之下快速排序或者歸併排序的O(nlogn)時間複雜度明明更加優越。

這些都是學習語言的時候的練習題罷了，看懂了表示你已經會用循環實現簡單的排序演算法了，不必深究。

了解歷史的進程+1

但是話說回來，演算法不是那麼死板的東西，多一個變數少一個變數並不影響我們對於一個演算法的辯識。常數優化罷了

了解歷史的進程。

讓我想起了高中政治老師的一句話：存在即合理！但似乎這個世界上對於程序開發來說，存在即合理嗎？又要從狹義和廣義兩個方面做討論，在科技界隱含了一個規則，就是早些年不適用不合理的技術，現在這個時代又流行起來，現在就行的的技術在將來也許又不適用了。

總結就是：適合的就是最好的！