2010年6月8日（最後更新：2010年6月8日）

排序演算法

評分：3.3/5（66 票）
*****
引言
 在常見的程式設計中，你通常不會發現自己需要直接進行排序。使用者通常會希望按照給定的順序獲取資訊，這是有原因的。但是，如果使用者希望以某種特定的順序進行排序，你該怎麼做呢？

假設你有 1 美元、5 美元、10 美元、20 美元和 50 美元的鈔票，順序是 50 - 10 - 20 - 1 - 5。作為人類，我們可以很容易地將這些錢按從小到大或從大到小的順序排列。但我們理所當然地認為這種常見做法的實際操作。

當我們嘗試透過機器程式碼來實現一個時，我們會遇到代數方程、遞迴函式，以及我們從未見過的數字。我們不能像用我們的大腦那樣簡單地按順序排列，即使這看起來很容易。但是，我們可以模擬我們如何整理我們的美元鈔票。

例如，拿出美元鈔票並嘗試對它們進行排序。預設情況下，並且按照你的本性，你的大腦應該已經告訴你遵循某種模式。我的大腦告訴我最高的數字是 50 和 1，然後將它們放在各自的位置。然後我尋找相等或更低的值，並將其放在下面，然後繼續迭代尋找更多相同值或更低的值，直到我找到最低的。然後我嘗試迭代，尋找第二個最低的，然後是下一個最高的，依此類推，直到它被整理好。

在這方面實現它很容易，但說實話，它通常不是很有效。我們的大腦選擇了一條簡單的路線，因為它有能力在毫秒內計算出來，我們通常無法區分。如果我們的大腦選擇了一種太難的模式來整理鈔票，它會選擇另一種更簡單的路徑，或者會以不同的方式繼續按照相同的模式進行。但是，你永遠不會透過數字排序來更改演算法，並且你始終在嘗試找到最最佳化和最快的編碼方法。這就是演算法文章存在的原因。它不僅展示了不同的演算法，還展示了它背後的數學原理以及在哪裡應用它們。


術語和概念
 你可能需要知道的一些術語和概念，我不會親自解釋，因為我不是真正教概念的人，而是更多地在我自己的小世界中理解它。相反，我將為你提供在哪裡尋找對概念和術語的理解的方向，從大 O 符號開始。

大 O 符號只是用數學方法來表達函式完成所需的時間：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
你需要理解的另一個概念是演算法複雜度，這是對演算法難度的判斷，通常衡量演算法的空間和時間。維基百科上有一個更好的資訊來源：http://en.wikipedia.org/wiki/Computational_complexity_theory#Machine_models_and_complexity_measures
我個人和誠實地說，我並不瞭解所有關於它的知識，只足以理解複雜性的衡量標準。另一篇值得一看的文章是：http://www.progressive-coding.com/tutorial.php?id=1
另一個要理解的概念是演算法穩定性，它是演算法保持排序陣列中相同值的元素相對位置的能力。例如，你有兩張 5 美元的鈔票，它們需要被排序，一張上面有一個複選標記，另一張沒有。在一個穩定的演算法中，在前面的那個仍然會在排序後在前面。這被認為是擁有一個穩定的演算法。在大多數情況下，它不是必需的，但是在你有一個附加到你想要排序的值陣列的第二個值的情況下，必須理解演算法穩定性以及它如何影響你。

最後但並非最不重要的是演算法適應性。這是演算法接受一個已經部分排序的陣列，並能夠從它離開的地方繼續，並且比它沒有預先排序的情況下更快完成的能力。這通常是一個很大的問題，因為它可以成倍地節省你的時間。

一旦你理解了這些術語和概念的基礎知識，你就可以跟隨和比較不同的演算法，並理解為什麼我選擇一種演算法而不是另一種。


比較排序演算法
 現在最常用的演算法型別稱為比較排序，它是一個通用的演算法類別。它所指的就是演算法將一個元素與另一個元素進行比較，並根據該比較的結果做出反應以對陣列進行排序。

一種常見的比較排序是氣泡排序，它是比較排序的一個子類，稱為交換排序，它包括交換相鄰的項直到排序完成

http://codepad.org/YeU6tmzB 稍微最佳化版本：http://codepad.org/YCJpEFMN
它通常效率低下，僅用於簡單的教育目的。該演算法的平均複雜度為 O(n^2)，這意味著它在較大的列表上非常糟糕。在陣列已經排序的情況下，最佳情況下的複雜度為 O(n)。但是，它易於實現、穩定且具有適應性。

比這種排序更進一步的是插入排序，它本身就是一種型別和排序，並且有很多變體。它比氣泡排序效率更高，儘管複雜度通常為 O(n^2)，就像我們談到的效率低下的氣泡排序一樣。它比氣泡排序有很多優勢，但其中大部分不足以在更大的列表上常用。它也更復雜一些。

http://codepad.org/UUZqOqC9
bbl，得早點起床。
它沒有完成，但感謝你的直率 Bazzy。至少你給出了理由，不像有些人。

1) 我將描述它們的複雜性，可能還有大 O 符號......我遺漏了很多東西。
2) 我沒有評論，因為我沒找到在哪裡評論。如果你能為我評論，那就太好了。
3) 我解釋了它們是靈活的，並且可以與其他型別一起使用，這就是我使用模板來給出一個示例的原因。
4) 我使用了 codepad，這樣我就可以給出帶有結果的完整工作程式，而不使用我的措辭限制。

bbl，必須跑了。