返回顶部

收藏

合并排序(递归调用)

更多
#include <iomanip.h>//调用setw

#include <iostream.h>  //将b[0]至b[right-left+1]拷贝到a[left]至a[right]

template <class T> 

void Copy(T a[],T b[],int left,int right)

{  int size=right-left+1;

   for(int i=0;i<size;i++)

   {  

   a[left++]=b[i];

   }

}  //合并有序数组a[left:i],a[i+1:right]到b,得到新的有序数组b

template <class T> 

void Merge(T a[],T b[],int left,int i,int right)

{  int a1cout=left,//指向第一个数组开头  

   a1end=i,//指向第一个数组结尾  

   a2cout=i+1,//指向第二个数组开头  

   a2end=right,//指向第二个数组结尾  

   bcout=0;//指向b中的元素    

for(int j=0;j<right-left+1;j++)//执行right-left+1次循环

{  if(a1cout>a1end)

 {   b[bcout++]=a[a2cout++]; 

     continue; }  //如果第一个数组结束,拷贝第二个数组的元素到b

  if(a2cout>a2end) 

 {

    b[bcout++]=a[a1cout++];

    continue; }  //如果第二个数组结束,拷贝第一个数组的元素到b

if(a[a1cout]<a[a2cout])

{  b[bcout++]=a[a1cout++];

   continue; }  //如果两个数组都没结束,比较元素大小,把较小的放入b

 else 

 {  b[bcout++]=a[a2cout++];

    continue;} } }  //对数组a[left:right]进行合并排序

template <class T> 

void MergeSort(T a[],int left,int right)

 {  T *b=new

    int[right-left+1];

  if(left<right)

{ 

  int i=(left+right)/2;//取中点 

  MergeSort(a,left,i);//左半边进行合并排序

  MergeSort(a,i+1,right);//右半边进行合并排序

  Merge(a,b,left,i,right);//左右合并到b中

  Copy(a,b,left,right);//从b拷贝回来

 }

} 

 int main()

 { int n; 

  cout<<"请输入您将要排序的数目:"; cin>>n; 

 int *a=new int[n];  cout<<"请输入相应的数字:";

 for(int i=0;i<n;i++)

 {  cin>>a[i]; } 

 MergeSort( a, 0, n-1); cout<<"排序结果:";

 for(int j=0;j<n;j++)

 {  cout<<setw(5)<<a[j];  } 

    cout<<endl;

    return 1;

 } 

标签:c/c++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. yuer 发表 2018-07-27 08:46:07 coredump之百米之内必有解药
  2. hev 发表 2018-04-28 06:11:38 一个简单、轻量的 Linux 协程实现
  3. hev 发表 2017-10-19 15:56:11 FSH – 助你接入私有网络中的 Linux 终端
  4. gonwan 发表 2015-04-15 08:03:07 Database Access Layer in C++
  5. gonwan 发表 2015-12-28 08:41:13 Basic Usage of Boost MultiIndex Containers
  6. gonwan 发表 2016-01-19 03:37:54 Coroutines in C++/Boost
  7. Haoxiang Li 发表 2017-10-25 20:29:02 MXNet C++ Deployment
  8. yuer 发表 2017-10-20 07:52:47 基于leveldb的持久消息队列SDK
  9. yuer 发表 2017-10-07 07:51:32 c++11完美转发
  10. 博主 发表 2016-09-03 00:00:00 C++编译期类型信息的利用
  11. yuer 发表 2017-09-06 03:03:29 libcurl访问unix socket
  12. yuer 发表 2017-09-07 08:14:58 valgrind检测php扩展的warning

发表评论