归并排序的介绍
归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
问题描述
给出两个有序数组（数组大小不一定不相等），要求合并成一个有序数组并输出
int main() { int arr1[] = { 1,3,5,7,9,11,13,15,17 }; int arr2[] = { 2,4,6,8,10,12,14 }; return 0; }
算法思想
比较各个子序列的第一个记录的键值， 最小的一个就是排序后序列的第一个记录。
取出 这个记录，继续比较各子序列现有的第一个记录 的键值，便可找出排序后的第二个记录。
如此继 续下去，最终可以得到排序结果。
思路分析
首先求出两个有序序列的大小并分别存入两个整型变量
int main() { int arr1[] = { 1,3,5,7,9,11,13,15,17 }; int arr2[] = { 2,4,6,8,10,12,14 }; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); return 0; }
创建一个数组用来存放排好序合并后的数组
——我这里因为使用的编译器是VS2022，不支持变长数组，所以直接申请了100大小的数组来存放合并后的序列。如果在其他编译器上可以直接申请一个m+n大小的数组
int main() { int arr1[] = { 1,3,5,7,9,11,13,15,17 }; int arr2[] = { 2,4,6,8,10,12,14 }; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); int arr3[100] = { 0 }; return 0; }
创建一个while循环，在其内部实现两个序列的合并，循环执行的条件是两个数组元素都未比较完成
实现的逻辑：
当数组arr1中的当前比较元素较小时，将数组arr1中的元素放入数组arr3，数组arr1的下标+1
当数组arr2中的当前比较元素较小时，将数组arr2中的元素放入数组arr3，数组arr2的下标+1
完成一轮比较之后，数组arr3下标+1
while (i < m && j < n) { if (arr1[i] < arr2[j]) { arr3[k] = arr1[i]; i++; } else { arr3[k] = arr2[j]; j++; } k++; }
当上面这个循环结束时，说明至少其中一个数组的元素已经输出完毕
接下来再进行判断
如果是数组arr1的元素未输出完毕，将数组arr1中元素依次输入到数组arr3中
如果是数组arr2的元素未输出完毕，将数组arr2中元素依次输入到数组arr3中
while (i < m) { arr3[k] = arr1[i]; i++; k++; } while (j < n) { arr3[k] = arr2[j]; j++; k++; }
接下来打印合并后的数组arr3
printf("合并后的数组为\n"); for (int i = 0; i < k; i++) { printf("%d ", arr3[i]); }
完整代码
#include<stdio.h> int main() { int arr1[] = { 1,3,5,7,9,11,13,15,17 }; int arr2[] = { 2,4,6,8,10,12,14,16 }; int m = sizeof(arr1) / sizeof(arr1[0]);//第一个数组的大小 int n = sizeof(arr2) / sizeof(arr2[0]);//第二个数组的大小 int arr3[100] = { 0 };//存放合并后的数组 int i = 0, j = 0, k = 0;//分别作为数组arr1，arr2，arr3的下标使用 while (i < m && j < n) { if (arr1[i] < arr2[j]) { arr3[k] = arr1[i]; i++; } else { arr3[k] = arr2[j]; j++; } k++; } while (i < m) { arr3[k] = arr1[i]; i++; k++; } while (j < n) { arr3[k] = arr2[j]; j++; k++; } printf("合并后的数组为\n"); for (int i = 0; i < k; i++) { printf("%d ", arr3[i]); } return 0; }
结果测试
