合并排序的分治求解方法

排序

输入 8

        4  9  -5 2  96  0  13  -6

输出 -6  -5  0  2  4  9  13  96

 

#include <iostream>
#include <algorithm>
using  namespace std;
int a[105];
int b[105];

void  merge(int a[], int b[], int bott, int mid,int top)//合并
{
   int i=bott;int j=mid+1;
   int k=bott;
   while(i<=mid||j<=top)
   {
       if(i>mid)
       {
           for(;j<=top;j++)
           {
               b[k++]=a[j];
           }
       }
       if(j>top)
       {
           for(;i<=mid;i++)
           {
               b[k++]=a[i];
           }
       }
       if(a[i]<=a[j])
       {
           b[k++]=a[i];
           i++;
       }
       else 
       {
           b[k++]=a[j];
           j++;
       }
   }
}

void copy(int a[], int b[],int  bott,int top)
{
    for(int i=bott;i<=top;i++)
    {
        a[i]=b[i];
    }
}
    





void mergeSort(int a[], int bott, int top)
   {
      if (bott < top) {    //至少有2个元素
      int mid = (bott + top)/2;  //取中点
      mergeSort(a, bott, mid);
      mergeSort(a, mid + 1, top);
      merge(a, b, bott, mid, top);  //合并到数组b
      copy(a, b, bott, top);    //复制回数组a
      }
   }



int main()
{
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    mergeSort(a,1,n);
    for(int i=1;i<=n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}