c++ - 递归合并排序

我试图编写一个合并排序程序，以及它在运行时如何选择垃圾值。

该程序如下。
（我使用了几条提示进行调试）

#include <iostream>

using namespace std;

void merge(int array[], int low, int mid, int high){
    int temp[10];
    int j = mid;
    int i = low;

    cout<<endl<<"Entered merge"<<endl;
    cout<<"low = "<<low<<" mid = "<<mid<<"high = "<<high<<endl;

    for(int i=0;i<10;i++){
        temp[i]=array[i];
    }

    //cout<<"checkpoint1"<<endl;

    for(int k=low;k<=high;k++){
        if(i>j) {
            cout<<"level1"<<endl;
            //cout<<"array[k] = "<<array[k]<<" temp[j] = "<<temp[j]<<endl;
            array[k]=temp[j++];

        }
        else if(j>high) {
            cout<<"level2"<<endl;
            //cout<<"array[k] = "<<array[k]<<" temp[i] = "<<temp[i]<<endl;
            array[k]=temp[i++];
        }
        else if(temp[i]<temp[j]) {
            cout<<"level3"<<endl;
            //cout<<"array[k] = "<<array[k]<<" temp[i] = "<<temp[i]<<endl;
            array[k]=temp[i++];
        }
        else {
            cout<<"level4"<<endl;
            //cout<<"array[k] = "<<array[k]<<" temp[j] = "<<temp[j]<<endl;
            array[k]=temp[j++];
        }
    }


    for(int i=0;i<10;i++){
       cout<<array[i]<<"  ";
   }
   cout<<endl;

}

int m_sort(int arr[],int low,int high){
    cout<<endl<<"Entered m_sort";
    /*for(int i=0;i<10;i++){
       cout<<arr[i]<<"  ";
    }*/
   cout<<endl<<"low = "<<low<<"  High = "<<high;

    if(low==high) return low;
    int mid = (low + high)/2;

    int merge_low = m_sort(arr,low,mid);
    int merge_mid = m_sort(arr,mid+1,high);
    cout<<"entering merge function"<<"  merge_low = "<<merge_low<<endl;
    cout<<"entering merge function"<<"  merge_Mid = "<<merge_mid<<endl;
    merge(arr,merge_low,merge_mid,high);
    cout<<"merge_low = "<<merge_low<<endl;
    cout<<"merge_mid = "<<merge_mid<<endl;
}


int main()
{
   int a[] = {0,9,8,7,6,5,4,3,2,1};
   int low = 0;
   int high = 9;

   cout<<endl<<"Before sorting:"<<endl;
   for(int i=0;i<10;i++){
       cout<<a[i]<<"  ";
   }
   cout<<endl;

   m_sort(a,low,high);

   cout<<endl<<"After sorting:"<<endl;
   for(int i=0;i<10;i++){
       cout<<a[i]<<"  ";
   }
   cout<<endl;
   return 0;
}

输出如下

Compiling the source code....
$g++ main.cpp -o demo -lm -pthread -lgmpxx -lgmp -lreadline 2>&1

Executing the program....
$demo

Before sorting:
0 9 8 7 6 5 4 3 2 1

Entered m_sort
low = 0 High = 9
Entered m_sort
low = 0 High = 4
Entered m_sort
low = 0 High = 2
Entered m_sort
low = 0 High = 1
Entered m_sort
low = 0 High = 0
Entered m_sort
low = 1 High = 1entering merge function merge_low = 0
entering merge function merge_Mid = 1

Entered merge
low = 0 mid = 1high = 1
level3
level4
0 9 8 7 6 5 4 3 2 1
merge_low = 0
merge_mid = 1

Entered m_sort
low = 2 High = 2entering merge function **merge_low = 6297440**
entering merge function merge_Mid = 2

Entered merge
**low = 6297440 mid = 2high = 2**
0 9 8 7 6 5 4 3 2 1
merge_low = 6297440
merge_mid = 2

Entered m_sort
low = 3 High = 4
Entered m_sort
low = 3 High = 3
Entered m_sort
low = 4 High = 4entering merge function merge_low = 3
entering merge function merge_Mid = 4

Entered merge
low = 3 mid = 4high = 4
level4
level2
0 9 8 6 7 5 4 3 2 1
merge_low = 3
merge_mid = 4
entering merge function merge_low = 6297440
entering merge function merge_Mid = 6297440

Entered merge
low = 6297440 mid = 6297440high = 4
0 9 8 6 7 5 4 3 2 1
merge_low = 6297440
merge_mid = 6297440

Entered m_sort
low = 5 High = 9
Entered m_sort
low = 5 High = 7
Entered m_sort
low = 5 High = 6
Entered m_sort
low = 5 High = 5
Entered m_sort
low = 6 High = 6entering merge function merge_low = 5
entering merge function merge_Mid = 6

Entered merge
low = 5 mid = 6high = 6
level4
level2
0 9 8 6 7 4 5 3 2 1
merge_low = 5
merge_mid = 6

Entered m_sort
low = 7 High = 7entering merge function merge_low = 6297440
entering merge function merge_Mid = 7

Entered merge
low = 6297440 mid = 7high = 7
0 9 8 6 7 4 5 3 2 1
merge_low = 6297440
merge_mid = 7

Entered m_sort
low = 8 High = 9
Entered m_sort
low = 8 High = 8
Entered m_sort
low = 9 High = 9entering merge function merge_low = 8
entering merge function merge_Mid = 9

Entered merge
low = 8 mid = 9high = 9
level4
level2
0 9 8 6 7 4 5 3 1 2
merge_low = 8
merge_mid = 9
entering merge function merge_low = 6297440
entering merge function merge_Mid = 6297440

Entered merge
low = 6297440 mid = 6297440high = 9
0 9 8 6 7 4 5 3 1 2
merge_low = 6297440
merge_mid = 6297440
entering merge function merge_low = 6297440
entering merge function merge_Mid = 6297440

Entered merge
low = 6297440 mid = 6297440high = 9
0 9 8 6 7 4 5 3 1 2
merge_low = 6297440
merge_mid = 6297440

After sorting:
0 9 8 6 7 4 5 3 1 2

请帮助我了解该程序中发生了什么。

提前致谢！！

最佳答案

您正在获取垃圾值，因为m_sort中没有return语句。

我想您要编写的代码是这样的

m_sort(arr,low,mid);
m_sort(arr,mid+1,high);
merge(arr,low,mid,high);