时间戳

首页 > 解决方案 > Javascript中合并排序的迭代方法

javascript - Javascript中合并排序的迭代方法

问题描述

我正在尝试迭代地实现合并排序，但在 javascript 中。我也尝试在互联网上搜索，但它们只有 C、Python 和 java。我的函数给出的数组未排序。我尝试了不同的方法，但无法找出错误。有人可以指出我做错了什么吗？

function mergeSortIterative(arr){
    let sorted=[...arr];//copying the array so that original remains unchanged.
    let n=sorted.length;
    let currSize;
    let leftStart;
    for(currSize=1;currSize<=n-1;currSize=2*currSize){
        for(leftStart=0;leftStart<n-1;leftStart+=2*currSize){
            let mid=Math.min(leftStart+currSize-1,n-1);
            let rightEnd=Math.min(leftStart+2*currSize-1,n-1);
            // let left=sorted.slice(leftStart,mid);
            // let right=sorted.slice(mid,rightEnd);
            // sorted=mergeIterative(sorted,left,right);
            mergeIterative(sorted,leftStart,mid,rightEnd);
        }
    }
    return sorted;
}

function mergeIterative(sorted,leftStart,mid,rightEnd){
    let left=sorted.slice(leftStart,mid);
    let right=sorted.slice(mid,rightEnd);
    let leftIndex=0,rightIndex=0,k=leftStart;
    while(leftIndex<left.length && rightIndex<right.length){
        //picking the lesser one 
        if(left[leftIndex]<=right[rightIndex]){
            sorted[k]=left[leftIndex];
            leftIndex++;
            k++;
        }
        else{
            sorted[k]=right[rightIndex];
            rightIndex++;
            k++;
        }
    }
    while(leftIndex<left.length && k<sorted.length){
        sorted[k]=left[leftIndex];
        leftIndex++;
        k++;
    }
    while(rightIndex<right.length && k<sorted.length){
        sorted[k]=right[rightIndex];
        rightIndex++;
        k++;
    }
}

标签： javascriptarrayssortingmergesort

解决方案

您的代码中的错误在于内容mid和rightEnd含义的定义不一致。

从以下代码中，我们了解到这些索引指向前面子数组之后的条目：

let left = sorted.slice(leftStart, mid);
let right = sorted.slice(mid, rightEnd);

但是在查看作业时：

let mid = Math.min(leftStart + currSize - 1, n - 1); 
let rightEnd = Math.min(leftStart + 2 * currSize - 1, n - 1);

...我们看到它们指向前面子数组的最后一个元素。

您可以通过两种方式更正此问题，但由于slice解释其参数的方式是“标准”方式，我建议在分配中进行更正，删除所有这些- 1，如下所示：

let mid = Math.min(leftStart + currSize, n); 
let rightEnd = Math.min(leftStart + 2 * currSize, n);

推荐阅读