JS中常見排序Sort算法的示例分析

小編給大家分享一下JS中常見排序Sort算法的示例分析，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

排序算法（Sort）

引言

我們平時對計算機中存儲的數據執行的兩種最常見的操作就是排序和查找，對于計算機的排序和查找的研究，自計算機誕生以來就沒有停止過。如今又是大數據，云計算的時代，對數據的排序和查找的速度、效率要求更高，因此要對排序和查找的算法進行專門的數據結構設計，（例如我們上一篇聊到的二叉查找樹就是其中一種），以便讓我們對數據的操作更加簡潔高效。

這一篇我們將會介紹一些數據排序的基本算法和高級算法并利用JavaScript來逐一實現，讓大伙對計算機中常見的排序算法的思想和實現有基本的了解，起到一個拋磚引玉的作用。

關于排序算法的說明

在介紹各個算法之前，我們有必要了解一下評估算法優劣的一些術語：

穩定：如果a原本在b前面，當a=b時，排序之后a仍然在b的前面 不穩定：如果a原本在b的前面，當a=b時，排序之后a可能會出現在b的后面

內排序：所有排序操作都在內存中完成 外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行

時間復雜度：一個算法執行所耗費的時間 空間復雜度：運行完一個程序所需內存的大小

有想要了解更多，關于時間空間復雜度的，我推薦一篇文章，請戳這里

基本排序算法

基本排序算法的核心思想就是對一組數據按照一定的順序重新排序，其中重排時一般都會用到一組嵌套的 for 循環，外循環會遍歷數組的每一項元素，內循環則用于進行元素直接的比較。

1.冒泡排序（BubbleSort）

冒泡排序是比較經典的算法之一，也是排序最慢的算法之一，因為它的實現是非常的容易的。

冒泡排序的算法思想如下（升序排序）：

1. 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；

2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣最終最大數被交換到最后的位置

3. 除了最后一個元素以外，針對所有的元素重復以上的步驟

4. 重復步驟1~3，直到排序完成

下面我借用網上一張動圖，來展示冒泡排序的過程：

冒泡排序

具體的JS實現如下：

//冒泡排序
function bubbleSort ( data ) {
 var temp = 0;
 for ( var i = data.length ; i > 0 ; i -- ){
  for( var j = 0 ; j < i - 1 ; j++){
   if( data[j] > data[j + 1] ){
    temp = data[j];
    data[j] = data [j+1];
    data[j+1] = temp;
   }
  }
 }
 return data;
}

我們先設定一組數據，后面我們將都用這組數據來測試 :

var dataStore = [ 72 , 1 , 68 , 95 , 75 , 54 , 58 , 10 , 35 , 6 , 28 , 45 , 69 , 13 , 88 , 99 , 24 , 28 , 30 , 31 , 78 , 2 , 77 , 82 , 72 ];

console.log( '原始數據:' + dataStore );
console.log( '冒泡排序:' + bubbleSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 冒泡排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

2.選擇排序（SelctionSort）

選擇排序是一種比較簡單直觀的排序算法。它的算法思想是，從數組的開頭開始遍歷，將第一個元素和其他元素分別進行比較，記錄最小的元素，等循環結束之后，將最小的元素放到數組的第一個位置上，然后從數組的第二個位置開始繼續執行上述步驟。當進行到數組倒數第二個位置的時候，所有的數據就完成了排序。

選擇排序同樣會用到嵌套循環，外循環從數組第一個位置移到倒數第二個位置；內循環從第二個位置移動到數組最后一個位置，查找比當前外循環所指向的元素還要小的元素，每次內循環結束后，都會將最小的值放到合適的位置上。

同樣，我借用網上一張動圖，來展示選擇排序的過程 ：

選擇排序

了解了算法思想，具體實現應該也不成問題：

//選擇排序
function selectionSort( data ) {
 for( var i = 0; i< data.length ; i++){
  var min = data[i];
  var temp;
  var index = i;
  for( var j = i + 1; j< data.length; j++){
   if( data[j] < min ){
    min = data[j];
    index = j;
   }
  }

  temp = data[i];
  data[i] = min;
  data[index]= temp;
 }
 return data;
}

它的測試結果如下：

console.log( '原始數據:' + dataStore );
console.log( '選擇排序:' + selectionSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 選擇排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

3.插入排序（insertionSort）

插入排序有點類似人類按字母順序對數據進行排序，就如同你打撲克牌一樣，將摸來的撲克按大小放到合適的位置一樣。它的原理就是通過嵌套循環，外循環將數組元素挨個移動，而內循環則對外循環中選中的元素及它后面的元素進行比較；如果外循環中選中的元素比內循環中選中的元素小，那么數組元素會向右移動，為內循環中的這個元素騰出位置。

實現步驟如下：

1. 從第一個元素開始，該元素默認已經被排序

2. 取出下一個元素，在已經排序的元素序列中從后向前掃描

3. 如果該元素（已排序）大于新元素，將該元素移到下一位置

4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置

5. 將新元素插入到該位置

6. 重復步驟2~5，直到排序完成

它的實現效果圖如下：

插入排序

具體實現代碼如下：

//插入排序

function insertionSort( data ) {
 var len = data.length;
 for (var i = 1; i < len; i++) {
  var key = data[i];
  var j = i - 1;
  while ( j >= 0 && data[j] > key) {
   data[j + 1] = data[j];
   j--;
  }
  data[j + 1] = key;
 }
 return data;
}

排序結果如下：

console.log( '原始數據:' + dataStore );
console.log( '插入排序:' + insertionSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 插入排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

我們已經學習了三種基本的排序算法，其中冒泡排序是最慢的，插入排序是最快的，我們可以在運行的過程中通過 console.time('sortName') 和 console.timeEnd('sortName') 兩個輸出來看他們的效率如何，我這里給出一組值作為參考，實際中需要大量的數據測試和反復實驗，進行數理統計后才能被視為有效的統計；

排序時間比較

高級排序算法

4.希爾排序（Shell Sort）

我們首先要學習的就是希爾排序，又稱縮小增量排序，這個算法是在插入排序的基礎上做了很大的改善，與插入排序不同的是，它首先會比較位置較遠的元素，而非相鄰的元素。這種方案可以使離正確位置很遠的元素能夠快速回到合適的位置，當算法進行遍歷時，所有元素的間距會不斷的減小，直到數據的末尾，此時比較的就是相鄰元素了。

該方法的基本思想是：先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上有較大提高。

好吧，我還是用個案例來解釋，這樣會更清晰，我們以下面一組數據為例：

數據集

• 第一次 gap(增量) = 10 / 2 = 5 , 會按照下面進行分組得到五組數據（49，13）、（38，27）、（65，49）、（97，55）、（26，4），這樣進行組內排序之后（13，49）、（27，38）、（49，65）、（55，97）、（4，26）

第一次分組

此時，數據會排成如下結構

第一次排序

• 第二次 gap = 5 / 2 = 2 , 此時可以得到兩個分組，如下

第二次分組

再通過組內排序之后，可以得到

第二次排序

• 第三次 gap = 2 / 2 = 1 ， 即不用分組，進行排序后

第三次排序

• 第四次 gap = 1 / 2 = 0 ，即可得到排序完成的數組

排序完成

現在，可能對希爾排序有了一定得了解了，用JS實現如下：

//希爾排序

function shallSort(array) {
 var increment = array.length;
 var i
 var temp; //暫存
 do {
  //設置增量
  increment = Math.floor(increment / 3) + 1;
  for (i = increment ; i < array.length; i++) {
   if ( array[i] < array[i - increment]) {
    temp = array[i];
    for (var j = i - increment; j >= 0 && temp < array[j]; j -= increment) {
     array[j + increment] = array[j];
    }
    array[j + increment] = temp;
   }
  }
 }
 while (increment > 1)

 return array;
}

效果如下：

console.log( '原始數據:' + dataStore );
console.log( '希爾排序:' + shallSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希爾排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

5.歸并排序（Merge Sort）

將兩個的有序數列合并成一個有序數列，我們稱之為"歸并"，歸并排序的思想就是將一系列排序好的子序列合并成一個大的完整有序的序列。

實現步驟如下：

1. 把長度為n的輸入序列分成兩個長度為n/2的子序列；

2. 對這兩個子序列分別采用歸并排序；

3. 將兩個排序好的子序列合并成一個最終的排序序列

一張動圖來說明歸并排序的過程：

歸并排序

具體的JS代碼實現如下：

//歸并排序

function mergeSort ( array ) {
 var len = array.length;
 if( len < 2 ){
  return array;
 }
 var middle = Math.floor(len / 2),
  left = array.slice(0, middle),
  right = array.slice(middle);
 return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
 var result = [];
 while (left.length && right.length) {
  if (left[0] <= right[0]) {
   result.push(left.shift());
  } else {
   result.push(right.shift());
  }
 }
 while (left.length)
  result.push(left.shift());
 while (right.length)
  result.push(right.shift());
 return result;
}

測試結果如下 ：

console.log( '原始數據:' + dataStore );
console.log( '希爾排序:' + mergeSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 希爾排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

6.快速排序（Quicksort）

快速排序是處理大數據最快的排序算法之一，它也是一種分而治之的算法，通過遞歸方式將數據依次分解為包含較小元素和較大元素的不同子序列，會不斷重復這個步驟，直到所有的序列全部為有序的，最后將這些子序列一次拼接起來，就可得到排序好的數據。

該算法首先要從數列中選出一個元素作為基數（pivot）。接著所有的數據都將圍繞這個基數進行，將小于改基數的元素放在它的左邊，大于或等于它的數全部放在它的右邊，對左右兩個小數列重復上述步驟，直至各區間只有1個數。

整個排序過程如下：

快速排序

具體實現如下：

//快速排序

function quickSort( arr ){
 if ( arr.length == 0) {
  return [];
 }
 var left = [];
 var right = [];
 var pivot = arr[0];
 for (var i = 1; i < arr.length; i++) {
  if (arr[i] < pivot) {
   left.push( arr[i] );
  } else {
   right.push( arr[i] );
  }
 }
 return quickSort( left ).concat( pivot, quickSort( right ));
}

測試結果如下：

console.log( '原始數據:' + dataStore );
console.log( '快速排序:' + quickSort( dataStore) );

// 原始數據:72,1,68,95,75,54,58,10,35,6,28,45,69,13,88,99,24,28,30,31,78,2,77,82,72
// 快速排序:1,2,6,10,13,24,28,28,30,31,35,45,54,58,68,69,72,72,75,77,78,82,88,95,99

以上是“JS中常見排序Sort算法的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！