-2

スタックメモリはどのように割り当てられますか?
ここで再帰がどのように機能するのか理解できません
。パーティション関数の「4 行目」にコメントした行を説明してください。この行がいつ実行されるかを説明しますか?

  void partition(int arr[],int low,int high){

        int mid;

        if(low<high){
             mid=(low+high)/2;
             partition(arr,low,mid);
             partition(arr,mid+1,high);   //line 4
             mergeSort(arr,low,mid,high);
        }
    }

    void mergeSort(int arr[],int low,int mid,int high){

        int i,m,k,l,temp[MAX];

        l=low;
        i=low;
        m=mid+1;

        while((l<=mid)&&(m<=high)){

             if(arr[l]<=arr[m]){
                 temp[i]=arr[l];
                 l++;
             }
             else{
                 temp[i]=arr[m];
                 m++;
             }
             i++;
        }

        if(l>mid){
             for(k=m;k<=high;k++){
                 temp[i]=arr[k];
                 i++;
             }
        }
        else{
             for(k=l;k<=mid;k++){
                 temp[i]=arr[k];
                 i++;
             }
        }

        for(k=low;k<=high;k++){
             arr[k]=temp[k];
        }
4

1 に答える 1

0

MergSort のグラフィカルな表現であるこの画像を確認してくださいここに画像の説明を入力

最初の行は元のアリを表しています。ここで、パーティション関数が呼び出されます。3 行目は {38,27,43,3} でパーティション関数を呼び出し、4 行目は {9,82,10} でパーティション関数を呼び出し、それらを小さなパーティションに分割し、同じ関数が再度呼び出されます。このプロセスは、Low < High まで続きます。図では 4 行目まで。その後、元に戻り、MargSort 関数によってこれらのパーティションのマージが開始されます。

于 2013-10-10T06:45:55.320 に答える