归并排序技术的归并算法中最后2个while循环的用途

Question

下面的代码是在我的数据结构和算法课程中教授的。我目前正在复习它以准备考试。讲师编写的代码运行良好。

#include<iostream>
#define size 34
using namespace std;

int i,j,n;
int array[size];

void getvalues(){
    cout<<"how many values ";
    cin>>n;
    cout<<"enter values ";
    for(i=0; i<n; i++){
        cin>>array[i];
    }
}
void display(){
    for(i=0; i<n; i++){
        cout<<array[i]<<"  ";
    }
}

void merge(int array[], int low, int mid, int high){
    i=low; //low of first half
    j=mid+1; //low of second half 
    int k=low; // LOW for temporary new sorted array that we will form
    int temp[n];
    
    // Its like while low of each list <= high
    while(i<=mid && j<=high){  //?????????????????????????????
        // if array at i < array at j...
        if(array[i] < array[j]){
            temp[k] = array[i]; // set array at k to be equal to array at i
            i++; //move foward by one
            k++; //move foward byone
            
        } 
        else // if array at j < array at i...
        {
            temp[k]=array[j]; // set array at k to be equal to array at j instead
            k++; //move foward by one
            j++; //move foward by one
        }
            
    }
    
    //mop remaining values
    while(i<=mid){
        temp[k]=array[i];
            i++;
            k++;    
    }
    
    while(j<=high){
        temp[k]=array[j];
            k++;
            j++;
    }
    //copy to original array
    for(i=low; i<k; i++)
    array[i]=temp[i];
}

void mergesort(int array[], int low, int high)
{
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        // Split the data into two half.
        mergesort(array, low, mid);
        mergesort(array, mid+1, high);
 
        // Merge them to get sorted output.
        merge(array, low, mid, high);
    }
}

 
 int main(){
    getvalues();
    mergesort(array, 0, n-1);
    display();
}

但是，我不明白 merge （不是 mergesort）函数中最后 2 个 while 循环的目的。我以为只要 1 就足够了。

有人可以向我解释一下为什么我们需要 2 个额外的 while 循环吗？

帮助测试 我还需要有关如何在退出第一个 while 循环后测试结果的帮助。我如何打印该结果？我尝试过使用 display() 函数以及其他返回奇怪结果或根本不起作用的方法。我也可以得到帮助吗？

下面是我在合并函数中的第一个 while 循环之后尝试使用显示进行打印后得到的“奇怪的结果”。由于数组未排序，它甚至会导致结果失真。如何在 C++ 中测试打印？

Answer 1

初始化：我们有两个排序数组 A 和 B，我们将它们合并到一个排序数组 C 中。

合并功能的思路是：

1.我们使用两个索引同时迭代两个数组，每个索引对应一个数组。 虽然两个数组都有剩余元素，但我们比较当前索引处的元素。较小的元素被附加到组合数组 C 中。 我们增加从中取出较小元素的数组的索引，并增加数组 C 的索引。

2. 如果数组 A 在 B 数组之前到达末尾，我们就知道另一个数组中的剩余元素已经排序。因此，我们只需将该数组中的剩余元素复制到 C 中即可。 这是在主合并循环之后的单独循环中完成的。（这是第二个 while 循环）

3. 第三个 while 循环与 2 相同，但检查相反。 （如果 B 在 A 之前到达终点）。

希望对你有帮助，祝你考试顺利！