原创 分冶排序C++实现

#include <iostream>
using namespace std;
class merge_sort
{
 public:
  merge_sort(){};
  ~merge_sort(){delete[] a;};
  void input();
  void output();
  void msort();
 private:
  int *a;
  int leng;
  void mergesort(int p,int r);
  void merge(int p,int q,int r);
};
void merge_sort::input()
{
 cout<<"请输入参加排序整数的个数\n";
 cin>>leng;
 a=new int[leng];
 for(int i="0";i<leng;i++)
 {
  cout<<"请输入第"<<i+1<<"个整数\n";
  cin>>a;
 }
}
void merge_sort::output()
{
 cout<<"现在数组中的数字分别为：\n";
 for(int i="0";i<leng;i++)
 {
  cout<<a<<"\t";
 }
 cout<<endl;
}
void merge_sort::msort()
{
 mergesort(0,leng-1);
}
void merge_sort::mergesort(int p,int r)
{
 if(p<r)
 {
  int q=(p+r)/2;
  mergesort(p,q);
  mergesort(q+1,r);
  merge(p,q,r);
 }
}
void merge_sort::merge(int p,int q,int r)
{
 int *temp=new int[r-p+1];
 int i,j,k;
 for(i=p,j=q+1,k=0;i<=q&&j<=r;)
 {
  if(a<a[j])
  {
   temp[k++]=a[i++];
  }
  else//a>=a[j]
  {
   temp[k++]=a[j++];
  }
 }
 for(;i<=q;)
 {
        temp[k++]=a[i++];
 }
 for(;j<=r;)
 {
        temp[k++]=a[j++];
 }
 for(i=0;i<=r-p;i++)
 {
  a[p+i]=temp;
 }
 delete[] temp;
}
int main()
{
 merge_sort test;
 test.input();
 test.output();
 cout<<"排序中......\n";
 test.msort();
 test.output();
 return 0;
}