一. 演算法

高德納在《計算機程序設計藝術》里對演算法歸納為以下幾點：

1. 輸入: 一個演算法必須有零或以上的輸入量
2. 輸出: 一個演算法應有一個或以上的輸出量
3. 明確性: 演算法的描述必須無歧義,實際運行結果是確定的
4. 有限性: 必須在有限個步驟內結束
5. 有效性: 又稱可行性,能夠被執行者實現

如果想詳細研究演算法推薦《數據結構與演算法分析》

二. 定義問題

也就是需求:

數組array含有N個正整數

輸入量為array

代碼例子

var array = [5,2,4,6,8]function sort(){ 你的代碼}sort(array) // [2,4,5,6,8]

當你遇到思路障礙怎麼辦?

• 將抽象的問題轉化為具體的問題
• 將沒見過的問題轉化為見過的問題

三. 排序演算法

所有演算法都可在此查看演示

1. 冒泡排序(BUBBLE)

重複地比較要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。比較數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。每比較一整輪,最大的都會出現在最後故名---冒泡排序

流程如下:

1. 我們拿到一個數組

   

2. 開始從前兩個開始比較,發現44>3,所以不用交換

   

3. 接著往後比較,發現38<44,所以交換他們兩個的位置

   

4. 以此類推直到第一輪結束,我們得到了最大的那一個----50(冒的第一個泡)

   

   第一輪結束

5. 接著下一輪,又從頭開始兩個兩個地比較,重複第一輪,我們就得到了第二個最大的------48

   

   第二輪結束

6. 如此進行多輪比較我們會得到一個從小到大的數組

   

2. 選擇排序(SELECT)

每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。

1. 拿到一個數組

   

2. 我們要選出這個數組中最小的元素然後把它和第一個數交換(放到最前面),所以我們先認為3為最小,然後和後面的數依次進行比較.

   

3. 當比到2的時候,我們發現3>2,所以我們就認為2為最小值,後面的數應該都和2進行比較.

   

4. 當比較完所有的元素,確定2為最小值的時候,把最小值也就是2與第一個元素的位置互換.

   

5. 然後從第二個元素開始新一輪的比較,過程和第一輪一樣.把44看做最小值和後面的元素進行比較.

   

6. 經過多輪比較得到從小到大的數組.

   

3, 插入排序(INSERT)

將一個數據插入到已經排好序的有序數據中，從而得到一個新的、個數加一的有序數據，演算法適用於少量數據的排序。是穩定的排序方法。

1. 拿到一個數組

   

2. 把第一個元素看做一個新數組,然後把第二個元素依次和新數組的元素進行比較(雖然只有一個...),然後插入到適當的位置.

   

   與新數組的元素進行比較

   

   插入到適當的位置

3. 然後以此類推,把前兩個元素看做是一個新數組,然後把第三個元素依次與新數組進行比較,然後插入到適當的位置.

   

   比較

   

   插入適當的位置

4. 把剩下的元素依次插入,最後得到從小到大排列的數組.

   

4. 歸併排序(MERGE)

將已有序的子序列合併，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。

1. 拿到一個數組

   

2. 我們把數組平均分成左右兩部分,得到兩個新數組,然後再把每個數組平均分成兩部分,一直分到每個數組只有兩個元素,然後比較第一組

   

3. 因為3<44所以位置不變然後比較第二組,因為38>5所以調換位置.

   

4. 重點來了,這個時候先不著急比較第三組而是把排好序的一二兩組放在一起排序.

   

5. 之後就是比較第三組和第四組,然後同樣把他們放在一起排好序.

   

6. 然後並不是比較第五組和第六組,而是把第一組和第二組產生的新數組和第三組和第四組產生的新數組放在一起排序成為新數組.

   

7. 同樣把剩下的按以上步驟重來一遍.我們得到兩個排好序的數組.然後給這兩個數組排序就完成了.

   

   排序後:

   

5. 快速排序

每個元素找到自己對應的位置(前面的都比我小,後面的都比我大)

1. 拿到一個數組

   

2. 拿第一個元素和後面的元素進行比較,找出所有比第一個元素小的元素,放在第一個元素的右邊然後把第一個元素與這些比他小的元素的最後一個互換.

   

   只有2比3小

   

   互換

3. 前兩個元素的位置已經沒錯了,然後以第三個元素為標準,和後面的元素進行比較.

   

4. 把比他小的元素放在他的右邊(綠色),然後讓它和綠色的最後一個交換位置.

   

5. 然後從左邊沒有確定位置的元素(非橙色)開始以上步驟----也就是19

   

6. 一直到所有元素的位置都正確.

   

6. 隨機快速排序

顧名思義,就是在快速排序的基礎上,加入隨機的機制.

1. 拿到一個數組

   

2. 隨機選擇一個元素,隨機選擇到了44.

   

3. 並且把比他小的放在他的右邊

   

4. 然後把他和比他小的最右邊的元素交換位置

   

5. 然後在隨機選一個元素,重複步驟,直到所有元素都是在正確的位置

   

推薦閱讀：