递归合并排序c语言

❶ c语言归并排序 的合并是靠什么实现的。

是靠优化的插入排序实现的。按递归的思路将要排序的部分，拆分成不可拆分的小段再两两合并。
之所以说优化后的插入排序是因为合并的两端都是有序的，所以只需要每次比较最前方的一个元素，当一列完全插入后，在后面追加另一列。

你给出的例子没有拆分到底，所以先拆分

比如：49, 38,65, 97,76, 13, 27
先拆分
（49, 38,65, 97）,（76, 13, 27）
（49, 38）,（65, 97）,（76, 13）,（ 27）你的例子
(49),(38),(65),(97),(76),(13),(27)
(38,49),(65,97),(13,76),(27)
（38,49,65,97）,(13,27,76)
(13,27,49,65,76,97)

❷ 归并排序C语言版

#include <stdio.h>
void merge(int r[], int s[], int x1, int x2, int x3) /*实现一次归并排序函数*/
{
int i, j, k;
i = x1; /*第一部分的开始位置*/
j = x2 + 1; /*第二部分的开始位置*/
k = x1;
while ((i <= x2) && (j <= x3))
/*当i和j都在两个要合并的部分中*/
if (r[i] <= r[j])
/*筛选两部分中较小的元素放到数组s中*/
{
s[k] = r[i];
i++;
k++;
}
else
{
s[k] = r[j];
j++;
k++;
}
while (i <= x2)
/*将x1~x2范围内的未比较的数顺次加到数组r中*/
s[k++] = r[i++];
while (j <= x3)
/*将x2+1~x3范围内的未比较的数顺次加到数组r中*/
s[k++] = r[j++];
}
void merge_sort(int r[], int s[], int m, int n)
{
int p;
int t[20];
if (m == n)
s[m] = r[m];
else
{
p = (m + n) / 2;
merge_sort(r, t, m, p);
/*递归调用merge_sort函数将r[m]~r[p]归并成有序的t[m]~t[p]*/
merge_sort(r, t, p + 1, n); /*递归调用merge_sort函数将r[p
+1]~r[n]归并成有序的t[p+1]~t[n]*/
merge(t, s, m, p, n); /*调用函数将前两部分归并到s[m]~s[n]*/
}
}
main()
{
int a[11];
int i;
printf("please input 10 numbers:\n");
for (i = 1; i <= 10; i++)
scanf("%d", &a[i]);
/*从键盘中输入10个数*/
merge_sort(a, a, 1, 10); /*调用merge_sort函数进行归并排序*/
printf("the sorted numbers:\n");
for (i = 1; i <= 10; i++)
printf("%5d", a[i]);
/*将排序后的结构输出*/
}


❸ C语言利用递归实现插入排序，选择排序，快速排序，归并排序算法。 要求有注释 ！ 谢谢各位大神！

//InsertionSort
void insertionSort(int a[], int size) {
int i, j, key;

for (i = 0; i < size; i++) {
key = a[i];
j = i-1;
while (j >= 0 && key < a[j]) { //把元素插入到之前的有序元组中
a[j+1] = a[j];
j--;
}
a[j+1] = key;
}
}

//MergeSort
void merge(int a[], int p, int q, int r) { //合并两个子元组
int i, j, k, n1, n2;
int *array1, *array2;
n1 = q - p + 1,
n2 = r - q;

array1 = (int *)calloc(n1+1, sizeof(int));
array2 = (int *)calloc(n2+1, sizeof(int));
if (array1 == NULL || array2 == NULL) {
printf("Error: calloc failed in concat\n");
exit(EXIT_FAILURE);
}
for(i = 0; i < n1; i++)
array1[i] = a[p + i];
for(i = 0; i < n2; i++)
array2[i] = a[q + 1 + i];
array1[n1] = MAXNUMBER;
array2[n2] = MAXNUMBER;
i = 0, j = 0;
for(k = p; k <= r; k++)
if(array1[i] <= array2[j])
a[k] = array1[i++];
else
a[k] = array2[j++];
free(array1);
free(array2);
}

void mergeSort(int a[], int p, int r) {//归并的递归调用
int q;
if (p < r) {
q = (p+r)/2;
mergeSort(a,p,q);
mergeSort(a,q+1,r);
merge(a,p,q,r);
}
}

//QuickSort
int partition(int a[], int p, int r) {//快排的分组函数
int i, j, x, temp;
x = a[r];
i = p - 1;

for (j = p; j < r; j++)
if (x > a[j]) {
temp = a[++i];
a[i] = a[j];
a[j] = temp;
}
temp = a[++i];
a[i] = a[r];
a[r] = temp;

return i;
}

void quickSort(int a[], int p, int r) { //快排
int q;
if (p < r) {
q = partition(a, p, r);
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}

//随即版的quickSort
int randomPartition(int a[], int p, int r){

int i, temp;
i = rand();
while( i < p || i > r)
i = rand();
temp = a[i];
a[i] = a[r];
a[r] = temp;
return partition(a,p,r);
}

void randomQuickSort(int a[], int p, int r){
int q;
if(p < r){
q = randomPartition(a,p,r);
randomQuickSort(a,p,q-1);
randomQuickSort(a,q+1,r);
}
}
//BubbleSort();//冒泡排序
void bubbleSort(int a[], int size) {
int i, j, temp;

for (i = size -1; i >= 0; i--)
for (j = 0; j < i; j++)
if (a[j] < a[j+1]) {
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}

❹ 怎样使用递归实现归并排序

第一步：先写一个合并两个排序好数组的方法，方法名就叫做merge，如下：

[java]view plain

• publicstaticvoidmerge(int[]a,intaSize,int[]b,intbSize,int[]c){

• inttempA=0,tempB=0,tempC=0;

• while(tempA<aSize&&tempB<bSize){

• if(a[tempA]>b[tempB]){

• c[tempC++]=b[tempB++];

• }else{

• c[tempC++]=a[tempA++];

• }

• }

• while(tempA<aSize){

• c[tempC++]=a[tempA++];

• }

• while(tempB<bSize){

• c[tempC++]=b[tempB++];

• }


这个方法非常简单，一共有着5个参数（也可以简化为3个参数）,其中a，b数组是待合并数组，aSize，bSize是数组长度（这两个参数可以去掉）,c为目标数组。主要的流程就是不断的比较a，b数组的大小，然后将较小数据复制进c中。这里面关键的一点就是使用了3个临时变量，用于标志每个数组对应的位置，这样子可以极大简化我们的代码设计。下面是对应的图示过程：



有了这个方法之后，我们就可以开始写归并排序的主体方法了。写主体方法也很简单，思想就是分治算法。

• 第一步：就是将大数组分成两个小的数组

• 第二部：排序这两个数组，使用的是递归排序方法，也就是自己调用自己

• 第三部：调用上面的合并方法合并起来即可

代码非常简单，直接贴上

[java]view plain

• publicclassTowersApp{

• publicstaticvoidmain(String[]args){

• int[]a={1,1,0,1,1,5,3};

• mergeSort(a);

• for(inti=0;i<a.length;i++){

• System.out.print(a[i]);

• }

• }

• publicstaticvoidmergeSort(int[]source){

• //递归出口

• if(source.length==1)return;

• //将大数组分成两个小数组

• intmiddle=source.length/2;

• int[]left=newint[middle];

• for(inti=0;i<middle;i++){

• left[i]=source[i];

• }

• int[]right=newint[source.length-middle];

• for(inti=middle;i<source.length;i++){

• right[i-middle]=source[i];

• }

• //对数据进行排序（这里使用递归排序）

• mergeSort(left);

• mergeSort(right);

• //合并排序好的数据

• merge(left,left.length,right,right.length,source);

• }

• publicstaticvoidmerge(int[]a,intaSize,int[]b,intbSize,int[]c){

• inttempA=0,tempB=0,tempC=0;

• while(tempA<aSize&&tempB<bSize){

• if(a[tempA]>b[tempB]){

• c[tempC++]=b[tempB++];

• }else{

• c[tempC++]=a[tempA++];

• }

• }

• while(tempA<aSize){

• c[tempC++]=a[tempA++];

• }

• while(tempB<bSize){

• c[tempC++]=b[tempB++];

• }

• }

• }






总结：要记住归并排序算法的核心核心思想：分而治之。

❺ 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<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语言编写归并排序代码，要求易懂，本人只是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语言，二路归并排序，递归调用到底是怎么调用的求详解！

程序代码都是顺序执行的，当然是把一路调用完再做第二路调用，最后把排好序的2路进行合并；

在排序每一路的时候也是使用归并的方式，把一路分成2路，层层深入。

理解的话，你可以这样：

比如8个数，你从上到下竖着排成一列，然后中间一条横线分割。

横线上面的部分再从中间分割成2部分，2部分放在第二列；

依次往后分割。得到形如这样的图：

然后按照红色箭头先按A反推一层，再按B向下一层，这样就会合并一次产生排好序的前一层。如此反复，这就是递归实际的执行流程。

❾ 用C语言,随机输入十个整数,用合并排序法对这些整数进行排序~

用递归函数实现：

#include<stdlib.h>
#include<stdio.h>
/* 将a的两个有序子序列（a[l]~a[m]和a[m+1]~a[r]）合并为一个有序序列 */
void merge(int a[], int l, int m, int r)
{
int i,j,k;
int *t=(int*)malloc((r-l+1)*sizeof(int)); /* 建立临时数组，保存合并结果 */
i=l; /* i为前一序子序列的待合并元素位置 */
j=m+1; /* j为后一序子序列的待合并元素位置 */
k=0; /* k为即将加入到合并结果序列的元素位置 */
while(i<=m && j<=r) /* 条件：两个序子序列均未合并完 */
{
/* 将两个序子序列的待合并元素中较小的一个元素合并到t */
if(a[i]<a[j])
t[k]=a[i++];
else
t[k]=a[j++];
k++;
}

/* 前一序子序列未合并完，将剩余部分传入t */
while(i<=m)
t[k++]=a[i++];

/* 后一序子序列未合并完，将剩余部分传入t */
while(j<=r)
t[k++]=a[j++];

/* 合并结果传回数组a的a[l] ~ a[r] */
for (i=0; i<k; i++)
a[l+i]=t[i];
free(t);
}

void sort(int a[], int l, int r)
{
if(l<r)
{
int m=(l+r)/2; /* 分解成两组：l ~ m 和 m+1 ~ r */
sort(a, l, m); /* 递归：对前半段排序 */
sort(a, m+1, r); /* 递归：对后半段排序 */
merge(a, l, m, r); /* 合并结果 */
}
}

void main()
{
int a[10];
int i;
for(i=0; i<10; i++)
scanf("%d",&a[i]);
sort(a,0,9);
for(i=0; i<10; i++)
printf("%d ",a[i]);
printf("\n");
}

❿ c语言递归排序怎么写、

哪有什么递归排序，递归只是一种函数调用方式，只是很多排序方法有用到递归，比如快速排序，搜索中的二分法，深搜，广搜。