歸並排序演算法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)
;
}
}