代码改变世界

【思维】归并排序

2010-03-17 16:53  BlueDream  阅读(417)  评论(0)    收藏  举报

归并排序:

是一个在效率上高于一般排序的算法.一般排序:冒泡, 插入, 选择排序的时间复杂度为O(N^2), 而归并排序的时间复杂度为O(N*LOG N).

如果N(及排序项的数目)是10000.那么N^2就是100000000, 而N * LOG N则是40000. 也就是如果这个数量的数据.如果用归并排序需要40S的时间,那么用插入排序则需要28个小时.

归并排序算法的核心:

核心思想就是分治算法.先进行划分,再进行排序归并.归并两个有序的数组.即归并两个有序的数组A和B,然后就有了包含这两个新数组的数组C.

即一次拿出A和B的数组项进行比较.小的就插入到新容器C中.直到一方已经插入完毕.如果另一方还有剩余那么就表示剩余的是有序的而且比较大的.那么就直接连接到C数组容易的后面即可.

 

 代码:

 

 /* 排序并合并*/
 function merge(left, right) {
    var re = [];
    while(left.length > 0 && right.length > 0) {
        if(left[0] < right[0]) {
            re.push(left.shift());
        } else {
            re.push(right.shift());
        }
    }
    /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
    return re.concat(left).concat(right);
 }

 function mergeSort(array) {
    if(array.length == 1) return array;
    /* 首先将无序数组划分为两个数组 */
    var mid = Math.floor(array.length / 2);
    var left = array.slice(0, mid);
    var right = array.slice(mid);
    /* 递归分别对左右两部分数组进行排序合并 */
    return merge(mergeSort(left), mergeSort(right));
 }
 var a = [23, 47 ,81 ,95 ,7, 14, 39, 55, 62, 74]
 alert(mergeSort(a));

参考连接:

http://chuna2.787528.xyz/springfield/archive/2009/11/25/1610510.html