Javascript算法——歸并排序

cheukyin 發(fā)布于2019-08-20 15:26 / 413人閱讀

摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。這里主要介紹歸并排序。一圖勝千言歸并排序算法描述歸并排序是建立在歸并操作上的一種有效的排序算法。若將兩個有序表合并成一個有序表，稱為路歸并。

常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。這里主要介紹歸并排序。

一圖勝千言：

1.歸并排序 1.1 算法描述

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個典型的應(yīng)用。合并排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。

1.2 算法分析

時間復(fù)雜度：O (nlogn)

空間復(fù)雜度：O (n)

1.3 算法實現(xiàn)

function merge(leftArr, rightArr){  
    var result = [];  
    while (leftArr.length > 0 && rightArr.length > 0){  
      if (leftArr[0] < rightArr[0])  
        result.push(leftArr.shift()); //把最小的最先取出，放到結(jié)果集中   
      else   
        result.push(rightArr.shift());  
    }   
    return result.concat(leftArr).concat(rightArr);  //剩下的就是合并，這樣就排好序了  
}  

function mergeSort(array){  
    if (array.length == 1) return array;  
    var middle = Math.floor(array.length / 2);       //求出中點  
    var left = array.slice(0, middle);               //分割數(shù)組  
    var right = array.slice(middle);  
    return merge(mergeSort(left), mergeSort(right)); //遞歸合并與排序  
}  

var arr = mergeSort([32,12,56,78,76,45,36]);
console.log(arr);   // [12, 32, 36, 45, 56, 76, 78]