当前位置：首页 > news >正文

7-1 递归二路归并排序

news 来源：原创 2024/5/14 0:38:48

7-1 递归二路归并排序

本题目要求读入N个整数，采用递归的二路归并排序法进行排序，输出前3轮排序后的结果。

输入格式:

输入不超过100的正整数N和N个整数（空格分隔）。

输出格式:

输出三行，第一行为第一轮排序结果，第二行为第二轮排序结果，第三行为第三轮排序结果。数据间用一个空格分隔。

为简便起见，最后一个元素后也有一个空格。

输入样例:

5
5 4 3 2 1

输出样例:

4 5 3 2 1 
3 4 5 2 1 
3 4 5 1 2

简化版代码：

#include <iostream>
#include <algorithm>
using namespace std;const int N = 110;
int a[N], n, cnt;void merge_sort(int l, int r)
{if (l >= r) return ;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);sort(a + l, a + r + 1);if (++cnt > 3) return ;for (int i = 0; i < n; ++i) {printf("%d ", a[i]);}printf("\n");
}int main()
{scanf("%d", &n);for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);}merge_sort(0, n);return 0;
}

注意：代码sort(a + l, a + r + 1);为了方便起见写成这样，但实际上思路和时间复杂度差不多，如果是正常学习，还请按经典写法写。

中文注释版代码

#include <iostream>
#include <algorithm>
using namespace std;const int N = 110;
int a[N], n, cnt;// 归并排序
void merge_sort(int l, int r)
{if (l >= r) return ;int mid = l + r >> 1;merge_sort(l, mid);merge_sort(mid + 1, r);// 对[l, r]范围内的数组进行排序sort(a + l, a + r + 1);// 输出排序后的数组，最多输出三次if (++cnt > 3) return ;for (int i = 0; i < n; ++i) {printf("%d ", a[i]);}printf("\n");
}int main()
{scanf("%d", &n);// 输入数组元素for (int i = 0; i < n; ++i) {scanf("%d", &a[i]);}// 调用归并排序函数merge_sort(0, n);return 0;
}

java版代码

import java.util.Arrays;
import java.util.Scanner;public class Main {static final int N = 110;static int[] a = new int[N];static int n, cnt;// 归并排序static void mergeSort(int l, int r) {if (l >= r) return;int mid = (l + r) >> 1;mergeSort(l, mid);mergeSort(mid + 1, r);// 对[l, r]范围内的数组进行排序Arrays.sort(a, l, r + 1);// 输出排序后的数组，最多输出三次if (++cnt > 3) return;for (int i = 0; i < n; ++i) {System.out.print(a[i] + " ");}System.out.println();}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 输入数组长度n = scanner.nextInt();// 输入数组元素for (int i = 0; i < n; ++i) {a[i] = scanner.nextInt();}// 调用归并排序函数mergeSort(0, n - 1);}
}