c语言的归并排序算法
㈠ c语言归并排序代码
voidmergeSort(inta[],intleft,intright)
{
inti;
//保证至少有两个元素
if(left<right)
{
i=(left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
merge(a,left,right);
}
}
voidmerge(inta[],intleft,intright)
{
intbegin1=left;
intmid=(left+right)/2;
intbegin2=mid+1;
intk=0;
intnewArrayLen=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:目标数组起始位置
*
*/
voidArray(intsource[],intdest[],intlen,intfirst)
{
inti;
intj=first;
for(i=0;i<len;i++)
{
dest[j]=source[i];
j++;
}
}
voidmergeSortTest()
{
inta[]={5,18,151,138,160,63,174,169,79,200};
intlen=sizeof(a)/sizeof(int);
showArray(a,len);
mergeSort(a,0,len-1);
showArray(a,len);
}
㈡ 给定一个数列，如何用归并排序算法把它排成升序,用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语言归并排序
/* 二路归并排序算法的源程序*/
#include<stdio.h>
#define MAXNUM 100
#define TRUE 1
#define FALSE 0
typedef int KeyType;
typedef int DataType;
typedef struct
{ KeyType key; /* 排序码字段 */
/*DataType info; 记录的其它字段 */ } RecordNode;
typedef struct
{ int n; /* n为文件中的记录个数，n<MAXNUM */
RecordNode record[MAXNUM]; } SortObject;
/* r[low]到r[m]和r[m+1]到r[right]是两个有序段 */
void merge(RecordNode r[], RecordNode r1[], int low, int m, int high)
{ int i=low, j=m+1, k=low;
while ( i<=m && j<=high ) /* 反复复制两个段的第一个记录中较小的 */
if (r[i].key<=r[j].key) r1[k++]=r[i++];
else r1[k++]=r[j++];
while (i<=m) r1[k++]=r[i++]; /* 复制第一个段的剩余记录 */
while (j<=high) r1[k++]=r[j++];/* 复制第二个段的剩余记录 */
}
/* 对 r 做一趟归并，结果放到 r1 中 */
void mergePass(RecordNode r[], RecordNode r1[], int n, int length)
{ int i=0, j; /* length为本趟归并的有序子段的长度 */
while (i+2*length-1<n)
{ merge(r,r1,i,i+length-1,i+2*length-1); /*归并长length的两个子段*/
i+=2*length; }
if(i+length-1<n-1) /* 剩下两段，后一段长度小于length */
merge(r, r1, i, i+length-1, n-1);
else for(j=i; j<n; j++) r1[j]=r[j]; /* 将剩下的一段复制到数组r1 */
}
void mergeSort(SortObject * pvector)
{ RecordNode record[MAXNUM];
int length = 1;
while (length<pvector->n) /*一趟归并，结果存放在数组record中*/
{ mergePass(pvector->record, record, pvector->n, length);
length*=2;
/* 一趟归并，结果存回 */
mergePass(record, pvector->record, pvector->n, length);
length *= 2; }
}
SortObject vector = {8, 49,38,65,97,76,13,27,49};
main()
{ int i;
mergeSort(&vector);
for(i = 0; i < 8; i++) printf("%d ", vector.record[i]);
getchar();
}
㈣ c语言的归并排序的完整程序
这个不难:
#include<stdio.h>
// 一个递归函数
void mergesort(int *num,int start,int end);
// 这个函数用来将两个排好序的数组进行合并
void merge(int *num,int start,int middle,int end);
int main()
{
// 测试数组
int num[10]= {12,54,23,67,86,45,97,32,14,65};
int i;
// 排序之前
printf("Before sorting:\n");
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
// 进行合并排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之后
for (i=0; i<10; i++)
{
printf("%3d",num[i]);
}
printf("\n");
return 0;
}
//这个函数用来将问题细分
void mergesort(int *num,int start,int end)
{
int middle;
if(start<end)
{
middle=(start+end)/2;
// 归并的基本思想
// 排左边
mergesort(num,start,middle);
// 排右边
mergesort(num,middle+1,end);
// 合并
merge(num,start,middle,end);
}
}
//这个函数用于将两个已排好序的子序列合并
void merge(int *num,int start,int middle,int end)
{
int n1=middle-start+1;
int n2=end-middle;
// 动态分配内存，声明两个数组容纳左右两边的数组
int *L=new int[n1+1];
int *R=new int[n2+1];
int i,j=0,k;
//将新建的两个数组赋值
for (i=0; i<n1; i++)
{
*(L+i)=*(num+start+i);
}
// 哨兵元素
*(L+n1)=1000000;
for (i=0; i<n2; i++)
{
*(R+i)=*(num+middle+i+1);
}
*(R+n2)=1000000;
i=0;
// 进行合并
for (k=start; k<=end; k++)
{
if(L[i]<=R[j])
{
num[k]=L[i];
i++;
}
else
{
num[k]=R[j];
j++;
}
}
delete [] L;
delete [] R;
}
㈤ 高分送！！如何用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要改成你需要用的数~
㈥ 归并排序算法
两种归并排序算法的实现：二路归并排序和基本归并排序（虚拟消除递归的二路归并排序）
#define ARRAY_SIZE 1024
int B[1024]; //使用一个全局变量，避免归并排序中每次都重新申请和释放空间造成的开销
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[i]<A[j])
{
B[k++] = A[i];
i++;
}
else
{
B[k++] = A[j];
j++;
}
}
while(i<=m)
{
B[k++] = A[i++];
}
while(j<=h)
{
B[k++] = A[j++];
}
for(i=l; i<=h; i++)
{
A[i] = B[i-l];
}
}
//二路归并排序的实现
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[l]>a[h])
{
std::swap(a[l], a[h]);
}
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[], T b[], 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[j]<a[k])
{
b[m++] = a[j];
j++;
}
else
{
b[m++] = a[k];
k++;
}
}
while((j<jE)&&(j<n))
{
b[m++] = a[j++];
}
while((k<kE)&&(k<n))
{
b[m++] = a[k++];
}
}
}
//基本归并排序，虚拟消除递归
template <typename T>
void MergeSort2(T a[], int n)
{
int s = 1; //merge 的步长
T* b = new T[n];
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[ARRAY_SIZE];
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个长度为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)
;
}
}
㈧ c语言归并排序
int merge(int *a, int begin, int end){
int n = end - begin +1;
int mid = (begin+end)/2;
int i = begin;
int j = mid+1;
int k = begin;
while(i<=mid&&j<=end){
if(a[i]<=a[j]){
c[k]=a[i];
k++;
i++;
}
else{
c[k]=a[j];
k++;
j++;
}
}
for(;i<=mid;i++,k++){
c[k]=a[i];
}
for(;j<=end;j++,k++){
c[k]=a[j];
}
for(i=begin;i<=end;i++){
a[i]=c[i];
}
return 1;
}
㈨ C语言排序算法一共多少种
选择排序
#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 Merger<T>::sub_Merger(T * array, size_t n)
{
if(n == 1) //~ 递归终止
return ;
else if(n == 2) //~ 递归终止
{
if( array[0] > array[1] )
{
T tmp = array[0];
array[0] = array[1];
array[1] = tmp;
}
}
else
{
/* 将数组均分为两部分，分别排好，然后归并*/
size_t m = n / 2;
//~ 分别排序
sub_Merger(array, m + 1);
sub_Merger(array + m + 1, n - m - 1);
//~ 归并
size_t i = 0, j = m + 1, k = 0;
memcpy(extra, array, (m + 1)* sizeof(T));
while( i <= m && j < n)
{
array[k++] = extra[i] < array[j] ? extra[i++]:array[j++];
}
while(i <= m)
{
array[k++] = extra[i++];
}
}
}