//1.当元素个数为1时，终止排序
//2.否则将待排序元素分成大小规模相同的两个子集合,分别对两个子集合排序(
//3.最终将排序好的子集合合并为所要求的排序好的集合

#include<iostream>
#include<cstdlib>
using namespace std;

void hb(int s[],int tem[],int left,int middle,int right)  //合并算法
{
 int i=left;
 int j=middle+1;

 int k=left-1;                  //临时数组开头处
 while(i<=middle && j<=right)
 {
  if(s[i] <= s[j])
   tem[++k] = s[i++];
  else
   tem[++k] = s[j++];
 }

 if(i > middle)
 {
  int q;
  for(q=j;q<=right;q++)
   tem[++k] = s[q];
 }
 else
 {
  int q;
  for(q=i;q<=middle;q++)
   tem[++k] = s[q];
 }
 for(int q=left;q<=right;q++)        //把排序好的数重新放回S中
  s[q] = tem[q];
 
}

void mergesort(int s[],int left,int right)   //排序算法
{ 
 if(left == right || left+1 == right)
 {
  if(s[left] > s[right])
  {
   int temp = s[left];
   s[left] = s[right];
   s[right] = temp;
  }
 }
 
 else
 {
  int middle = (left + right) / 2;
  mergesort(s,left,middle);
  mergesort(s,middle+1,right);
  int tem[20]; //临时数组
  
  hb(s,tem,left,middle,right);
 }
}

int main()
{
 int s[] = {1,6,9,4,3,8,11};
 int left = 0;
 int right = sizeof s / sizeof *s - 1;
 cout<<"排序前: "<<endl;
 for(int i=0;i<=right;i++)
  cout<<s[i]<<"  ";
 cout<<endl;

 mergesort(s,left,right);

 cout<<"排序后: "<<endl;
 for(i=0;i<=right;i++)
  cout<<s[i]<<"  ";
 cout<<endl;
}
 

评论