归并排序

归并排序

这个排序算法是建立在归并操作上的一种有效的排序算法，算法主要采用分治法，归并排序的算法复杂度为O（n*logn），需要一个与数组的长度n一样的额外空间，实现归并排序通常对于一个数组我们对前半部分进行排序，然后进行后半部分进行排序，实现原地归并操作，不过需要额外的空间存储数组。归并排序分为两种，一种是自顶向下的归并排序，一种是自底向上的归并排序。

一、自顶向下的归并排序

把数组元素不断的二分，直到子数组的元素个数为一个，这时子数组必然是有序的，然后将两个有序的序列合并成一个新的有序的序列，两个新的有序序列又可以合并成另一个新的有序序列，以此类推，直到合并成一个有序的数组。

var data=[1,5,3,23,4,67,8];
function merge(data, left, center, right) {
    var tmpArr = [];
    var mid = center + 1;
    var third = left;
    var tmp = left;
    while (left <= center && mid <= right) {
        if (data[left] <= data[mid]) {
            tmpArr[third++] = data[left++];
        } else {
            tmpArr[third++] = data[mid++];
        }
    }
    while (mid <= right) {
        tmpArr[third++] = data[mid++];
    }
    while (left <= center) {
        tmpArr[third++] = data[left++];
    }
    while (tmp <= right) {
        data[tmp] = tmpArr[tmp++];
    }
}
function sort(data, left, right) {
    if (left >= right)
        return;
    var center = parseInt((left + right) / 2);
    sort(data,left,center);
    sort(data,center+1,right);
    merge(data,left,center,right);
    console.log(data);
}

sort(data,0,6);
console.log(data);

二、自底向上的归并排序

其实逻辑跟上一个一样，只有sort函数有差别，不过这个不需要递归到最后，直接从一开始就进行比较，通过控制增量解决合并的问题，如果有8个元素，增量为1时有四组合并，增量为2时候，两组合并，最后进行全部合并。

function sort2(data,left,right)
{
    var len=data.length;
    for (var sz = 1; sz < len; sz *= 2)
    {
        for (var lo = 0; lo < len; lo += 2 * sz)
        {
            merge(data, lo, lo+sz-1, min(lo+2*sz-1, len-1));
        }
    }
}
function min(m,n) {
    if(m<=n){
        return m;
    }else {
        return n;
    }
}

结果数组