首先是一道特别水的题
题目描述
将两个按升序排列的数列，仍按升序合并存放到另一个数组中，要求每个数都一次到位，不得在新数组中重新排序。
特别说明：两个初始数列中元素的个数均不超过20个。
输入
输入为两个升序数列：
第一行为两个数列的长度m和n，
第二行为第一个数列的m个元素的值，
第三行为第二个数列的n个元素的值。
输出
输出为排序好的数组，数组中各个元素之间用空格隔开，最后一个数字后面没有空格。
样例输入
5 4
1 3 5 7 9
2 4 6 8
样例输出
1 2 3 4 5 6 7 8 9
#include<stdio.h>
#include<stdlib.h>
int main(void) {
int m;
int n;
int *a;
int *b;
int *c;
int i;
int j;
int k;
scanf("%d %d",&m,&n);
a = (int *)calloc(sizeof(int),m);
b = (int *)calloc(sizeof(int),n);
c = (int *)calloc(sizeof(int),m + n);
for(i = 0;i < m;i++) {
scanf("%d",&a[i]);
}
for(i = 0;i < n;i++) {
scanf("%d",&b[i]);
}
for(i = 0,j = 0,k = 0;i < m && j < n;k++) {
if(a[i] > b[j]) {
c[k] = b[j++];
} else if(a[i] < b[j]) {
c[k] = a[i++];
} else {
c[k++] = b[j++];
c[k] = a[i++];
}
}
while(i == m && j != n) {
c[k++] = b[j++];
}
while(i != m && j == n){
c[k++] = a[i++];
}
for(i = 0;i < m+n;i++) {
printf(i == 0 ? "%d" : " %d",c[i]);
}
puts("");
free(a);
free(b);
free(c);
return 0;
}归并排序也称合并排序，其算法思想是将待排序序列分为两部分，依次对分得的两个部分再次使用归并排序，之后再对其进行合并。仅从算法思想上了解归并排序会觉得很抽象，接下来就以对序列A[0], A[l]…, A[n-1]进行升序排列来进行讲解，在此采用自顶向下的实现方法，操作步骤如下。
(1)将所要进行的排序序列分为左右两个部分，如果要进行排序的序列的起始元素下标为first，最后一个元素的下标为last，那么左右两部分之间的临界点下标mid=(first+last)/2，这两部分分别是A[first … mid]和A[mid+1 … last]。
(2)将上面所分得的两部分序列继续按照步骤(1)继续进行划分，直到划分的区间长度为1。
(3)将划分结束后的序列进行归并排序，排序方法为对所分的n个子序列进行两两合并，得到n/2或n/2+l个含有两个元素的子序列，再对得到的子序列进行合并，直至得到一个长度为n的有序序列为止。
#include <stdio.h>
#include <stdlib.h>
#define N 7
void merge(int arr[], int low, int mid, int high){
int i, k;
int *tmp = (int *)malloc((high-low+1)*sizeof(int));
//申请空间，使其大小为两个
int left_low = low;
int left_high = mid;
int right_low = mid + 1;
int right_high = high;
for(k = 0; left_low <= left_high && right_low <= right_high; k++){ // 比较两个指针所指向的元素
if(arr[left_low] <= arr[right_low]){
tmp[k] = arr[left_low++];
} else{
tmp[k] = arr[right_low++];
}
}
if(left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
for(i = left_low;i <= left_high;i++)
tmp[k++] = arr[i];
}
if(right_low <= right_high){
//若第二个序列有剩余，直接复制出来粘到合并序列尾
//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
for(i=right_low; i<=right_high; i++)
tmp[k++] = arr[i];
}
for(i=0; i<high-low+1; i++)
arr[low+i] = tmp[i];
free(tmp);
return;
}
void merge_sort(int arr[], unsigned int first, unsigned int last){
int mid = 0;
if(first < last){
mid = (first+last)/2; /* 注意防止溢出 */
/*mid = first/2 + last/2;*/
//mid = (first & last) + ((first ^ last) >> 1);
merge_sort(arr, first, mid);
merge_sort(arr, mid+1,last);
merge(arr,first,mid,last);
}
return;
}
int main(){
int i;
int a[N] = {32,12,56,78,76,45,36};
printf ("排序前 \n");
for(i = 0;i < N;i++)
printf("%d\t",a[i]);
merge_sort(a,0,N-1); // 排序
printf ("\n 排序后 \n");
for(i = 0;i < N;i++)
printf("%d\t",a[i]); printf("\n");
return 0;
}