【数据结构与算法】详解归并

大家好，欢迎来到IT知识分享网。

一、归并的定义及思路

归并就是归并排序，将两个有序的或两个以上有序的数列合并成一个有序的数列

其基本思想是：

分而治之，与快排的分治是不同的，并归是以中间点分治。

其步骤为：

第一步：确定分界点，分界点为mid=(left+right)/2。
第二步：递归排序左边和右边，即 left 和 right。
第三步：把两个有序的数列合并成一个有序的数列，即合二为一。

二、归并的代码实现

输入格式：
输入共两行。第一行包含整数n（n >= 1 && n <= ）。
第二行包含n个整数，表示整个数列。

输出格式：
输出共一行，包含n个整数，表示已排好序的数列。

代码如下：

#include <stdio.h> #define N  int tmp[N]; void merge_sort(int m[], int left, int right) { 
     if (left >= right) return; int mid = (left + right) / 2; merge_sort(m, left, mid); merge_sort(m, mid + 1, right); int k = 0; int i = left; int j = mid + 1; while (i <= mid && j <= right) { 
     if (m[i] < m[j]) { 
     tmp[k++] = m[i++]; } else { 
     tmp[k++] = m[j++]; } } while (i <= mid) { 
     tmp[k++] = m[i++]; } while (j <= right) { 
     tmp[k++] = m[j++]; } for (i = left, j = 0; i <= right; i++, j++) { 
     m[i] = tmp[j]; } } int main() { 
     int n = 0; int i = 0; int m[N]; scanf("%d", &n); for (i = 0; i < n; i++) { 
     scanf("%d", &m[i]); } merge_sort(m, 0, n - 1); for (i = 0; i < n; i++) { 
     printf("%d ", m[i]); } return 0; }