归并排序算法c语言

⑴ 求大神解释下二路归并排序法，C语言。

#include <stdio.h>
#include<malloc.h>
void merge(int *a, int beg, int mid, int end)// 合并子序列
{
int i=beg, j=mid+1, cnt=0;
int *a1;
a1=(int*)malloc((end-beg+1)*sizeof(int));

while(i<=mid && j<=end)
{
a1[cnt++]=a[i]<=a[j]? a[i++]:a[j++];
}
while(i<=mid)
{
a1[cnt++]=a[i++];
}
while(j<=end)
{
a1[cnt++]=a[j++];
}
for(cnt=0, i=beg; i<=end; cnt++,i++)
{
a[i]=a1[cnt];
}

}
void merge_sort(int*a, int beg, int end)//二路归并排序
{
int mid=0;
if(beg<end)
{
mid=(beg+end)/2;//左右两部分分解
merge_sort(a, beg, mid);//左半部分排序
merge_sort(a, mid+1, end);//右半部分排序
merge(a, beg, mid, end);//左右两部分合并
}
}

int main(void)
{
int a[10]={12,54,14,25,21,87,48,1,547,12};

int i=0,j=0,k=0;
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');
merge_sort(a, 0, 9);
for(i=0;i<10;i++)
{
printf("%4d",a[i]);
}
putchar('\n');

}

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

#include <stdio.h>

int main()

{int a[]={1,3,5,7,9},b[]={2,4,6,8},c[10];

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[i]<b[j])c[k++]=a[i++];

else c[k++]=b[j++];

for(;i<n1;)c[k++]=a[i++];

for(;j<n2;)c[k++]=b[j++];

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

printf("%d ",c[k]);

printf(" ");

return 0;

}

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

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

⑷ 高分送！！如何用C语言实现归并排序算法！！！

#include <iostream>

using namespace std;

void merge(int array[],int left,int right)
{
int temparray[right];
for(int j=left;j<=right;j++)
{
temparray[j]=array[j];
}
int middle=(left+right)/2;
int index1=left;
int index2=middle+1;
int i=left;
while((index1<=middle)&&(index2<=right))
{
if(temparray[index1]<temparray[index2]) array[i++]=temparray[index1++];
else array[i++]=temparray[index2++];
}
while(index1<=middle) array[i++]=temparray[index1++];
while(index2<=right) array[i++]=temparray[index2++];

}
void sort(int array[],int left,int right)
{
if(left<right)
{
int middle=(left+right)/2;
sort(array,left,middle);
sort(array,middle+1,right);
merge(array,left,right);
}

}

这个不是特别的完美，但是大体上就是这么个思路啦~而且因为语法不严谨，貌似只能在c++下运行~建议看看youku上的数据结构课，然后你就会发现全明白了~
如果在c语言下运行，int temparray[right];这句话里面的right要改成你需要用的数~

⑸ C语言排序算法一共多少种

1. 选择排序
   

#include<iostream>
usingnamespacestd;
voidselect_sort(intarr[],intnum);
voidoutput_array(intarr[],intnum);
intmain()
{
inta[10];
for(inti=0;i<10;i++)
{
cin>>a[i];
}
select_sort(a,10);
output_array(a,10);
return0;
}
voidselect_sort(intarray[],intn)//形参array是数组名
{
inti,j,k,t;
for(i=0;i<n-1;i++)
{
k=i;//先设第i个就为最小
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;//通过循环，得到k为最小
t=array[k];//交换a[i]和a[k]
array[k]=array[i];
array[i]=t;
}
return;
}
voidoutput_array(intarr[],intnum)
{
inti;
for(i=0;i<num;i++)
{
cout<<arr[i];
cout<<endl;
}
return;
}

2.冒泡排序

#include<stdio.h>
intmain()
{
	inti,j,a[10],t;
	for(i=0;i<10;i++)
		scanf("%d",&a[i]);
	for(i=0;i<10;i++)
		for(j=i+1;j<10;j++)
			if(a[i]>a[j])
			{
				t=a[j];
				a[j]=a[i];
				a[i]=t;
			}
			for(i=0;i<10;i++)
				printf("%d",a[i]);
			return0;
}

3.堆排序

#include<iostream>
usingnamespacestd;
voidpaii(inta[20],inti,intm)
{
	intk,t;
t=a[i];
k=2*i+1;
while(k<m)
{
if((k<m-1)&&(a[k]<a[k+1]))
k++;
if(t<a[k])
{
a[i]=a[k];
i=k;
k=2*i+1;
}
elsebreak;
}
a[i]=t;
}
voidipai(inta[20],intn)
{
inti,k;
for(i=n/2-1;i>=0;i--)
paii(a,i,n);
for(i=n-1;i>=1;i--)
{
k=a[0];
a[0]=a[i];
a[i]=k;
paii(a,0,i);
}}
intmain()
{
inta[10],i;
for(i=0;i<10;i++)
cin>>a[i];
ipai(a,10);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
}

4.快速排序

#include<iostream>
usingnamespacestd;
voidQuicksort(inta[],intlow,inthigh)
{
if(low>=high)
{
return;
}
intfirst=low;
intlast=high;
intkey=a[first];
while(first<last)
{
while(first<last&&a[last]>=key)
--last;
a[first]=a[last];
while(first<last&&a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}


intmain()
{
inti,a[100],x,n=0;
	while(cin>>x)
	{
		a[n]=x;
		n++;
	}
	n--;
	Quicksort(a,0,n);
	for(i=0;i<=n;i++)
		cout<<a[i]<<"";
	cout<<endl;
return0;
}

5. 基数排序

#include<stdio.h>
#include<stdlib.h>
intmain(){
intdata[10]={73,22,93,43,55,14,82,65,39,81};//对十个数进行排序
inttemp[10][10]={0};//构造一个临时二维数组，其值为0
intorder[10]={0};//构造一维数组，其值为0
inti,j,k,n,lsd;
k=0;n=1;
for(i=0;i<10;i++)printf("%d",data[i]);//在排序前，对这10个数打印一遍
putchar('
');
while(n<=10){
for(i=0;i<10;i++){
lsd=((data[i]/n)%10);//lsd先对个位取余，然后再对十位取余，注意循环
temp[lsd][order[lsd]]=data[i];//temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯
order[lsd]++;//需要区分的是lsd和order[lsd]，这两个不是一样的概念嗷
}
printf("
重新排列:");
for(i=0;i<10;i++){
if(order[i]!=0)
for(j=0;j<order[i];j++){


data[k]=temp[i][j];
printf("%d",data[k]);
k++;
}
order[i]=0;
}
n*=10;//第二次用十位
k=0;
}
putchar('
');
printf("
排序后:");
for(i=0;i<10;i++)printf("%d",data[i]);
return0;
}

6.希尔排序

#include<iostream>
usingnamespacestd;
voidshell_sort(inta[],intn);
intmain()
{
intn,a[10000];
cin>>n;
for(inty=0;y<n;y++)
cin>>a[y];
shell_sort(a,n);
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<endl;
}

voidshell_sort(inta[],intn)
{
intgap,k,temp;//定义增量；
for(gap=3;gap>0;gap--)//设置初始增量，递减；
{
for(inti=0;i<gap;i++)//按增量分组；
{
for(intj=i+gap;j<n;j=j+gap)//每组分别比较大小；
{
if(a[j]<a[j-gap])
{
temp=a[j];
k=j-gap;
while(k>=0&&a[k]>temp)
{
a[k+gap]=a[k];
k=k-gap;
}

a[k+gap]=temp;
}
}
}
}
}

7.归并排序

#include<iostream>
usingnamespacestd;
voidMergeSort(intp[],ints,intm,intt)
{
intq[100];//q[100]用来存放排好的序列
	inti=s;
	intj=m+1;
	intk=s;
while(i<=m&&j<=t)
	{
		if(p[i]<=p[j])
			q[k++]=p[i++];
		else
			q[k++]=p[j++];
	}
	if(i<=m)
		while(i<=m)
			q[k++]=p[i++];
		elsewhile(j<=t)
			q[k++]=p[j++];
		for(intn=s;n<=t;n++)
p[n]=q[n];
}
voidMerge(intp[],ints,intt)
{
	if(s<t)
	{
		intm=(s+t)/2;//将数组分成两半
		Merge(p,s,m);//递归拆分左数组
		Merge(p,m+1,t);//递归拆分右数组
		MergeSort(p,s,m,t);//合并数组
}
}
intmain()
{
intn;
	intp[100];
	cin>>n;
	for(inti=0;i<n;i++)
cin>>p[i];
	Merge(p,0,n-1);
	for(intj=0;j<n;j++)
		cout<<p[j]<<"";
	cout<<endl;
	return0;
}

排序方法基本就这些，还有双向冒泡这种拓展的排序方法，还有直接排序如桶排序

⑹ 用c语言编写归并排序代码，要求易懂，本人只是c语言的初学者，越简单越好。

//#include<iostream>
//
//using namespace std;
//
//void Guibing(int*arr,int low,int high)
//{
// int m_Begin1 = low;
// int m_End1 = (low+high)/2;
// int m_Begin2 = m_End1+1;
// int m_End2 = high;
//
// int* temp = new int[high-low+1];
// //申请一个这两组的空间
// //要看 只要有一组到结尾就要结束
// int k=0;
// for (;m_Begin1 <= m_End1 && m_Begin2 <= m_End2;k++)
// {
// // 然后找小的往里存
// if (arr[m_Begin1] < arr[m_Begin2])
// {
// temp[k] = arr[m_Begin1];
// m_Begin1++;
// }
// else
// {
// temp[k] = arr[m_Begin2];
// m_Begin2++;
// }
// }
//
// //如果第一组没到结尾 顺序存
// while(m_Begin1 <= m_End1)
// {
// temp[k] = arr[m_Begin1];
// k++;
// m_Begin1++;
// }
// //如果第二组没到结尾 顺序存
// while(m_Begin2 <= m_End2)
// {
// temp[k] = arr[m_Begin2];
// k++;
// m_Begin2++;
// }
// //把已经排好序的 temp 放回到原来对应的位置
// for (k = 0;k<high-low+1;k++)
// {
// arr[low+k] = temp[k];
// }
// delete[] temp;
//}
//
//void Digui(int*arr,int low,int high)
//{
// if (low < high)
// {
// int mid = (low+high)/2;
// Digui(arr,low,mid);
// Digui(arr,mid+1,high);
// Guibing(arr,low,high);
// }
//}
//
//int main()
//{
// int arr[10] = {9,11,5,3,17,13,1,17,25,8};
//
// Digui(arr,0,9);
//
// for (int i =0 ;i<10;i++)
// {
// cout << arr[i] << " ";
// }
//
// system("pause");
// return 0;
//}

⑺ C语言关于归并排序的问题，高分等待

1. 这个方法是把两组已经排好序的元素合并成一组新的排好序的元素。首先要把原本的元素不断分成两堆，直到每一堆只有0到1个元素。然后将这些小堆的元素两两按照顺序合并，然后再把这些新的堆继续两两合并，直至合并完。
2. 这个算法的比较次数不是最少的，但是最稳定的，并不比快速排序要少。
3. 冒泡算是最慢的方法之一。

⑻ 急求归并排序算法:将有序数组A[0, … , n]和B[0 , … , m]合并(C语言)

int guibing(int *a,int *b,int n,int m,int *s)
{
int i=0,j=0;

while(i<n&&j<m)
{
if(a[i]<b[j])
{
s[i+j]=a[i];
i++;
}
else
{
s[i+j]=b[j];
j++;
}
}
while(i<n)
{
s[i+j]=a[i];
i++;
}
while(j<m)
{
s[i+j]=b[j];
j++;
}

return 1;
}

⑼ 给定一个数列，如何用归并排序算法把它排成升序,用c语言实现。

void MergeSort(int x[],int n) { //非递归归并排序
//元素数组为x，其长度为n
int i,j,k1,k2,l;
int *a;
for(i=1;i<=n-1;i=i*2)//i为插入排序的子段长度
{
for(j=1;j<=n-1;j=j+2*i)//j为进行插入排序的子段起始位置
{
a=(int *)malloc(2*i*sizeof(int));
l=0;k1=j;k2=j+i;
while((l<2*i)&&(k2<=n-1)&&(k2<j+2*i)&&(k1<j+i))
{//子段中，比较，移至辅助内存
if(x[k1]<x[k2])
{
a[l++]=x[k1];k1++;
}
else
{
a[l++]=x[k2];k2++;
}
}
if((k2>n-1)||(k2>=j+2*i))
{//子段的后一段超出数组范围
for(;k1<j+i;k1++)
a[l++]=x[k1];
}
else//就只有第一段就超数组了
{
if(k1>=j+i)
{
for(;(k2<j+2*i)&&(k2<=n-1);k2++)
a[l++]=x[k2];
}
}
for(k1=0;k1<l;k1++)//最后移位
{
x[j+k1]=a[k1];
}free(a);
}
}
}

非递归的归并排序，我以前写的。
中间malloc与free的话，是为了方便管理不定大小的空间，这里需要malloc.h的头文件

⑽ 输入一组整数对该序列进行简单选择和归并排序（数据结构用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[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
;
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)
;
}
}