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

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

大家好,欢迎来到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; } 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/135998.html

(0)
上一篇 2025-06-30 18:20
下一篇 2025-05-14 15:45

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信