從上面的引言中，你應該理解，對給定信息得先排序再搜索。本節會介紹一些在計算機科學中最著名的排序算法。我們會從最慢的一個開始，接著是一些性能較好的算法。
在開始排序算法之前，我們先創建一個數組（列表）來表示待排序和搜索的數據結構。
function ArrayList{
var array = ; //{1}
this.insert = function(item){ //{2}
array.push(item);
};
this.toString= function{ //{3}
return array.join;
};
}
如你所見，ArrayList是一個簡單的數據結構，它將項存儲在數組中（行{1}）。我們只需要一個插入方法來向數據結構中添加元素（行{2}），用第2章中介紹的JavaScript Array類原生的push方法即可。最後，為了幫助我們驗證結果，toString方法使用JavaScript原生Array類的join方法，來拼接數組中的所有元素至一個單一的字符串，這樣我們就可以輕鬆地在瀏覽器的控制台輸出結果了。
join方法拼接數組元素至一個字符串，並返回該字符串。
注意ArrayList類並沒有任何方法來移除數據或插入數據到特定位置。我們刻意保持簡單是為了能夠專注於排序和搜索算法。所有的排序和搜索算法會添加至這個類中。
我們現在開始吧！
10.1.1 冒泡排序
人們開始學習排序算法時，通常都先學冒泡算法，因為它在所有排序算法中最簡單。然而，從運行時間的角度來看，冒泡排序是最差的一個，接下來你會知曉原因。
冒泡排序比較任何兩個相鄰的項，如果第一個比第二個大，則交換它們。元素項向上移動至正確的順序，就好像氣泡升至表面一樣，冒泡排序因此得名。
讓我們來實現一下冒泡排序：
this.bubbleSort = function{
var length = array.length; //{1}
for (var i=0; i<length; i++){ //{2}
for (var j=0; j<length-1; j++ ){ //{3}
if (array[j] > array[j+1]){ //{4}
swap(array, j, j+1); //{5}
}
}
}
};
首先，聲明一個名為length的變量，用來存儲數組的長度（行{1}）。這一步可選，它能幫助我們在行{2}和行{3}時直接使用數組的長度。接著，外循環（行{2}）會從數組的第一位迭代至最後一位，它控制了在數組中經過多少輪排序（應該是數組中每項都經過一輪，輪數和數組長度一致）。然後，內循環將從第一位迭代至倒數第二位，內循環實際上進行當前項和下一項的比較（行{4}）。如果這兩項順序不對（當前項比下一項大），則交換它們（行{5}），意思是位置為j+1的值將會被換置到位置j處，反之亦然。
現在我們得聲明swap函數（一個私有函數，只能用在ArrayList類的內部代碼中）：
var swap = function(array, index1, index2){
var aux = array[index1];
array[index1] = array[index2];
array[index2] = aux;
};
交換時，我們用一個中間值來存儲某一交換項的值。其他排序法也會用到這個方法，因此我們聲明一個方法放置這段交換代碼以便重用。
如果使用在第1章學過的ES6（ECMAScript 2015）增強的對象屬性，這個函數可以寫成下面這樣：
[array[index1], array[index2]] = [array[index2], array[index1]];
下面這個示意圖展示了冒泡排序的工作過程：
該示意圖中每一小段表示外循環的一輪（行{2}），而相鄰兩項的比較則是在內循環中進行的（行{3}）。
我們將使用下面這段代碼來測試冒泡排序算法，看結果是否和示意圖所示一致：
function createNonSortedArray(size){ //{6}
var array = new ArrayList;
for (var i = size; i> 0; i--){
array.insert(i);
}
return array;
}
var array = createNonSortedArray(5); //{7}
console.log(array.toString); //{8}
array.bubbleSort; //{9}
console.log(array.toString); //{10}
為了輔助測試本章將要學習的排序算法，我們將創建一個函數來自動地創建一個未排序的數組，數組的長度由函數參數指定（行{6}）。如果傳遞5作為參數，該函數會創建如下數組：[5, 4, 3, 2, 1]。調用這個函數並將返回值存儲在一個變量中，該變量將包含這個以某些數字來初始化的ArrayList類實例（行{7}）。我們在控制台上輸出這個數組內容，確保這是一個未排序數組（行{8}），接著我們調用冒泡排序方法（行{9}）並再次在控制台上輸出數組內容以驗證數組已被排序了（行{10}）。
ArrayList源碼和測試代碼（帶有補充註釋的）。
注意當算法執行外循環的第二輪的時候，數字4和5已經是正確排序的了。儘管如此，在後續比較中，它們還一直在進行著比較，即使這是不必要的。因此，我們可以稍稍改進一下冒泡排序算法。
改進後的冒泡排序
如果從內循環減去外循環中已跑過的輪數，就可以避免內循環中所有不必要的比較（行{1}）。
this.modifiedBubbleSort = function{
var length = array.length;
for (var i=0; i<length; i++){
for (var j=0; j<length-1-i; j++ ){ //{1}
if (array[j] > array[j+1]){
swap(j, j+1);
}
}
}
};
下面這個示意圖展示了改進後的冒泡排序算法是如何執行的：
我們將在第12章詳細介紹大O表示法，對算法做更多的討論。
10.1.2 選擇排序
選擇排序算法是一種原址比較排序算法。選擇排序大致的思路是找到數據結構中的最小值並將其放置在第一位，接著找到第二小的值並將其放在第二位，以此類推。
下面是選擇排序算法的源代碼：
this.selectionSort = function{
var length = array.length, //{1}
indexMin;
for (var i=0; i<length-1; i++){ //{2}
indexMin = i; //{3}
for (var j=i; j<length; j++){ //{4}
if(array[indexMin]>array[j]){ //{5}
indexMin = j; //{6}
}
}
if (i !== indexMin){ //{7}
swap(i, indexMin);
}
}
};
首先聲明一些將在算法內使用的變量（行{1}）。接著，外循環（行{2}）迭代數組，並控制迭代輪次（數組的第n個值——下一個最小值）。我們假設本迭代輪次的第一個值為數組最小值（行{3}）。然後，從當前i的值開始至數組結束（行{4}），我們比較是否位置j的值比當前最小值小（行{5}）；如果是，則改變最小值至新最小值（行{6}）。當內循環結束（行{4}），將得出數組第n小的值。最後，如果該最小值和原最小值不同（行{7}），則交換其值。
用以下代碼段來測試選擇排序算法：
array = createNonSortedArray(5);
console.log(array.toString);
array.selectionSort;
console.log(array.toString);
下面的示意圖展示了選擇排序算法，此例基於之前代碼中所用的數組。
數組底部的箭頭指示出當前迭代輪尋找最小值的數組範圍（內循環{4}），示意圖中的每一步則表示外循環。
選擇排序同樣也是一個複雜度為O(n2)的算法。和冒泡排序一樣，它包含有嵌套的兩個循環，這導致了二次方的複雜度。然而，接下來要學的插入排序比選擇排序性能要好。
10.1.3 插入排序
插入排序每次排一個數組項，以此方式構建最後的排序數組。假定第一項已經排序了，接著，它和第二項進行比較，第二項是應該待在原位還是插到第一項之前呢？這樣，頭兩項就已正確排序，接著和第三項比較（它是該插入到第一、第二還是第三的位置呢？），以此類推。
下面這段代碼表示插入排序算法：
this.insertionSort = function{
var length = array.length, //{1}
j, temp;
for (var i=1; i<length; i++){ //{2}
j = i; //{3}
temp = array[i]; //{4}
while (j>0 && array[j-1] > temp){ //{5}
array[j] = array[j-1]; //{6}
j--;
}
array[j] = temp; //{7}
}
};
照例，算法的第一行用來聲明代碼中使用的變量（行{1}）。接著，迭代數組來給第i項找到正確的位置（行{2}）。注意，算法是從第二個位置（索引1）而不是0位置開始的（我們認為第一項已排序了）。然後，用i的值來初始化一個輔助變量（行{3}）並將其值亦存儲於一臨時變量中（行{4}），便於之後將其插入到正確的位置上。下一步是要找到正確的位置來插入項目。只要變量j比0大（因為數組的第一個索引是0——沒有負值的索引）並且數組中前面的值比待比較的值大（行{5}），我們就把這個值移到當前位置上（行{6}）並減小j。最終，該項目能插入到正確的位置上。
下面的示意圖展示了一個插入排序的實例：
舉個例子，假定待排序數組是[3, 5, 1, 4, 2]。這些值將被插入排序算法按照下面形容的步驟進行排序。
(1) 3已被排序，所以我們從數組第二個值5開始。3比5小，所以5待在原位（數組的第二位）。3和5排序完畢。
(2) 下一個待排序和插到正確位置上去的值是1（目前在數組的第三位）。5比1大，所以5被移至第三位去了。我們得分析1是否應該被插入到第二位——1比3大嗎？不，所以3被移到第二位去了。接著，我們得證明1應該插入到數組的第一位上。因為0是第一個位置且沒有負數位，所以1必須被插入到第一位。1、3、5三個數字已經排序。
(3) 4應該在當前位置（索引3）還是要移動到索引較低的位置上呢？4比5小，所以5移動到索引3位置上去。那麼應該把4插到索引2的位置上去嗎？4要比3大，所以4插入到數組的位置3上。
(4) 下一個待插入的數字是2（數組的位置4）。5比2大，所以5移動至索引4。4比2大，所以4也得移動（位置3）。3也比2大，所以3還得移動。1比2小，所以2插入到數組的第二位置上。至此，數組已排序完成。
排序小型數組時，此算法比選擇排序和冒泡排序性能要好。
10.1.4 歸並排序
歸並排序是第一個可以被實際使用的排序算法。你在本書中學到的前三個排序算法性能不好，但歸並排序性能不錯，其複雜度為O(nlogn)。
Array類定義了一個sort函數（Array.prototype.sort）用以排序JavaScript數組（我們不必自己實現這個算法）。ECMAScript沒有定義用哪個排序算法，所以瀏覽器廠商可以自行去實現算法。例如，Mozilla Firefox使用歸並排序作為Array.prototype.sort的實現，而Chrome使用了一個快速排序（下面我們會學習的）的變體。
歸並排序是一種分治算法。其思想是將原始數組切分成較小的數組，直到每個小數組只有一個位置，接著將小數組歸並成較大的數組，直到最後只有一個排序完畢的大數組。
由於是分治法，歸並排序也是遞歸的：
this.mergeSort = function{
array = mergeSortRec(array);
};
像之前的章節一樣，每當要實現一個遞歸函數，我們都會實現一個實際被執行的輔助函數。對歸並排序我們也會這麼做。我們將聲明mergeSort方法以供隨後使用，而mergeSort方法將會調用mergeSortRec，該函數是一個遞歸函數：
var mergeSortRec = function(array){
var length = array.length;
if(length === 1) { //{1}
return array; //{2}
}
var mid = Math.floor(length / 2), //{3}
left = array.slice(0, mid), //{4}
right = array.slice(mid, length); //{5}
return merge(mergeSortRec(left), mergeSortRec(right)); //{6}
};
歸並排序將一個大數組轉化為多個小數組直到只有一個項。由於算法是遞歸的，我們需要一個停止條件，在這裡此條件是判斷數組的長度是否為1（行{1}）。如果是，則直接返回這個長度為1的數組（行{2}），因為它已排序了。
如果數組長度比1大，那麼我們得將其分成小數組。為此，首先得找到數組的中間位（行{3}），找到後我們將數組分成兩個小數組，分別叫作left（行{4}）和right（行{5}）。left數組由索引0至中間索引的元素組成，而right數組由中間索引至原始數組最後一個位置的元素組成。
下面的步驟是調用merge函數（行{6}），它負責合併和排序小數組來產生大數組，直到回到原始數組並已排序完成。為了不斷將原始數組分成小數組，我們得再次對left數組和right數組遞歸調用mergeSortRec，並同時作為參數傳遞給merge函數。
var merge = function(left, right){
var result = , // {7}
il = 0,
ir = 0;
while(il < left.length && ir < right.length) { // {8}
if(left[il] < right[ir]) {
result.push(left[il++]); // {9}
} else{
result.push(right[ir++]); // {10}
}
}
while (il < left.length){ // {11}
result.push(left[il++]);
}
while (ir < right.length){ // {12}
result.push(right[ir++]);
}
return result; // {13}
};
merge函數接受兩個數組作為參數，並將它們歸並至一個大數組。排序發生在歸並過程中。首先，需要聲明歸並過程要創建的新數組以及用來迭代兩個數組（left和right數組）所需的兩個變量（行{7}）。迭代兩個數組的過程中（行{8}），我們比較來自left數組的項是否比來自right數組的項小。如果是，將該項從left數組添加至歸並結果數組，並遞增迭代數組的控制變量（行{9}）；否則，從right數組添加項並遞增相應的迭代數組的控制變量（行{10}）。
接下來，將left數組或者right數組所有剩餘的項添加到歸並數組中（行{11}和行{12}）。最後，將歸並數組作為結果返回（行{13}）。
如果執行mergeSort函數，下圖是具體的執行過程：
可以看到，算法首先將原始數組分割直至只有一個元素的子數組，然後開始歸並。歸並過程也會完成排序，直至原始數組完全合併並完成排序。
10.1.5 快速排序
快速排序也許是最常用的排序算法了。它的複雜度為O(nlogn)，且它的性能通常比其他的複雜度為O(nlogn)的排序算法要好。和歸並排序一樣，快速排序也使用分治的方法，將原始數組分為較小的數組（但它沒有像歸並排序那樣將它們分割開）。
快速排序比到目前為止你學過的其他排序算法要複雜一些。讓我們一步步地來學習。
(1) 首先，從數組中選擇中間一項作為主元。
(2) 創建兩個指針，左邊一個指向數組第一個項，右邊一個指向數組最後一個項。移動左指針直到我們找到一個比主元大的元素，接著，移動右指針直到找到一個比主元小的元素，然後交換它們，重複這個過程，直到左指針超過了右指針。這個過程將使得比主元小的值都排在主元之前，而比主元大的值都排在主元之後。這一步叫作劃分操作。
(3) 接著，算法對劃分後的小數組（較主元小的值組成的子數組，以及較主元大的值組成的子數組）重複之前的兩個步驟，直至數組已完全排序。
讓我們開始快速排序的實現吧：
this.quickSort = function{
quick(array, 0, array.length - 1);
};
就像歸並算法那樣，開始我們聲明一個主方法來調用遞歸函數，傳遞待排序數組，以及索引0及其最末的位置（因為我們要排整個數組，而不是一個子數組）作為參數。
var quick = function(array, left, right){
var index; //{1}
if (array.length > 1) { //{2}
index = partition(array, left, right); //{3}
if (left < index - 1) { //{4}
quick(array, left, index - 1); //{5}
}
if (index < right) { //{6}
quick(array, index, right); //{7}
}
}
};
首先聲明index（行{1}），該變量能幫助我們將子數組分離為較小值數組和較大值數組，這樣，我們就能再次遞歸的調用quick函數了。partition函數返回值將賦值給index（行{3}）。
如果數組的長度比1大（因為只有一個元素的數組必然是已排序了的（行{2}），我們將對給定子數組執行partition操作（第一次調用是針對整個數組）以得到index（行{3}）。如果子數組存在較小值的元素（行{4}），則對該數組重複這個過程（行{5}）。同理，對存在較大值得子數組也是如此，如果存在子數組存在較大值，我們也將重複快速排序過程（行{7}）。
劃分過程
第一件要做的事情是選擇主元（
pivot），有好幾種方式。最簡單的一種是選擇數組的第一項（最左項）。然而，研究表明對於幾乎已排序的數組，這不是一個好的選擇，它將導致該算法的最差表現。另外一種方式是隨機選擇一個數組項或是選擇中間項。現在，讓我們看看劃分過程：
var partition = function(array, left, right) { var pivot = array[Math.floor((right + left) / 2)], //{8} i = left, //{9} j = right; //{10} while (i <= j) { //{11} while (array[i] < pivot) { //{12} i++; } while (array[j] > pivot) { //{13} j--; } if (i <= j) { //{14} swap(array, i, j); //{15} i++; j--; } } return i; //{16} };在本實現中，我們選擇中間項作為主元（行
{8}）。我們初始化兩個指針：left（低——行{9}），初始化為數組第一個元素；right（高——行{10}），初始化為數組最後一個元素。只要
left和right指針沒有相互交錯（行{11}），就執行劃分操作。首先，移動left指針直到找到一個元素比主元大（行{12}）。對right指針，我們做同樣的事情，移動right指針直到我們找到一個元素比主元小。當左指針指向的元素比主元大且右指針指向的元素比主元小，並且此時左指針索引沒有右指針索引大（行
{14}），意思是左項比右項大（值比較）。我們交換它們，然後移動兩個指針，並重複此過程（從行{11}再次開始）。在劃分操作結束後，返回左指針的索引，用來在行
{3}處創建子數組。swap函數和我們在本章開始為冒泡排序算法實現的相同。我們也可以將此函數替換為以下ES6代碼。[array[index1], array[index2]] = [array[index2], array[index1]];快速排序實戰
讓我來一步步地看一個快速排序的實際例子：
給定數組
[3, 5, 1, 6, 4, 7, 2]，前面的示意圖展示了劃分操作的第一次執行。下面的示意圖展示了對有較小值的子數組執行的劃分操作（注意7和6不包含在子數組之內）：
接著，我們繼續創建子數組，請看下圖，但是這次操作是針對上圖中有較大值的子數組（有1的那個較小子數組不用再劃分了，因為它僅含有一個項）。
子數組（
[2, 3, 5, 4]）中的較小子數組（[2, 3]）繼續進行劃分（算法代碼中的行{5}）：
然後子數組（
[2, 3, 5, 4]）中的較大子數組（[5, 4]）也繼續進行劃分（算法中的行{7}），示意圖如下：
最終，較大子數組
[6, 7]也會進行劃分（partition）操作，快速排序算法的操作執行完成。
10.1.6 堆排序
堆排序也是一種很高效的算法，因其把數組當作二叉樹來排序而得名。這個算法會根據以下信息，把數組當作二叉樹來管理。
索引0是樹的根節點；
除根節點外，任意節點N的父節點是N/2；
節點L的左子節點是2*L；
節點R的右子節點是2*R+1。
舉例來說，可以將數組[3, 5, 1, 6, 4, 7, 2]想像成下面的樹：
堆排序算法實現如下：
this.heapSort = function {
var heapSize = array.length;
buildHeap(array); //{1}
while (heapSize > 1) {
heapSize--;
swap(array, 0, heapSize); //{2}
heapify(array, heapSize, 0); //{3}
}
};
第一步，構造一個滿足array[parent(i)] ≥ array[i]的堆結構（行{1}）。
第二步，交換堆裡第一個元素（數組中較大的值）和最後一個元素的位置（行{2}）。這樣，最大的值就會出現在它已排序的位置。
第二步可能會丟掉堆的屬性。因此，我們還需要執行一個heapify函數，再次將數組轉換成堆，也就是說，它會找到當前堆的根節點（較小的值），重新放到樹的底部。
buildHeap函數實現如下：
var buildHeap = function(array){
var heapSize = array.length;
for (var i = Math.floor(array.length / 2); i >= 0; i--) {
heapify(array, heapSize, i);
}
};
如果對數組[3, 5, 1, 6, 4, 7, 2]調用buildHeap函數，堆的構建過程如下：
最後，heapify函數實現如下：
var heapify = function(array, heapSize, i){
var left = i * 2 + 1,
right = i * 2 + 2,
largest = i;
if (left < heapSize && array[left] > array[largest]) {
largest = left;
}
if (right < heapSize && array[right] > array[largest]) {
largest = right;
}
if (largest !== i) {
swap(array, i, largest);
heapify(array, heapSize, largest);
}
};
堆構造好之後，就可以應用堆排序的算法了，也就是行{2}和行{3}。
10.1.7 計數排序、桶排序和基數排序（分佈式排序）
到目前為止，你已經學習了如何在不借助任何輔助數據結構的情況下對數組進行排序。還有一類被稱為分佈式排序的算法，原始數組中的數據會分發到多個中間結構（桶），再合起來放回原始數組。
最著名的分佈式算法有計數排序、桶排序和基數排序。這三種算法非常相似。