JavaScript中常见排序算法详解

gap = 1;

while(gap < len/3) { //动态定义距离序列

gap =gap*3+1;

}

for (gap; gap > 0; gap = Math.floor(gap/3)) {

for (var i = gap; i < len; i++) {

temp = arr[i];

for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {

arr[j+gap] = arr[j];

}

arr[j+gap] = temp;

}

return arr;

}

归并排序

作为一种典范的分而治之思惟的算法应用，归并排序的实现由两种办法：

自上而下的递归（所有递归的办法都可以用迭代重写，所以就有了第2种办法）
自下而上的迭代

在《数据构造与算法JavaScript描述》中，作者给出了自下而上的迭代办法。然则对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而,在 JavaScript 中这种方法不太可行,因为这个算法的递归深度对它来讲太深了。

说实话，我不太懂得这句话。意思是JavaScript编译器内存太小，递归太深轻易造成内存溢出吗？还望有大年夜神可以或许指教。

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

归并排序动图演示

归并排序JavaScript代码实现：

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	
			 4/9   首页 上一页 2 3 4 5 6 7 下一页 尾页	
			

　　推荐阅读
　　为啥你电脑越来越卡 别人却能战五年？
对于这种的办法：大年夜网页点击下载时要看看下载的文件名，绿色版的软件一般是目标软件的拼音或者英订婚名，多半是紧缩包(就算是安装版也要打包一下的)，所以如不雅下载文件名是无序字符串，以及是exe文件，十有八九>>>详细阅读


本文标题：JavaScript中常见排序算法详解
地址：http://www.17bianji.com/lsqh/39153.html
 1/2    1