我不断丢失值并得到 0。我的逻辑有什么问题？

Question

大家好，我需要使用给定的 header 在 C++ 中为 mergeSort() 编写归并排序；

我的分区是正确的，但是在它合并一个在它有 0 之前合并的数组的时候。例如：如果我有 [34][21]，我得到 [21, 34]，但是当它与 [8] 合并时，它给出 [0, 0, 8]。我正在失去价值观。请帮我调试一下。

注意： 我有一些 moveCount 来计算数据移动和 compCount 来计算计算。请不要与那些混淆。

int * merge(int * left ,int szLeft ,int * right,int szRight, int &compCount, int &moveCount){
    int * newArr = new int [szLeft+szRight];
    cout << "Left: ";
    for (int i = 0; i < szLeft; ++i){
        cout << left[i] << " ";
    }
    cout << endl;

    cout << "Right: ";
    for (int i = 0; i < szRight; ++i){
        cout << right[i] << " ";
    }
    cout << endl;

    int bigArrIndex = 0, rightArrIndex = 0,leftArrIndex = 0;

    while(leftArrIndex < szLeft && rightArrIndex < szRight){
        compCount++;
        if(right[rightArrIndex] <= left[leftArrIndex]){
            newArr[bigArrIndex] = right[rightArrIndex];
            rightArrIndex++;
            compCount++;
        }
        else{
            newArr[bigArrIndex] = left[leftArrIndex];
            leftArrIndex++;
        }
        moveCount++;
        bigArrIndex++;
    }

    //1 more computation done even if the loop is not executed
    compCount++;

    //copy the rest of the stuff if left
    while(rightArrIndex < szRight){
        moveCount++;
        compCount++;
        newArr[bigArrIndex] = right[rightArrIndex];
        rightArrIndex++;
        bigArrIndex++;
    }
    //1 more computation done even if the loop is not executed
    compCount++;

    //copy the rest of the stuff if left
    while(leftArrIndex < szLeft){
        moveCount++;
        compCount++;
        newArr[bigArrIndex] = left[leftArrIndex];
        leftArrIndex++;
        bigArrIndex++;
    }

    //1 more computation done even if the loop is not executed
    compCount++;

    return newArr;
}


void mergeSort( int * arr, int size, int &compCount, int &moveCount){
    //to take the branch or not needs 1 comparison
    compCount++;

    if(size > 1){
        int mid = size/2;
        int * left = new int[mid];
        int * right = new int[size-mid];


        for(int i = 0; i < mid; i++){
            compCount++;
            left[i] = arr[i];
            moveCount++;
        }
        //1 more computation done even if the loop is not executed
        compCount++;

        for(int i = mid; i < size; i++){
            right[i-mid] = arr[i];
            moveCount++;
            compCount++;
        }
        //1 more computation done even if the loop is not executed
        compCount++;

        mergeSort(left,mid,compCount,moveCount);
        mergeSort(right,size-mid,compCount,moveCount);
        int * sortedArr = merge(left,mid,right,size-mid,compCount,moveCount);
        cout << "Done: ";
        for (int i = 0; i < size; ++i)
            cout << sortedArr[i] << " ";
        cout << endl;

        //delete[] left;
        //delete[] right;

        for(int i = 0; i < size; i++){
            arr[i] = sortedArr[size];
            moveCount++;
            compCount++;
        } 
        //1 more computation done even if the loop is not executed
        compCount++;
    }
}

Answer 1

只有一行。评论中指出的修复：

        //delete[] left;
        //delete[] right;

        for(int i = 0; i < size; i++){
            arr[i] = sortedArr[i];    // fix from [size] to [i]
            moveCount++;
            compCount++;
        }

评论：在mergeSort中，代码可以使用arr而不是left，arr+mid而不是right，而不是分配left和right。少了两个分配。入口/辅助函数可以一次性分配与原始数组大小相同的临时数组，并将其作为参数传递给 mergeSort()，后者又将其作为参数传递给 merge()。在这种情况下，mergeSort 所做的只是在堆栈上创建索引对，而 merge 进行实际的合并和复制。

虽然可能超出了这个 class 的范围，但也可以使用两个相互递归的 mergeSort 版本来消除复制，其中一个合并数据以原始数组结尾，称为 mergeSortO() ，其中合并数据最终出现在临时数组中，调用此 mergeSortT()。 mergeSortO() 调用 mergeSortT() 两次（左半部分和右半部分），然后调用 merge() 将临时数组合并到原始数组。 mergeSortT() 调用 mergeSortO() 两次（左半边和右半边），然后调用 merge() 将原始数组合并到临时数组，或者如果大小为 1，则将一个元素从原始数组复制到临时数组。

也可能在 class 之外，另一种选择是自下而上的归并排序，因为大多数库（例如 STL std::stable_sort()）使用自下而上归并排序的一些变体。

我不断丢失值并得到 0。我的逻辑有什么问题？

I keep losing the values and getting 0's. What's the wrong with my logic?

c++

sorting

merge

mergesort