归并排序
本帖最后由 冬冬 于 2011-7-23 10:25 编辑//下面两个函数全都是基于递归的的排序方法，效率都是相当不错的
#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;
int t;
srand(time(NULL));
for (int i=0;i<10;i++)
{
t=rand()%100;
a=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<array)
{
temp=array;
begin1++;
}
else
{
temp=array;
begin2++;
}
k++;
}
while (begin1<=end1)
{
temp=array;
}
while (begin2<=end2)
{
temp=array;
}
for (i=0;i<=(r-p);i++)
{
array=temp;
}
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<<"";
}
cout<<endl;
}
void QuickSort(int *array,int first,int last)
{
int base=array;
int x=first,y=last;
if (x>=y)
{
return;
}
while(x<y)
{
while(x<y && array>=base)
y--;
array=array;
while(x<y && array<=base)
x++;
array=array;
}
array=base;
QuickSort(array,first,x);
QuickSort(array,x+1,last);
}
有点注释,或者能说一下算法的核心思想就好了
一上来就上一段代码
不是那么好理解 看看学习学习 有二路归并和三路归并一起的那种吗？他们在算法有什么不一样？还有怎么编比较次数和移动次数？ 三路归并怎么写啊？ {:5_110:}
页:
[1]