1035 插入与归并（JAVA）

旧城等待， 2023-09-28 18:19 15阅读 0赞

根据维基百科的定义：

**插入排序**是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

**归并排序**进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

#### 输入格式： ####

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

#### 输出格式： ####

首先在第 1 行中输出`Insertion Sort`表示插入排序、或`Merge Sort`表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

#### 输入样例 1： ####

10
    3 1 2 8 7 5 9 4 6 0
    1 2 3 7 8 5 9 4 6 0

#### 输出样例 1： ####

Insertion Sort
    1 2 3 5 7 8 9 4 6 0

#### 输入样例 2： ####

10
    3 1 2 8 7 5 9 4 0 6
    1 3 2 8 5 7 4 9 0 6

#### 输出样例 2： ####

Merge Sort
    1 2 3 8 4 5 7 9 0 6

#### 代码实现： ####

import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.Arrays;
     
    public class Main {
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            String[] pre = br.readLine().split(" ");
            String[] later = br.readLine().split(" ");
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(pre[i]);
                b[i] = Integer.parseInt(later[i]);
            }
            
            int i = 0;
            while(b[i] <= b[i + 1] && i < n){
            	i++;
            }
            //判断排好序的位置
            boolean isInsert = true;
            for (int j = i + 1; j < n; j++) {
                if (a[j] != b[j]) {//插入排序过程中不会改变后方元素索引
                    isInsert = false;
                    break;
                }
            }
            //3 1 2 8 7 5 9 4 6 0
            //1 2 3 7 8 5 9 4 6 0
            if (isInsert) { 	
                System.out.println("Insertion Sort");
                //再加一个数字进行排序
                sort(a, 0, i + 1);//1 2 3 5 7 8 9 4 6 0
            } else {
            	//3 1 2 8 7 5 9 4 0 6
            	//1 3 2 8 5 7 4 9 0 6
                System.out.println("Merge Sort");
                int k = 1;
                boolean flag = false;
                while (flag == false) {
                	//当a==b时，再执行一次，下一次判断时跳出
                    flag = Arrays.equals(a, b);//使用 Arrays.equals()方法比较两个数组元素是否相等
                    k = k * 2;
                    int p = 0;
                    for (p = 0; p < n / k; p++)
                    	//p是分成的一个一个小组，k时每个组的成员个数
                    	//一组的起始时p*k，结束时下一组的开始位置减一
                        sort(a, p * k, (p + 1) * k - 1);
                    //分完组后剩下的不够的做一次分组内的归并
                    //开始是n/k*k（组数*长度），结束是到数组的最后
                    sort(a, n / k * k, n - 1);//1 2 3 8 4 5 7 9 0 6
                }
            }
            for (int k = 0; k < n - 1; k++) 
                System.out.print(a[k] + " ");
            System.out.print(a[n - 1]);
        }
      //自定义交换排序，也可用Arrays.sort，但是位置限制有点麻烦
        public static void sort(int[] a, int from, int to) {
            for (int i = from; i < to; i++) {
                for (int j = i + 1; j <= to; j++) {
                    if (a[j] < a[i]) {//按升序排序
                        int temp = a[i];
                        a[i] = a[j];
                        a[j] = temp;
                    }
                }
            }
        }
    }