溫故js系列（2）-快速排序&插入排序&選擇排序&冒泡排序算法&優(yōu)化

ningwang 發(fā)布于2019-08-19 18:43 / 1799人閱讀

摘要：優(yōu)化當(dāng)待排序序列長度時(shí)，使用插入排序，可以加速排序。插入排序原理通過構(gòu)建有序序列，對于未排序元素，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。

前端學(xué)習(xí)：教程&開發(fā)模塊化/規(guī)范化/工程化/優(yōu)化&工具/調(diào)試&值得關(guān)注的博客/Git&面試-前端資源匯總

歡迎提issues斧正：排序算法

JavaScript-排序算法及簡易優(yōu)化 快速排序

原理：在待排序序列中選一個(gè)分割元素，將待排序序列分隔成獨(dú)立的子序列，子序列1里的元素比分割元素元素都小（大），子序列2反之，遞歸進(jìn)行此操作，以達(dá)到子序列都有序。最后將子序列用concat方法連接起來即是排序好的序列。

function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }    
    var num = Math.floor(arr.length/2);
    var numValue = arr.splice(num,1);

    var left = [];
    var right = [];
    for(var i = 0;i
優(yōu)化：當(dāng)待排序序列長度N < 10時(shí)，使用插入排序，可以加速排序。
function quickSort(arr){
    if(arr.length <= 1){
        return arr;
    }
    if(arr.length < 10){
        insertSort(arr);
    }    
    var num = Math.floor(arr.length/2);
    var numValue = arr.splice(num,1);

    var left = [];
    var right = [];
    for(var i = 0;i
插入排序
原理：通過構(gòu)建有序序列，對于未排序元素，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。一般可以將第一個(gè)元素作為有序序列，用未排序的元素與之相比，插入，直到排序完畢。
function insertSort(arr){
    var len = arr.length;
    if(len <= 1){
        return arr;
    }
    for(var i = 1;i tmp){
            arr[j] = arr[j-1];
            --j;
        }
        arr[j] = tmp;
    }
    return arr;
}
console.log(insertSort([1,45,43,4,56,7,20,1]));
//[1, 1, 4, 7, 20, 43, 45, 56]
優(yōu)化：二分插入排序，在有序序列中使用二分查找法查找一個(gè)插入位置，減少元素比較次數(shù)
function binaryInsertSort(arr){
    var len = arr.length;
    if(len <= 1){
        return arr;
    }
    for (var i = 1; i < len; i++) {
        var tmp = arr[i], left = 0, right = i - 1;
        while (left <= right) {
              var index = parseInt((left + right) / 2);
              if (tmp < arr[index]) {
                  right = index - 1;
              } else {
                left = index + 1;
              }
        }
        for (var j = i - 1; j >= left; j--) {
              arr[j + 1] = arr[j];
        }
        arr[left] = tmp;
      }
    return arr;
}
console.log(binaryInsertSort([1,45,43,4,56,7,20,1,2,3,4,56,3]));
//[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]

選擇排序
原理：在待排序序列中找到最?。ù螅┰兀旁谛蛄械钠鹗嘉恢?，然后，再從剩余元素中尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。重復(fù)，直到所有元素均排序完畢。
Array.prototype.selectionSort = Array.prototype.selectionSort || function(){
    var len = this.length;
    if(len <= 1){
        return this;
    }    
    var min,tmp;
    for(var i = 0;i
優(yōu)化：堆排序，在直接選擇排序中，為了從序列中選出關(guān)鍵字最?。ㄗ畲螅┑挠涗?，必須進(jìn)行n-1次比較，接著在剩下序列中選出最?。ㄗ畲螅┑脑兀中枰鰊-2次比較。但是，在n-2次比較中，有的比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時(shí)未保留這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。
function heapSort(arr) { 
     function swap(arr, i, j) {
          var temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
    }
 
     function maxHeapify(arr, index, heapSize) {
          var iMax,iLeft,iRight;
          while (true) {
               iMax = index;
               iLeft = 2 * index + 1;
               iRight = 2 * (index + 1);
 
               if (iLeft < heapSize && arr[index] < arr[iLeft]) {
                iMax = iLeft;
               }
 
               if (iRight < heapSize && arr[iMax] < arr[iRight]) {
                iMax = iRight;
               }
 
               if (iMax != index) {    
                swap(arr, iMax, index);
                index = iMax;
               } else {
                    break;
               }
          }
     }
 
     function buildMaxHeap(arr) {
          var i,iParent = Math.floor(arr.length / 2) - 1;
 
          for (i = iParent; i >= 0; i--) {
               maxHeapify(arr, i, arr.length);
          }
     }
 
     function sort(arr) {
          buildMaxHeap(arr);
 
          for (var i = arr.length - 1; i > 0; i--) {
               swap(arr, 0, i);
               maxHeapify(arr, 0, i);
          }
          return arr;
     }
 
     return sort(arr);
}
console.log(heapSort([1,45,43,4,56,7,20,1,2,3,4,56,3]));
//[1, 1, 2, 3, 3, 4, 4, 7, 20, 43, 45, 56, 56]

冒泡排序
原理：從第一個(gè)元素開始，一次比較兩個(gè)元素，如果arr[n]大于arr[n+1]，就交換。重復(fù)遍歷直到?jīng)]有再需要交換，排序完成。
function bubbleSort(arr){
    var len = arr.length;
    if(len <= 1){
        return arr;
    }
    var tmp;
    for(var i = 0;i
優(yōu)化：上面代碼中，里面一層循環(huán)在某次掃描中沒有發(fā)生交換，說明此時(shí)數(shù)組已經(jīng)全部排好序，后面的步驟就無需再執(zhí)行了。因此，增加一個(gè)標(biāo)記，每次發(fā)生交換，就標(biāo)記，如果某次循環(huán)完沒有標(biāo)記，則說明已經(jīng)完成排序。
function bubbleSort(arr)  {  
    var len = arr.length;
    if(len <= 1){
        return arr;
    }
    var bSwaped = true;  
    for (var i = 0; i < len -1; i++)  {  
        // 每次先重置為false  
        bSwaped = false;  
        for (var j = len - 1; j > i ; j--)  {  
            if (arr[j-1] > arr[j])  {  
                var temp = arr[j-1];  
                arr[j-1] = arr[j];  
                arr[j] = temp;  
  
                bSwaped = true;  
            }  
        }  
        // 如果上一次掃描沒有發(fā)生交換，則說明數(shù)組已經(jīng)全部有序，退出循環(huán)  
        if (!bSwaped){
            break;
        }              
    }  
    return arr;
}  
console.log(bubbleSort([1,45,43,4,56,7,20,1]));
//[1, 1, 4, 7, 20, 43, 45, 56]

在上一步優(yōu)化的基礎(chǔ)上進(jìn)一步思考：如果R[0..i]已是有序區(qū)間，上次的掃描區(qū)間是R[i..n]，記上次掃描時(shí)最后一次發(fā)生交換的位置是lastSwapPos，那么lastSwapPos會(huì)在在i與n之間，所以R[i..lastSwapPos]區(qū)間是有序的，否則這個(gè)區(qū)間也會(huì)發(fā)生交換；所以下次掃描區(qū)間就可以由R[i..n]縮減到[lastSwapPos..n] :
function bubbleSort(arr){ 
    var len = arr.length;
    if(len <= 1){
        return arr;
    } 
    var lastSwapPos = 0, lastSwapPosTemp = 0;  
    for (var i = 0; i < len - 1; i++){  
        lastSwapPos = lastSwapPosTemp;  
        for (var j = len - 1; j > lastSwapPos; j--){  
            if (arr[j - 1] > arr[j]){  
                var temp = arr[j - 1];  
                arr[j - 1] = arr[j];  
                arr[j] = temp;  
  
                lastSwapPosTemp = j;  
            }  
        }  
        if (lastSwapPos == lastSwapPosTemp){
            break;
        }                         
    }  
    return arr;
}
console.log(bubbleSort([1,45,43,4,56,7,20,1]));
//[1, 1, 4, 7, 20, 43, 45, 56]

這一些列優(yōu)化都需要測速才知道有沒有優(yōu)化成功，只是簡單的測試一兩個(gè)數(shù)組是不容易看出來的。我們可以造一些很大的數(shù)據(jù)去測試，再用一個(gè)比較簡單的測試時(shí)間的方法，隨機(jī)創(chuàng)建10萬個(gè)數(shù)：
var arr = [];
var num = 0;
for(var i = 0; i < 100000; i++){
    num = Math.floor(Math.random()*100000);
    arr.push(num);
}
console.time("testTime");
bubbleSort(arr);
console.timeEnd("testTime");
==> testTime: 21900.684ms （比較數(shù)目越多，差距越大，更好對比）