锐客网

  1. 首页 > 睿知 > it技术 > >

c语言中归并排序的函数 归并排序c算法实现

IT技术归并

c语言归并排序直接上源码c语言中归并排序的函数，仅供参考c语言中归并排序的函数：
#includestdio.h
// 一个递归函数
void mergesort(int *num,int start,int end);
// 这个函数用来将两个排好序c语言中归并排序的函数的数组进行合并
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; i10; i)
{
printf("=",num[i]);
}
printf("\n");
// 进行合并排序
mergesort(num,0,9);
printf("After sorting:\n");
// 排序之后
for (i=0; i10; i)
{
printf("=",num[i]);
}
printf("\n");
return 0;
}
//这个函数用来将问题细分
void mergesort(int *num,int start,int end)
{
int middle;
if(startend)
{
middle=(start end)/2;
// 归并c语言中归并排序的函数的基本思想
// 排左边
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;
// 动态分配内存c语言中归并排序的函数，声明两个数组容纳左右两边的数组
int *L=new int[n1 1];
int *R=new int[n2 1];
int i,j=0,k;
//将新建的两个数组赋值
for (i=0; in1; i)
{
*(L i)=*(num start i);
}
// 哨兵元素
*(L n1)=1000000;
for (i=0; in2; 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语言归并排序简单问题当调用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语言 归并排序之前写过一个模版类，这里是部分代码：
void MergerT::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, m1);
sub_Merger(arraym1, n - m - 1);
//~ 归并
size_t i = 0, j = m1, k = 0;
memcpy(extra, array, (m1)* sizeof(T));
while( i = mjn)
{
array[k] = extra[i]array[j] ? extra[i]:array[j];
}
while(i = m)
{
array[k] = extra[i];
}
}
}
C语言归并排序代码void mergeSort(int a[],int left,int right)
{
int i;
// 保证至少有两个元素
if(leftright)
{
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=midbegin2=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];
copyArray(b,a,newArrayLen,left);
free(b);
}
/**
* 复制数组
* source:源数组
* dest:目标数组
* len:源数组长度
* first:目标数组起始位置
*
*/
void copyArray(int source[], int dest[],int len,int first)
{
int i;
int j=first;
for(i=0;ilen;i)
{
dest[j] = source[i];
j;
【c语言中归并排序的函数 归并排序c算法实现】}
}
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语言的归并排序、归并简单点说就是2分法 一直除以2 然后把从0到N/2c语言中归并排序的函数的下标 c语言中归并排序的函数，和 N/2 1 到N的地址传送到合并函数里面c语言中归并排序的函数 ， 递归调用
c语言中归并排序的函数的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于归并排序c算法实现、c语言中归并排序的函数的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：Oracle截取字符串的函数，oracle 截取字符串中指定位置

    下一篇：gnnswvs电脑直播，pc直播