今天重溫一下算法，其實剛開始我覺得冒泡排序和選擇排序是一樣的，因為他們排序過程中都是通過相鄰的數據比較找到最小/最大的數據，通過不斷思考和學習才明白，兩者還是有區別的。

冒泡排序

概念

冒泡排序(Bubble Sort)，可以說是知名度最高也是特別特別重要的經典排序算法。

冒泡排序和選擇排序都屬于交換排序算法的一種。所謂交換排序算法，是指在排序過程中，要發生數組元素的交換。

之所以要把該算法稱為“冒泡算法”，這是因為每個大的元素，每次經過交換都會慢慢“浮”到數組的頂端，故名“冒泡排序”。

冒泡排序的核心思想，是把相鄰的元素進行兩兩比較，當一個元素大于右側相鄰的元素時，就交換它們的位置；當一個元素小于或等于右側相鄰的元素時，則保持位置不變。

注意：冒泡排序只會操作相鄰的兩個數據。每次冒泡操作都是對相鄰的兩個元素進行比較，看是否滿足大小關系。

實現步驟

接下來我們就以一個數值型的數組為例，向大家介紹冒泡排序的整個排序過程。

我們現在定義一個數組，其數組元素值依次為[5，8，6，3，9，2，1，7]。

如果我們采用冒泡排序算法，按從小到大的規則對其排序，其詳細過程會如下所示：

1. 將5和8進行比較，因為滿足左小右大的規則，不需要交換，保持元素位次不變；
2. 將8和6進行比較，因不滿足左小右大的規則，則需要交換。將8和6位置互換，互換位置后，元素6在下標1這個位置上，元素8在下標2這個位置上；
3. 接著將8和3進行比較，不滿足左小右大規則，需要交換。將8和3位置互換，互換位置后，元素3在下標2的位置上，元素8在下標3的位置上；
4. 繼續將8和9進行比較，滿足左小右大規則，不需要交換，保持元素位次不變；
5. 將9和2進行比較，不滿足左小右大的規則，需要交換。將9和2位置互換，互換位置后，元素2在下標4的位置上，元素9在下標5的位置上；
6. 將9和1進行比較，不滿足左小右大的規則，需要交換。將9和1位置互換，互換位置后，元素1在下標5的位置上，元素9在下標6的位置上。
7. 繼續將9和7進行比較，不滿足左小右大的規則，需要交換。互換位置后，元素7在下標6的位置上，元素9在下標7的位置上。

如果我們把上述的文字描述，轉換為圖片，則會如下圖所示：

這樣就完成了第一輪的交換比較。經過第一輪交換后，元素9作為數列中最大的元素，就像是汽水里的氣泡一樣浮到了最右側。接著我們繼續如此重復上述的比較過程，每一輪結束后，都會有一個本輪最大的元素被移到了最右側，如下所示：

每一輪的排序結果最終會如上圖所示，所以最終的排序結果就是最后一排的數值結果。

最后我們來總結下，冒泡排序算法的3個核心步驟：

• 比較相鄰的元素。如果第一個元素比第二個元素大，就將兩者交換；

• 對每一對相鄰的兩個元素進行同樣的操作。從開始第一對到結尾的最后一對，最后的元素就是最大的數。

• 針對所有元素重復以上步驟。每重復一輪上述步驟，需要操作的元素就會越來越少，直到沒有任何一對元素需要比較。

代碼實現

算法步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。代碼如下所示：

Array.prototype.bubble_sort = function() {var i, j, temp;for (i = 0; i < this.length - 1; i++)for (j = 0; j < this.length - 1 - i; j++)if (this[j] > this[j + 1]) {temp = this[j];this[j] = this[j + 1];this[j + 1] = temp;}return this;
}

選擇排序

概念

選擇排序(Selection Sort) 是一種最簡單直觀的排序算法。即使在我們的日常生活中，大家可能都會經常無意地進行選擇排序。

例如：我們去超市買西紅柿，拿了一個袋子，從眾多的西紅柿中挑了一個最大好的放入袋中，然后又從剩下的西紅柿中挑了一個最大的放入袋子。這樣如此反復，直到挑夠了需要的西紅柿去結賬。這其實就是選擇排序的實現思想，就是不斷地從未排序的元素中選擇最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素為空。

基于上述實現思想，我們就可以提取出選擇排序的實現原理：

將一個數組分成有序的區間和無序的區間兩部分，初始時有序區間為空，每次從無序區間中選出最小的元素，并放到有序區間的末尾，直到無序區間為空。

實現步驟

假如我們現在有一個待排序的數組[5，8，6，3，9，2，1，7]

若采用選擇排序算法進行排序，其實現步驟如下：

1. 初始化待排序數組[5，8，6，3，9，2，1，7]；
2. 從待排序數組中，選出最小值1，和第一個元素5進行交換，即將最小的元素放在下標0的位置上；
3. 在剩下的無序區間的元素中，選擇最小的元素2，并將最小的元素2與無序區間的第一個元素8進行交換。交換后，有序區間的元素變為2個，分別是1和2，剩余的為無序區間。
4. 依次類推，將所有的元素通過不斷選擇的方式，按有序的方式放到有序區間，最終把整個數組全部排好順序。

我們把上述選擇排序的文字描述內容，變成對應的圖片，會如下圖所示：

代碼實現

算法步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。代碼如下：

function selectionSort(arr) {var len = arr.length;var minIndex, temp;for (var i = 0; i < len - 1; i++) {minIndex = i;for (var j = i + 1; j < len; j++) {if (arr[j] < arr[minIndex]) {     // 尋找最小的數minIndex = j;                 // 將最小數的索引保存}}temp = arr[i];arr[i] = arr[minIndex];arr[minIndex] = temp;}return arr;
}

總結

• 冒泡排序屬于交換排序算法的一種；

• 選擇排序算法是原地排序算法的一種；

• 冒泡排序的核心思想是把相鄰的元素進行兩兩比較，當一個元素大于右側相鄰的元素時，就交換它們的位置；當一個元素小于或等于右側相鄰的元素時，則保持位置不變。

• 選擇排序的實現思想，就是不斷地從未排序的元素中選擇最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素為空。

兩者的區別簡單了說就是冒泡排序在比較的過程中待排序的數據會發生位置改變，而選擇排序法在比較過程中，是記錄較大/較小數據的索引，只有在找到最大/最小數據的時候才會發生交換。?