c合并排序算法

‘壹’ 谁能给个简单的C语言归并排序算法的例子啊谢谢

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<time.h>
#define M 11
typedef int KeyType;
typedef int ElemType;
struct rec
{
KeyType key;ElemType data;
};
typedef rec sqlist[M];
void output( sqlist r, int n )
{
for ( int i = 0; i < n; i++ )
{
cout << setw( 4 ) << r[i].key;
}
cout << endl;
}
void xuanze( sqlist b, int m, int n )
{
int i, j, k;
for ( i = m; i < n - 1; i++ )
{
k = i;
for ( j = i; j < n; j++ )
{
if ( b[k].key > b[j].key )
{
k = j;
}
}
if ( k != i )
{
rec temp = b[k];
b[k] = b[i];b[i] = temp;
}
}
}
void merge( sqlist r, int l, int m, int h, sqlist r2 )
{
xuanze( r, l, m );
xuanze( r, m, h );
output( r, M );
int i, j, k;
k = i = l;
for ( j = m; i < m && j < h; k++ )
{
if ( r[i].key <= r[j].key )
{
r2[k] = r[i];i++;
}
else
{
r2[k] = r[j];j++;
}
output( r2, M );
}
while ( j < h )
{
r2[k] = r[j];j++;k++;
}
while ( i <= m )
{
r2[k] = r[i];i++;k++;
}
output( r2, M );
}
void main()
{
cout << "guibingfa2.cpp运行结果:\n";
sqlist a, b;int i, j = 0, k = M / 2, n = M;
srand( time( 0 ) );
for ( i = 0; i < M; i++ )
{
a[i].key = rand() % 80;b[i].key = 0;
}
cout << "排序前数组:\n";
output( a, M );
cout << "数组排序的过程演示:\n";
merge( a, j, k, n, b );
cout << "排序后数组:\n";
output( b, M );cin.get();
}

‘贰’ c语言的归并排序

、归并简单点说就是2分法 一直除以2 然后把从0到N/2的下标 ， 和 N/2+1 到N的地址传送到合并函数里面，递归调用

‘叁’ 用C语言编写算法实现将两个递增顺序表合并为一个递增顺序表

1.最容易的办法就是把两个表保存在一个新的表里，然后冒泡排序（就是这么暴力。）
2.不过这个问题用指针实现最方便了。
两个指针分别指着两个递增表：比较指针所指的值大小，将小的那个保存在新的表里，然后将小的那个指针往前走一步。再比较，再保存，再走....直到其中一个表走完，把另一个表剩下的数接在后面。
这样做的好处是原有的两个表的内容不会被修改。因为结果是保存在新的表里的，但是消耗内存。
3.插入排序，同样使用指针比较，把一个表里的数据插到另一个表里。这样省内存，但是被插入的这个表原有的数据就没咯。

‘肆’ （C语言数据结构） 设计两个有序顺序表的合并排序算法。

#include
#include
typedef
struct
node//定义结构体
{
int
score;
struct
node
*next;
}node;
node
*create(int
n)//创建链表
{
node
*head,*tail,*p;
head=tail=null;
int
i;
for(i=1;i<=n;i++)
{
p=(node
*)malloc(sizeof(node));
p->next=null;
printf("please
input
%d
score:",i);
scanf("%d",&p->score);
if(head==null)
head=tail=p;
else
{
tail->next=p;
tail=p;
}
}
return
head;
}
node
*range(node
*head)//排序
{
node
*p,*q;
int
score,i,n=0;
p=head;
while(p)
{
n++;
p=p->next;
}
for
(i=0;i
next!=null)//内循环
{
q=p->next;
if
(p->score>q->score)//值交换
{
score=p->score;
p->score=q->score;
q->score=score;
}
p=q;
}
}
return
head;
}
node
*connect(node
*head1,node
*head2)//合并
{
node
*p;
p=head1;
while(p->next!=null)
p=p->next;
p->next=head2;
return
head1;
}
void
output(node
*head)//输出
{
node
*p;
p=head;
while(p)
{
printf("%d
",p->score);
p=p->next;
}
printf("\n");
}
int
main()
{
node
*head,*hea1,*head2;
int
n1,n2;
printf("please
input
a
n1:");//第一个链表的成绩个数
scanf("%d",&n1);
hea1=create(n1);
printf("第一个链表的成绩:");
output(hea1);
printf("please
input
a
n2:");//第二个链表的成绩个数
scanf("%d",&n2);
head2=create(n2);
printf("第二个链表的成绩:");
output(head2);
head=connect(hea1,head2);
head=range(head);
printf("合并后，并排好序:");
output(head);
return
0;
}

‘伍’ 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语言归并排序代码

void mergeSort(int a[],int left,int right)
{
int i;
// 保证至少有两个元素
if(left < right)
{
i = (left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,left,right);
}
}
void merge(int a[],int left,int right)
{
int begin1 = left;
int mid = (left+right)/2 ;
int begin2 = mid+1;
int k=0;
int newArrayLen = right-left+1;
int *b = (int*)malloc(newArrayLen*sizeof(int));
while(begin1<=mid && begin2<=right)
{
if(a[begin1]<=a[begin2])
b[k++] = a[begin1++];
else
b[k++] = a[begin2++];
}
while(begin1<=mid)
b[k++] = a[begin1++];
while(begin2<=right)
b[k++] = a[begin2++];
Array(b,a,newArrayLen,left);
free(b);
}
/**
* 复制数组
* source:源数组
* dest:目标数组
* len:源数组长度
* first:目标数组起始位置
*
*/
void Array(int source[], int dest[],int len,int first)
{
int i;
int j=first;
for(i=0;i<len;i++)
{
dest[j] = source[i];
j++;
}
}
void mergeSortTest()
{
int a[] = {5, 18, 151, 138, 160, 63, 174, 169, 79, 200};
int len = sizeof(a)/sizeof(int);
showArray(a,len);
mergeSort(a,0,len-1);
showArray(a,len);
}

‘柒’ 高分送！！如何用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语言归并排序简单问题

当调用Merge_SortDC(1,8);时，
Merge_SortDC(1,4); 与Merge_SortDC(4+1,8); 都执行成功返回以后
两边的数组都是有序的了，这时候，执行Merge(low,mid,high)，也就是Merge(1,4,8）。
至于Merge_SortDC(1,4); 与Merge_SortDC(4+1,8)各自的执行顺序，也跟Merge_SortDC(1,8);是类似的，可以类推。
递归就是先递推调用到最后，然后再一层层返回来。

‘玖’ 求C或C++编程：有两组无序数字 arr1， arr2，将它们合并为一个从小到大排列的数字。

算法1。先排序，再合并；
算法2。先合并为一组，再排序。

‘拾’ 十大经典排序算法 C 语言实现[上]冒泡选择插入希尔归并

期中已到，期末将至。《算法设计与分析》的“预习”阶段借此开始~。在众多的算法思想中，如果你没有扎实的数据结构的功底，不知道栈与队列，哈希表与二叉树，不妨可以从排序算法开始练手。纵观各类排序算法，常见的、经典的排序算法将由此篇引出。

排序算法的输出必须遵守的下列两个原则：

十大经典的排序算法及其时间复杂度和稳定性如上表所示。判断一个排序算法是否稳定是看在相等的两个数据排序算法执行完成后是否会前后关系颠倒，如若颠倒，则称该排序算法为不稳定，例如选择排序和快速排序。

接下来十个经典排序算法的详细探讨缺少不了交换两个整数值的掌握，这里回顾一下其中三种方交换法：用临时变量交换两个整数的值(SwapTwo_1)、不用第三方变量交换两个整数的值(SwapTwo_2)、使用位运算交换两个整数的值(SwapTwo_3)。其中用临时变量交换两个整数的值效率最高，后俩者只适用于内置整型数据类型的交换，并不高效。

先不说公司面试笔试，大学实验室的纳新题里最常有的就是冒泡排序。冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。由于它的简洁，冒泡排序通常被用来对于程序设计入门的学生介绍算法的概念。

[图片上传失败...(image-93185f-1513765803581)]]( http://upload-images.jianshu.io/upload_images/2558748-990f8de3fbdbb50d.gif?imageMogr2/auto-orient/strip )

上图可见，冒泡排序算法的运作如下：

通俗来讲，整个冒泡排序就是通过两次循环，外层循环将此轮最大(小)值固定到此轮尾部，内层循环“冒泡”比较相邻的两个元素并决定是否交换位置。

从上图也可理解冒泡排序如何将每一轮最大（小）值固定到此轮尾部：尾部总为有序状态，前面无序状态区根据大小规则冒泡向后方传递最值。

选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

上图左下角和右上角可以分别看做排序序列起始位置(已排序区)和排序序列末尾(未排序区)，左下角一直稳定更新，但选择排序不稳定，即排序后曾经相同的两个元素的前后位置关系可能会发生颠倒。

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place
排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：

如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找插入排序。这里先不做涉及。

希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布。希尔排序也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。当步长为1时，算法变为插入排序，这就保证了数据一定会被排序。

已知的最好步长序列是由 Sedgewick 提出的(1, 5, 19, 41, 109,...)，这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长序列的希尔排序比插入排序要快，甚至在小数组中比快速排序和堆排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。

归并排序是创建在归并操作上的一种有效的排序算法，效率为 O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。

归并操作（merge），也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

归并排序用迭代法和递归法都可以实现，迭代法的算法步骤为：

递归法的算法步骤为：

这篇文章“十大经典排序算法及其 C 语言实现【上】”引出了十大经典算法的前五个并用 C 语言实践：冒泡排序、选择排序、插入排序、希尔排序和归并排序，并作出了充足的图文解释。即将推出的“十大经典排序算法及其 C 语言实现【下】”将对剩下五个经典算法快速排序、堆排序、计数排序、桶排序、基数排序作出完善，尽请期待~。