JavaScript实践数据结构和算法——归并排序

涎涎原创约 347 字大约 1 分钟...

JavaScript实践数据结构和算法——归并排序

注意

本博文仅供学术研究和交流参考，严禁将其用于商业用途。如因违规使用产生的任何法律问题，使用者需自行负责。

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>归并排序</title>
</head>
<body>
<script>
    function mergeSort(arr) {
        if(arr.length<2){
            return
        }
        var step = 1;
        var left,right;
        while (step<arr.length){
            left = 0;
            right = step;
            while (right+step<=arr.length){
                mergeArrays(arr,left,left+step,right,right+step);
                left = right + step;
                right = left + step;
            }
            if(right<arr.length){
                mergeArrays(arr,left,left+step,right,arr.length);
            }
            step *= 2;
        }
    }
    function mergeArrays(arr,startLeft,stopLeft,startRight,stopRight) {
        var rightArr = new Array(stopRight - startRight + 1);
        var leftArr = new Array(stopLeft - startLeft +1);
        k = startRight;
        for(var i = 0;i<(rightArr.length - 1);i++){
            rightArr[i] = arr[k];
            ++k;
        }
        k = startLeft;
        for(var i=0;i<(leftArr.length-1);i++){
            leftArr[i] = arr[k];
            ++k;
        }
        rightArr[rightArr.length-1] = Infinity;
        leftArr[leftArr.length-1] = Infinity;
        var m = 0;
        var n = 0;
        for(var k = startLeft;k<stopRight;k++){
            if(leftArr[m]<=rightArr[n]){
                arr[k] = leftArr[m];
                m++;
            }else {
                arr[k] = rightArr[n];
                n++;
            }
        }

    }
    var arr = [23,45,19,98,32,67,12,3,9];
    mergeSort(arr);
    console.log(arr);
</script>
</body>
</html>

得到结果：

JavaScript实践数据结构和算法——归并排序

JavaScript实践数据结构和算法——归并排序

分割线

预览:

JavaScript实践数据结构和算法——归并排序

# JavaScript实践数据结构和算法——归并排序

# 分割线

预览:

JavaScript实践数据结构和算法——归并排序

分割线