【C语言】归并排序的递归和非递归实现

递归和非递归实现"/>

【C语言】归并排序的递归和非递归实现

一、递归

核心就是一个数组中有序子列排序的问题，这里用了merge函数实现，其中int*a是待排序数组，int*tmp是临时数组，l是左边子列的起始下标，r是右边子列的起始下标，rightend是右边结束的位置，然后就把两个子列都扫描一遍，小的就往tmp里面填写，最后到只有一个子列还有数据，就把剩下的数据全都放进tmp就行了；

然后用一个mort函数递归的开始调用merge函数。

#include<stdio.h>
#include<stdlib.h>void merge(int* a, int *tmp, int l, int r, int rightend);
void mort(int* a, int* tmp, int l, int rightend);
int * mort_sort(int* a);int main()
{int n, i;scanf("%d", &n);int* a = (int*)malloc(sizeof(int) * n+1);for ( i = 0; i < n; i++){scanf("%d", &a[i]);}a=mort_sort(a, n);for ( i = 0; i < n; i++){printf("%d\t", a[i]);}}int* mort_sort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);mort(a,  tmp, 0, n-1);return a;
}void mort(int* a, int* tmp, int l, int rightend)
{int center;if (l<rightend){center = (l + rightend) / 2;mort(a, tmp, l, center);mort(a, tmp, center + 1, rightend);merge(a, tmp, l, center + 1, rightend);}
}void merge(int* a, int *tmp, int l, int r, int rightend)
{int leftend = r - 1;int temp = l;int amount = rightend - l + 1;while (l<=leftend && r<=rightend){if (a[l]<=a[r]){tmp[temp++] = a[l++];}else{tmp[temp++] = a[r++];}}while (l<=leftend){tmp[temp++] = a[l++];}while (r<=rightend){tmp[temp++] = a[r++];}for ( ; amount!=0; amount--){a[rightend] = tmp[rightend];rightend--;}
}

二、非递归

其实和递归思路基本上一样，不过这里的merge函数最后没有吧tmp里面的数倒回a里面，因为非递归若是每次都倒一下，所需的时间会比递归大很多

#include<stdio.h>
#include<stdlib.h>void merge(int* a, int* tmp, int left, int right, int rightend);
void premerge(int* a, int* tmp, int lenth, int n);
void merge_sort(int* a);int main()
{int* a=(int*)malloc(sizeof(int));merge_sort(a);
}void merge_sort(int* a)
{int i = 0;a = (int*)malloc(sizeof(int) * 30);printf("please enter the number youw want , 999 means end\n");while (i!=29){scanf("%d", &a[i]);if (a[i]==999){break;}i++;}int amount = i;int* tmp = (int*)malloc(sizeof(int) * (i + 1));int lenth = 1;while (lenth<amount){premerge(a, tmp, lenth, amount);lenth *= 2;premerge(tmp, a, lenth, amount);lenth *= 2;}for (int x = 0; x < amount; x++){printf("%d\t", a[x]);}
}void premerge(int* a, int* tmp, int lenth, int n)
{int i;for ( i = 0; i < n-2*lenth; i+=2*lenth){merge(a, tmp, i, i + lenth, i + 2 * lenth - 1);}if (i+lenth<n){merge(a, tmp, i, i + lenth, n-1);}else{for ( ; i <= n-1; i++){tmp[i] = a[i];}}return 0;
}void merge(int* a, int* tmp, int left, int right, int rightend)
{int leftend = right - 1;int numbers = rightend - left+1;int tmpbegin = left;while (left<=leftend && right<=rightend){if (a[left]<=a[right]){tmp[tmpbegin++] = a[left++];}else{tmp[tmpbegin++] = a[right++];}}while (left <= leftend){tmp[tmpbegin++] = a[left++];}while (right <= rightend){tmp[tmpbegin++] = a[right++];}return 0;
}