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