归并排序c语言（归并排序算法）

本文目录

• 归并排序算法
• C语言排序的方法
• 随机生成10个待排序数据，用C语言写出二路归并排序算法
• C语言 归并排序的完整代码
• 输入一组整数对该序列进行简单选择和归并排序（数据结构用c语言写啊）
• 求一个单链表归并排序算法，C语言的源代码，急需！

归并排序算法

两种归并排序算法的实现：二路归并排序和基本归并排序（虚拟消除递归的二路归并排序）
#define ARRAY_SIZE 1024
int B; //使用一个全局变量，避免归并排序中每次都重新申请和释放空间造成的开销
template 《typename T》
void Merge(T A, int l, int m, int h)
{
int i = l;
int j = m+1;
int k = 0;
while(i《=m&&j《=h)
{
if(A)
{
B;
i++;
}
else
{
B;
j++;
}
}
while(i《=m)
{
B;
}
while(j《=h)
{
B;
}
for(i=l; i《=h; i++)
{
A;
}
}
//二路归并排序的实现
template 《typename T》
void MergeSort(T a, int l, int h)
{
int m = (h+l)/2;
if(l》=h)
{
return;
}
if(l+1==h)
{
if(a)
{
std::swap(a);
}
return;
}
MergeSort(a, l, m);
MergeSort(a, m+1, h);
Merge(a, l, m, h);
}
//将a经过步长s归并到b中，n表示数组的大小
template 《typename T》
void Merge2(T a, int s, int n)
{
int m = 0;
//从头至尾按照步长s进行相邻数据的合并
for(int i=0; i《n; i+=2*s)
{
int j = i; //合并的第一组数的起始位置
int k = i+s; //合并的第二组数的起始位置
int jE = i+s; //合并的第一组数的起始位置
int kE = i+2*s; //合并的第二组数的起始位置
while((j《jE)&&(k《kE)&&j《n && k《n)
{
if(a)
{
b;
j++;
}
else
{
b;
k++;
}
}
while((j《jE)&&(j《n))
{
b;
}
while((k《kE)&&(k《n))
{
b;
}
}
}
//基本归并排序，虚拟消除递归
template 《typename T》
void MergeSort2(T a, int n)
{
int s = 1; //merge 的步长
T* b = new T;
while(s《n)
{
Merge2(a, b, s, n); //由a合并到b
s += s;
Merge2(b, a, s, n); //由b合并到a
s += s;
}
delete b;
}
//使用如下代码在VS2005中可以对两种归并排序进行性能比较，
//基本归并排序的时间性能稍微好一点，基本归并排序直接对数据按步长Merge，
//而二路归并排序需要将数据先不断的分层，到为一个或者两个元素时再进行Merge
void main()
{
int * p = new int;
int i = 0;
for(i=0; i《ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort(p, 0, ARRAY_SIZE-1);
for(i=0; i《ARRAY_SIZE; i++)
{
*(p+i) = rand()%ARRAY_SIZE;
}
MergeSort2(p, ARRAY_SIZE);
delete p;
}

C语言排序的方法

现在流行的排序有：直接插入排序、冒泡排序、简单选择排序、希尔排序、快速排序、堆排序、归并排序、基数排序。
对n个记录进行选择排序的方法是：通过n-i次关键字之间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1《=i《=n）个记录进行交换，当i等于n时所有记录都已有序排列。
void selectsort(int data,int n)
{
int i,j,k,temp;
for(i=0;i《n-1;i++)
{
k=i;
for(j=i+1;j《n;j++)
{
if(data) k=j;
if(k!=i)
{
temp=data=temp;
}//if
}//for
}//for
}//selectsort

随机生成10个待排序数据，用C语言写出二路归并排序算法

#include《stdio.h》
#include《stdlib.h》
#include《time.h》
int b, int l, int m, int r )
{
int i = l, j = m + 1, k = l;
while( ( i 《= m ) && ( j 《= r ) )
if( c;
else d;
if( i 》 m )
for( int q = j; q 《= r; q++ ) d;
else
for( int q = i; q 《= m; q++ ) d;
}void Copy( int c, int n1, int n2 )
{
for( int i = n1; i 《= n2; i++ )
c;
}void MergeSort( int a, int left, int right )
{
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 ); //复制到数组a
}
}int main()
{
int a, i;
srand( time( 0 ) );
for( i = 0; i 《 10; i++ ) a = rand() % 100; //随机生成
for( i = 0; i 《 10; i++ ) //输出随机生成的数据
printf( "%d\t", a );
printf( "\n" );
MergeSort( a, 0, 9 );
for( i = 0; i 《 10; i++ ) //输出排序后的结果
printf( "%d\t", a );
printf( "\n" );
return 0;
} //在vc++6.0上调试运行成功。若有不明白的地方，call me!!!

C语言 归并排序的完整代码

#include 《stdio.h》 

int main()

{int a;

int i,j,k,n1,n2,n3;

i=j=k=0;

n1=5;

n2=4;

n3=n1+n2;

for(;i《n1&&j《n2;)

if(a;

else c;

for(;i《n1;)c;

for(;j《n2;)c;

for(k=0;k《n3;k++)

printf("%d ",c);

printf("\n");  

return 0;

} 

输入一组整数对该序列进行简单选择和归并排序（数据结构用c语言写啊）

给你一个归并排序的具体算法和分析：
两路归并排序算法思路:
①.
把n个记录看成n个长度为l的有序子表
;
②.
进行两两归并使记录关键字有序,得到n/2个长度为2的有序子表;
③.
重复第②步直到所有记录归并成一个长度为n的有序表为止;
具体算法:
//
归并操作
template
static
void
merge
(typearray,
int
p,
int
q,
int
r){
int
i
,
k
;
int
begin1
,
end1
,
begin2
,
end2
;
int*
temp
=
(int*)malloc((r-p)*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)
;
}
//--------------------------------------------------------------------------------
template
void
mergesort(typearray,
unsigned
int
first,
unsigned
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)
;
}
}

求一个单链表归并排序算法，C语言的源代码，急需！

//MergeSort.cpp
#include 《iostream.h》
#include 《conio.h》
#define MAXSIZE 20
#define LENGTH 7
typedef int RedType;
typedef struct //SqList structure
{ RedType r; //Records Type
int length;
}SqList;
typedef SqList RcdType;
void Merge(RcdType SR,RcdType &TR,int i,int m,int n) //Merge() function
{ int j,k;
for(j=m+1,k=i;i《=m&&j《=n;++k)
{ if(SR.r)
TR.r;
else
TR.r;
}
while(i《=m)
TR.r;
while(j《=n)
TR.r;
}//end of Merge() function
void MSort(RcdType SR,RcdType &TR1,int s, int t) //MSort() function
{ int m;
RcdType TR2;//;
if(s==t)
TR1.r;
else
{ m=(s+t)/2;
MSort(SR,TR2,s,m);
MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t);
}//end of else
}//end of MSort() function
void MergeSort(SqList &L) //MergeSort() function
{
MSort(L,L,1,L.length);
}//end of MergeSort() function
void main() //main function
{ int i;
SqList L;//={{0,49,38,65,97,76,13,27,},LENGTH};
cout《《"MergeSort.cpp"《《endl《《"============="《《endl《《endl;
cout《《"Please input the length of SqList L: 《eg. 7》 ";
cin》》L.length;
cout《《"Please input the disordered array L.r: 《eg. {49,38,65,97,76,13,27,...}》"《《endl;
for(i=1;i《=L.length;i++)
cin》》L.r;
MergeSort(L);
cout《《endl《《"The sorted array L.r: ";
for(i=1;i《=L.length;i++)
cout《《L.r《《" ";
cout《《endl;
cout《《"...OK!..."《《endl;
getch();
}//end of main() function我以前的，可以调试的
应该符合你要求，只是很少部分你自己改一下，比如数的个数
输入改为 rand()随即输入,刚才粘贴错了