首页 > 编程语言 > 详细

归并排序

时间:2016-12-11 01:15:40      阅读:244      评论:0      收藏:0      [点我收藏+]

基本过程

1.将数组递归分解为有序数组(当分解到数组元素个数为1时候,数组自然有序)

2.将两个有序数组合并为一个大的有序数组

3.递归合并完成,即排序完成

javascript实现

function fMergeSort(arr,first,last,aTemp){
    if(first > last){
        throw new Error(‘first should less than last‘);
    }
    //取中对数组进行二分
    var mid = (first + last)/2;
    fMergeSort(arr,first,mid,aTemp);
    fMergeSort(arr,mid+1,last,aTemp);
    fMergeArray(arr,first,mid,last,aTemp);
}

function fMergeArray(arr,first,mid,last,aTemp){
    var k = 0,
        left = first,leftEnd = mid,
        right = mid+1,rightEnd = last;
    //将左右数组中较小者优先复制到临时数组
    while(left <= leftEnd && right <= rightEnd){
        if(arr[left] <= a[right]){
            aTemp[k++] = arr[left++];
        } 
        else{
            aTemp[k++] = arr[right++];
        }
    }
    //将left或right剩余元素复制到临时数组,left或right只会有一个剩余
    while(left <= leftEnd){
        aTemp[k++] = arr[left++];
    }
    while(right <= rightEnd){
        aTemp[k++] = arr[right++];
    }
    //将临时数组元素复制到元素数组中
    for(var i=0;i<k;i++){
        arr[first+i] = aTemp[i];
    }
}

 

归并排序

原文:http://www.cnblogs.com/mengff/p/6158470.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!