排序算法是將一系列的值按照順序進行排列的方法。 [TOC] ## 冒泡排序 ### 簡介 冒泡排序（Bubble Sort）是最易懂的排序算法，但是效率較低，生產環境中很少使用。 它的基本思想是： 1. 依次比較相鄰的兩個數，如果不符合排序規則，則調換兩個數的位置。這樣一遍比較下來，能夠保證最大（或最小）的數排在最后一位。 2. 再對最后一位以外的數組，重復前面的過程，直至全部排序完成。 由于每進行一次這個過程，在該次比較的最后一個位置上，正確的數會自己冒出來，就好像“冒泡”一樣，這種算法因此得名。 以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下： 1. 第一位的“3”與第二位的“2”進行比較，3大于2，互換位置，數組變成[2, 3, 4, 5, 1] 。 2. 第二位的“3”與第三位的“4”進行比較，3小于4，數組不變。 3. 第三位的“4”與第四位的“5”進行比較，4小于5，數組不變。 4. 第四位的“5”與第五位的“1”進行比較，5大于1，互換位置，數組變成[2, 3, 4, 1, 5] 。 第一輪排序完成，可以看到最后一位的5，已經是正確的數了。然后，再對剩下的數[2, 3, 4, 1] 重復這個過程，每一輪都會在本輪最后一位上出現正確的數。直至剩下最后一個位置，所有排序結束。 ### 算法實現 先定義一個交換函數，作用是交換兩個位置的值。 ~~~ function swap(myArray, p1, p2){ var temp = myArray[p1]; myArray[p1] = myArray[p2]; myArray[p2] = temp; } ~~~ 然后定義主函數。 ~~~ function bubbleSort(myArray){ var len = myArray.length, i, j, stop; for (i=0; i < len; i++){ for (j=0, stop=len-i; j < stop; j++){ if (myArray[j] > myArray[j+1]){ swap(myArray, j, j+1); } } } return myArray; } ~~~ ## 選擇排序 ### 簡介 選擇排序（Selection Sort）與冒泡排序類似，也是依次對相鄰的數進行兩兩比較。不同之處在于，它不是每比較一次就調換位置，而是一輪比較完畢，找到最大值（或最小值）之后，將其放在正確的位置，其他數的位置不變。 以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下： 1. 假定第一位的“3”是最小值。 2. 最小值“3”與第二位的“2”進行比較，2小于3，所以新的最小值是第二位的“2”。 3. 最小值“2”與第三位的“4”進行比較，2小于4，最小值不變。 4. 最小值“2”與第四位的“5”進行比較，2小于5，最小值不變。 5. 最小值“2”與第五位的“1”進行比較，1小于2，所以新的最小值是第五位的“1”。 6. 第五位的“1”與第一位的“3”互換位置，數組變為[1, 2, 4, 5, 3]。 這一輪比較結束后，最小值“1”已經排到正確的位置了，然后對剩下的[2, 4, 5, 3]重復上面的過程。每一輪排序都會將該輪的最小值排到正確的位置，直至剩下最后一個位置，所有排序結束。 ### 算法實現 先定義一個交換函數。 ~~~ function swap(myArray, p1, p2){ var temp = myArray[p1]; myArray[p1] = myArray[p2]; myArray[p2] = temp; } ~~~ 然后定義主函數。 ~~~ function selectionSort(myArray){ var len = myArray.length, min; for (i=0; i < len; i++){ // 將當前位置設為最小值 min = i; // 檢查數組其余部分是否更小 for (j=i+1; j < len; j++){ if (myArray[j] < myArray[min]){ min = j; } } // 如果當前位置不是最小值，將其換為最小值 if (i != min){ swap(myArray, i, min); } } return myArray; } ~~~ ## 插入排序 ### 簡介 插入排序（insertion sort）比前面兩種排序方法都更有效率。它將數組分成“已排序”和“未排序”兩部分，一開始的時候，“已排序”的部分只有一個元素，然后將它后面一個元素從“未排序”部分插入“已排序”部分，從而“已排序”部分增加一個元素，“未排序”部分減少一個元素。以此類推，完成全部排序。 以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下： 1. 將數組分成[3]和[2, 4, 5, 1]兩部分，前者是已排序的，后者是未排序的。 2. 取出未排序部分的第一個元素“2”，與已排序部分最后一個元素“3”比較，因為2小于3，所以2排在3前面，整個數組變成[2, 3]和[4, 5, 1]兩部分。 3. 取出未排序部分的第一個元素“4”，與已排序部分最后一個元素“3”比較，因為4大于3，所以4排在3后面，整個數組變成[2, 3, 4]和[5, 1]兩部分。 4. 取出未排序部分的第一個元素“5”，與已排序部分最后一個元素“4”比較，因為5大于4，所以5排在4后面，整個數組變成[2, 3, 4, 5]和[1]兩部分。 5. 取出未排序部分的第一個元素“1”，與已排序部分最后一個元素“5”比較，因為1小于5，所以再與前一個元素“4”比較；因為1小于4，再與前一個元素“3”比較；因為1小于3，再與前一個元素“2”比較；因為小于1小于2，所以“1”排在2的前面，整個數組變成[1, 2, 3, 4, 5]。 ### 算法實現 算法的實現如下： ~~~ function insertionSort(myArray) { var len = myArray.length, // 數組的長度 value, // 當前比較的值 i, // 未排序部分的當前位置 j; // 已排序部分的當前位置 for (i=0; i < len; i++) { // 儲存當前位置的值 value = myArray[i]; /* * 當已排序部分的當前元素大于value， * 就將當前元素向后移一位，再將前一位與value比較 */ for (j=i-1; j > -1 && myArray[j] > value; j--) { myArray[j+1] = myArray[j]; } myArray[j+1] = value; } return myArray; } ~~~ ## 合并排序 ### 簡介 前面三種排序算法只有教學價值，因為效率低，很少實際使用。合并排序（Merge sort）則是一種被廣泛使用的排序方法。 它的基本思想是，將兩個已經排序的數組合并，要比從頭開始排序所有元素來得快。因此，可以將數組拆開，分成n個只有一個元素的數組，然后不斷地兩兩合并，直到全部排序完成。 以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下： 1. 將數組分成[3, 2, 4]和[5, 1]兩部分。 2. 將[3, 2, 4]分成[3, 2]和[4]兩部分。 3. 將[3, 2]分成[3]和[2]兩部分，然后合并成[2, 3]。 4. 將[2, 3]和[4]合并成[2, 3, 4]。 5. 將[5, 1]分成[5]和[1]兩部分，然后合并成[1, 5]。 6. 將[2, 3, 4]和[1, 5]合并成[1, 2, 3, 4, 5]。 ### 算法實現 這里的關鍵是如何合并兩個已經排序的數組。具體實現請看下面的函數。 ~~~ function merge(left, right){ var result = [], il = 0, ir = 0; while (il < left.length && ir < right.length){ if (left[il] < right[ir]){ result.push(left[il++]); } else { result.push(right[ir++]); } } return result.concat(left.slice(il)).concat(right.slice(ir)); } ~~~ 上面的merge函數，合并兩個已經按升序排好序的數組。首先，比較兩個數組的第一個元素，將其中較小的一個放入result數組；然后，將其中較大的一個與另一個數組的第二個元素進行比較，再將其中較小的一個放入result數組的第二個位置。以此類推，直到一個數組的所有元素都進入result數組為止，再將另一個數組剩下的元素接著result數組后面返回（使用concat方法）。 有了merge函數，就可以對任意數組排序了。基本方法是將數組不斷地拆成兩半，直到每一半只包含零個元素或一個元素為止，然后就用merge函數，將拆成兩半的數組不斷合并，直到合并成一整個排序完成的數組。 ~~~ function mergeSort(myArray){ if (myArray.length < 2) { return myArray; } var middle = Math.floor(myArray.length / 2), left = myArray.slice(0, middle), right = myArray.slice(middle); return merge(mergeSort(left), mergeSort(right)); } ~~~ 上面的代碼有一個問題，就是返回的是一個全新的數組，會多占用空間。因此，修改上面的函數，使之在原地排序，不多占用空間。 ~~~ function mergeSort(myArray){ if (myArray.length < 2) { return myArray; } var middle = Math.floor(myArray.length / 2), left = myArray.slice(0, middle), right = myArray.slice(middle), params = merge(mergeSort(left), mergeSort(right)); // 在返回的數組頭部，添加兩個元素，第一個是0，第二個是返回的數組長度 params.unshift(0, myArray.length); // splice用來替換數組元素，它接受多個參數， // 第一個是開始替換的位置，第二個是需要替換的個數，后面就是所有新加入的元素。 // 因為splice不接受數組作為參數，所以采用apply的寫法。 // 這一句的意思就是原來的myArray數組替換成排序后的myArray myArray.splice.apply(myArray, params); // 返回排序后的數組 return myArray; } ~~~ ## 快速排序 ### 簡介 快速排序（quick sort）是公認最快的排序算法之一，有著廣泛的應用。 它的基本思想很簡單：先確定一個“支點”（pivot），將所有小于“支點”的值都放在該點的左側，大于“支點”的值都放在該點的右側，然后對左右兩側不斷重復這個過程，直到所有排序完成。 具體做法是： 1. 確定“支點”（pivot）。雖然數組中任意一個值都能作為“支點”，但通常是取數組的中間值。 2. 建立兩端的指針。左側的指針指向數組的第一個元素，右側的指針指向數組的最后一個元素。 3. 左側指針的當前值與“支點”進行比較，如果小于“支點”則指針向后移動一位，否則指針停在原地。 4. 右側指針的當前值與“支點”進行比較，如果大于“支點”則指針向前移動一位，否則指針停在原地。 5. 左側指針的位置與右側指針的位置進行比較，如果前者大于等于后者，則本次排序結束；否則，左側指針的值與右側指針的值相交換。 6. 對左右兩側重復第2至5步。 以對數組[3, 2, 4, 5, 1] 進行從小到大排序為例，步驟如下： 1. 選擇中間值“4”作為“支點”。 2. 第一個元素3小于4，左側指針向后移動一位；第二個元素2小于4，左側指針向后移動一位；第三個元素4等于4，左側指針停在這個位置（數組的第2位）。 3. 倒數第一個元素1小于4，右側指針停在這個位置（數組的第4位）。 4. 左側指針的位置（2）小于右側指針的位置（4），兩個位置的值互換，數組變成[3, 2, 1, 5, 4]。 5. 左側指針向后移動一位，第四個元素5大于4，左側指針停在這個位置（數組的第3位）。 6. 右側指針向前移動一位，第四個元素5大于4，右側指針移動向前移動一位，第三個元素1小于4，右側指針停在這個位置（數組的第3位）。 7. 左側指針的位置（3）大于右側指針的位置（2），本次排序結束。 8. 對 [3, 2, 1]和[5, 4]兩部分各自不斷重復上述步驟，直到排序完成。 ### 算法實現 首先部署一個swap函數，用于互換兩個位置的值。 ~~~ function swap(myArray, firstIndex, secondIndex){ var temp = myArray[firstIndex]; myArray[firstIndex] = myArray[secondIndex]; myArray[secondIndex] = temp; } ~~~ 然后，部署一個partition函數，用于完成一輪排序。 ~~~ function partition(myArray, left, right) { var pivot = myArray[Math.floor((right + left) / 2)], i = left, j = right; while (i <= j) { while (myArray[i] < pivot) { i++; } while (myArray[j] > pivot) { j--; } if (i <= j) { swap(myArray, i, j); i++; j--; } } return i; } ~~~ 接下來，就是遞歸上面的過程，完成整個排序。 ~~~ function quickSort(myArray, left, right) { if (myArray.length < 2) return myArray; left = (typeof left !== "number" ? 0 : left); right = (typeof right !== "number" ? myArray.length - 1 : right); var index = partition(myArray, left, right); if (left < index - 1) { quickSort(myArray, left, index - 1); } if (index < right) { quickSort(myArray, index, right); } return myArray; } ~~~ ## 參考鏈接 * Nicholas C. Zakas,?[Computer science in JavaScript: Bubble sort](http://www.nczonline.net/blog/2009/05/26/computer-science-in-javascript-bubble-sort/) * Nicholas C. Zakas,?[Computer science in JavaScript: Selection sort](http://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/) * Nicholas C. Zakas,?[Computer science in JavaScript: Insertion sort](http://www.nczonline.net/blog/2012/09/17/computer-science-in-javascript-insertion-sort/) * Nicholas C. Zakas,?[Computer science in JavaScript: Merge sort](http://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/) * Nicholas C. Zakas,?[Computer science in JavaScript: Quicksort](http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/)