(3)算法分析

• 最佳情况：T(n) = O(nlog2 n)
• 最坏情况：T(n) = O(nlog2 n)
• 平均情况：T(n) =O(nlog n)

5.归并排序(Merge Sort)

和选择排序一样，归并排序的机能不受输入数据的影响，但表示比选择排序好的多，因为始终都是O(n log n)的时光复杂度。价值是须要额外的内存空间。

(1)算法简介

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采取分治法(Divide and Conquer)的一个异常典范的应用。归并排序是一种稳定的排序办法。将已有序的子序列归并，获得完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表归并成一个有序表，称为2-路归并。

(2)算法描述和实现

具体算法描述如下：

• <1>.把长度为n的输入序列分成两个长度为n/2的子序列;
• <2>.对这两个子序列分别采取归并排序;
• <3>.将两个排序好的子序列归并成一个最终的排序序列。

Javscript代码实现:

function mergeSort(arr) {  //采取自上而下的递归办法 
 
    var len = arr.length; 
 
    if(len < 2) { 
 
        return arr; 
 
    } 
 
    var middle = Math.floor(len / 2), 
 
        left = arr.slice(0, middle), 
 
        right = arr.slice(middle); 
 
    return merge(mergeSort(left), mergeSort(right)); 
 
} 
 
function merge(left, right) 
 
{ 
 
    var result = []; 
 
    console.time('归并排序耗时'); 
 
    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) 	
			
 8/11   首页 上一页 6 7 8 9 10 11 下一页 尾页
	
			

　　推荐阅读
　　一文读懂矩阵的秩和行列式的意义
            【技巧沙龙】AI开辟者拭魅战营-7分钟打造1个定制技能。7月22号，我们等你一路！

            作为一个工科的学生,我们经久以来会应用比如像是矩阵以及行列式这些在线性代数上的常识,在这篇文┞仿中,我>>>详细阅读


本文标题：十大经典排序算法的JS版
地址：http://www.17bianji.com/lsqh/36267.html
 1/2    1