归并排序

冬冬

//下面两个函数全都是基于递归的的排序方法，效率都是相当不错的
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void MergeSort(int *array ,int first ,int last);//array为要排序的数组，first为要排序的开始位置，last为终止位置
void Merge(int *array,int p,int q,int r);//进行归并的函数
void Print(int *array,int begin,int end);  
void QuickSort(int *array,int fist,int last);  快排函数
int main()
{
 int a[10];
 int t;
 srand(time(NULL));
 
 for (int i=0;i<10;i++)
 {
  t=rand()%100;
  a[i]=t;
 }
 cout<<"排序前——"<<endl;
 Print(a,0,9);
// MergeSort(a,0,9);//归并
 QuickSort(a,0,9);
 cout<<"排序后——"<<endl;
 Print(a,0,9);
 return 0;
}

void Merge(int *array,int p,int q,int r)
{
 int i,k;
 int begin1,end1,begin2,end2;
 int *temp = (int *)malloc((r-p+1)*sizeof(int));
 begin1=p;
 end1=q;
 begin2=q+1;
 end2=r;
 k=0;
 while((begin1<=end1)&&(begin2<=end2))
 {
  if (array[begin1]<array[begin2])
  {
   temp[k]=array[begin1];
   begin1++;
  }
  else
  {
   temp[k]=array[begin2];
   begin2++;
  }
  k++;
 }
 while (begin1<=end1)
 {
  temp[k++]=array[begin1++];
 }
 while (begin2<=end2)
 {
  temp[k++]=array[begin2++];
 }
 for (i=0;i<=(r-p);i++)
 {
  array[p+i]=temp[i];
 }
 free(temp);
 
}
void MergeSort(int *array ,int first ,int last)
{
 int mid = 0;
 if (first <last)
 {
  mid = (first+last)/2;
  MergeSort(array,first,mid);
  MergeSort(array,mid+1,last);
  Merge(array,first , mid ,last );
 }
}

void Print(int *array,int begin,int end)//begin，end为数组索引位置
{
 for (int i=begin;i<=end;i++)
 {
  cout<<array[i]<<"  ";
 }
 cout<<endl;
}
void QuickSort(int *array,int first,int last)
{
 int base=array[first];
 int x=first,y=last;
 if (x>=y)
 {
  return;
 }
 while(x<y)
 {
  while(x<y && array[y]>=base)
  y--;
  array[x]=array[y];
  while(x<y && array[x]<=base)
  x++;
  array[y]=array[x];
 }
 
 array[y]=base;
 QuickSort(array,first,x);
 QuickSort(array,x+1,last);
}

Be_envious

有点注释,或者能说一下算法的核心思想就好了
一上来就上一段代码
不是那么好理解

Cocol

看看学习学习

星晴☆之乐

有二路归并和三路归并一起的那种吗？他们在算法有什么不一样？还有怎么编比较次数和移动次数？

星晴☆之乐

三路归并怎么写啊？

sheri528