常見的排序演算法總結（JavaScript）

引言

排序演算法是數據結構和演算法之中的基本功，無論是在筆試還是面試，還是實際運用中都有著很基礎的地位。這不正直七月，每年校招的備戰期，所以想把常見的排序演算法記錄下來。在本篇文章中的排序演算法使用 JavaScript 實現。

冒泡排序是排序演算法中最簡單的一個演算法，其優點是易理解，易實現。在一些對性能要求不高且數據量不大的需求中，冒泡排序是一個很好的選擇。

原理：假設排序順序為增序，數組長度為 N。數組每相鄰兩個元素進行比較，大數後移，小數前移，第一輪排序下來就能找到最大的數。也就是比較 A[i] 和 A[i+1] ，將大數後移，隨後增加 i 的值，再進行比較。第二輪再對剩餘的 N-1 個數進行排序，找出第二大的數，以此類推。同時也可以記錄交換次數來進行優化，如果在一層循環之中交換次數為 0，則排序結束。

下面這張圖展示了冒泡排序的全過程：

下面這張圖展示冒泡排序在宏觀層面的全過程：

1 function bubbleSort (arr) {
2 var swapTime = 0;
3 for(var i = 0, length1 = arr.length; i < length1; i ++){ 4 for(var j = 0, length2 = length1 - i; j < length2 - 1; j ++){ 5 if(arr[j] > arr[j+1]){
6 swapTime++;
7 var temp = arr[j];
8 arr[j] = arr[j+1];
9 arr[j+1] = temp;
10 }
11 }
12 //檢查交換次數，如果為0，則當前數組為有序數組；如不為0，則重置
13 if(swapTime === 0){
14 break;
15 }else {
16 swapTime = 0;
17 }
18 }
19 }

二、選擇排序

選擇排序演算法與冒泡排序演算法類似，即每一輪找出一個最大值。但和冒泡排序不同的一點是，冒泡排序是採用不停的交換將最大值（最小值）篩選出來，而選擇排序是記錄下最大值（最小值）的索引。

原理：假設排序方式為增序，數組長度為 N。設置最大值索引初始值 index = 0，然後遍曆數組，記錄下最大值的索引，即比較 A[i] 與 A[index] 的值，若 A[i] > A[index] 則更新 index = i。在每一輪遍歷結束後，交換 index 位置和末尾位置的值，即交換 A[index] 和 A[i]，這樣便保證了末尾值是最大值。隨後對剩餘的 N-1 個數進行同樣的方式排序，以此類推。

下面這張圖展示了選擇排序的全過程：

下面這張圖展示了在宏觀層面上選擇排序的全過程：

1 function selectSort (arr) {
2 for(var i = 0, length1 = arr.length; i < length1; i ++){ 3 var index = 0 4 for(var j = 0, length2 = length1 - i; j < length2; j ++){ 5 if(arr[j] > arr[index]){
6 index = j;
7 }
8 }
9 var temp = arr[index];
10 arr[index] = arr[length1 - i - 1];
11 arr[length1 - i - 1] = temp;
12 }
13 }

三、插入排序

插入排序的思想是將原始數組劃分成兩側，一側是有序數組，一側是無序數組。每次取出無序數組的一個元素，將它插入到有序數組的正確位置上，這種方式也會導致有序數組中其插入位置之後的元素全部後移。插入排序的思想類似於我們抓撲克牌。

原理：假設排序方式為增序，數組長度為 N。初始設 A[0] 為有序數組，A[1] ~ A[N-1] 為無序數組，取出 A[1] 將其插入至有序數組中的正確位置，使得有序數組增大為 A[0] ~ A[1]。繼續取 A[2] 將其插入至有序表數組的正確位置，以此類推，直至無序數組取完。

下面這張圖展示了插入排序的全過程：

下面這張圖展示了在宏觀層面上插入排序的全過程：

1 function insertSort (arr) {
2 for(var i = 0, length1 = arr.length; i < length1; i ++){ 3 for(var j = 0, length2 = i + 1; j < length2; j ++){ 4 if(arr[j] > arr[length2]){
5 var temp = arr[length2];
6 for(var k = length2; k > j; k --){
7 arr[k] = arr[k-1];
8 }
9 arr[j] = temp;
10 }
11 }
12 }
13 }

四、 希爾排序

希爾排序是優化過後的插入，其演算法的思想是在插入排序的基礎上加上了一個步長 gap，通過步長將數組分成若干個子項，先分別對子項進行插入排序，使得每一個元素朝著最終目的地跨了一大步。然後逐步縮小步長，這種排序演算法也是不穩定的。

原理：假設排序方式為增序，數組長度為 N。首先取步長 gap = N/2，那麼便將 N 長度的數組拆分成了 [A[0], A[gap]]，[A[1], A[gap+1]]，[A[2], A[gap+3]] ... ... [A[gap-1], A[N-1]] 子數組，分別對子數組進行插入排序。隨後逐步縮小步長，再進行插入排序，直至步長為 1。

下面這張圖展示了希爾排序的全過程：

下面這張圖展示了希爾排序在宏觀上的全過程：

1 function shellSort(arr) {
2 var gap = Math.floor(arr.length / 2);
3 while (gap >= 1) {
4 for (var i = 0; i < gap; i++) { 5 for (var j = i; j < arr.length; j += gap) { 6 for (var k = i, length = j + gap; k < length; k += gap) { 7 if (arr[k] > arr[length]) {
8 var temp = arr[length];
9 for (var x = length; x > k; x = x - gap) {
10 arr[x] = arr[x - gap];
11 }
12 arr[k] = temp;
13 }
14 }
15 }
16 }
17 gap = Math.floor(gap / 2);
18 }
19 }

五、歸併排序

歸併排序是分治法思想的典型應用，我們可以把一個 N 規模的問題分解成若干個小規模的子問題，用子問題的解來求解原問題。這同時也涉及到了問題的求解順序，在動態規劃演算法中有自頂向下和自底向上兩種不同的求解順序。在這裡一般採用的是自底向上的求解方法，比如一個 N 長度的數組，我們可以分解成 N/2 個長度為 2 或 1 的子數組，分別對子數組排序，再進行兩兩相併，直到歸併成原始數組。

原理：假設排序順序為增序，數組長度為 N。將數組拆分成 N 個長度為 1 的數組。然後相鄰子數組進行歸併，形成若干個長度為 2 或者 1 的數組，再繼續進行歸併，直至長度為 N。

下面這張圖展示了歸併的排序的全過程：

下面這張圖展示了在宏觀層面上歸併排序的全過程：

1 function mergeSort(arr) {
2 var n = 1;
3 while (n < arr.length) { 4 for (var i = 0; i < arr.length; i += n*2) { 5 var arr1 = arr.slice(i, i+n); 6 var arr2 = arr.slice(i+n, i+(n*2)); 7 var temp = ; 8 while(arr1.length != 0 || arr2.length != 0){ 9 if(arr1.length === 0){ 10 temp.push(arr2.shift); 11 continue; 12 } 13 if(arr2.length === 0){ 14 temp.push(arr1.shift); 15 continue; 16 } 17 if(arr1[0] < arr2[0]){ 18 temp.push(arr1.shift); 19 }else{ 20 temp.push(arr2.shift); 21 } 22 } 23 arr.splice(i, n*2, ...temp); 24 } 25 n = n * 2; 26 } 27 }

六、快速排序

快速排序同樣也使用了分治法的思想，在實際運用中使用的最多的就是快速排序。快速排序的核心思想是運用遞歸法，在每輪排序時指定一個基數，將基數移動到正確的位置上，然後再把基數的左右兩邊拆分出來，並分別進行相同的排序處理，直到其子數組長度為 1。其採用的是自頂向下的處理法。

原理：在每一輪排序中取一個基數 k ， 設 i 和 j 分別為數組的最左端和最右端，i 坐標從起始點向 k 點遍歷，若找到一個比 k 大的元素，則停下來等待 j 的遍歷。 j 坐標從起始點向 k 點遍歷，若找到一個比 k 小的元素，則 i 和 j 坐標的元素互相交換。若有一端提前到達了 k 點，則等待滿足條件後與另一端坐標交換。當 i 和 j 碰撞時，則為分治點，此時 i 和 j 相碰撞的坐標元素便是它的最終位置，以碰撞點為中心將數組拆分成兩段，並進行相同的遞歸處理。當 i >= j 時，則為回退點。

下面給出一張維基百科上的圖，展示了一輪快速排序的過程：

下面這張圖展示了一段快速排序的全過程：

1 function quickSort (arr) {
2 function sort(array, first, last) {
3 if (first >= last) {
4 return;
5 }
6 var base = Math.floor((first + last) / 2);
7 var i = first - 1;
8 var j = last - 1;
9 var temp;
10 while (j > i) {
11 while (j > i && array[j] > array[base]) {
12 j--;
13 }
14 while (i < j && array[i] <= array[base]) { 15 i++; 16 } 17 temp = array[i]; 18 array[i] = array[j]; 19 array[j] = temp; 20 } 21 temp = array[base]; 22 array[base] = array[i]; 23 array[i] = temp; 24 sort(array, first, i); 25 sort(array, i + 2, last) 26 } 27 sort(arr, 1, arr.length); 28 }

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！