首页 > 试题广场 >

插入与归并(25)

[编程题]插入与归并(25)

热度指数：8427 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

根据维基百科的定义：

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

10<br/>3 1 2 8 7 5 9 4 6 0<br/>1 2 3 7 8 5 9 4 6 0

输出

Insertion Sort<br/>1 2 3 5 7 8 9 4 6 0

算法知识视频讲解

Java

WZL0x7f

这题最麻烦的地方在于判断完了是归并排序后，在进行一次排序，由于归并排序的有序区很复杂，不好直接确定，所以我对原来数组（第一个输入的数组）进行归并排序按1 2 4 8 的间隔排，并在每次对比2数组是否完全一致，如果完全一致就再排一次就行。挺麻烦的。😅

import java.util.*;

public class Main{
	static int swi = 1;
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in); 
        int n = sc.nextInt();
        int k = 0;
        boolean flag = true;
        int [] arr = new int [n];
        int [] sortArr = new int [n];
        for(int i = 0; i < n; i++)
        	arr[i] = sc.nextInt();
        for(int i = 0; i < n; i++)
        	sortArr[i] = sc.nextInt();
        for(int i = 1; i < n; i++){
        	if(sortArr[i - 1] > sortArr[i]){
        		k = i;
        		break;
        	}
        }
        for(int i = k; i < n; i++){
        	if(arr[i] != sortArr[i]){
        		flag = false;
        		break;
        	}
        }
        if(flag)
        	insertionSort(sortArr, k);
        else{ 
        	int [] t = new int[arr.length];
        	for(int i = 1; i < n && swi != 0; i <<= 1, i++,swi++){
        		for(int j = 0; j < n; j += i + 1){
        			if(j + i > n)
        				sort(arr,j, n - 1,t);
        			else
        				sort(arr,j, j + i,t);
        		}
        		boolean f = check(arr, sortArr);
         		if(f) swi = -2;
        	}
        	System.out.println("Merge Sort");
        	for(int i = 0; i < arr.length - 1; i++)
    			System.out.print(arr[i] + " ");
    		System.out.print(arr[sortArr.length - 1]);
        }
    }
   private static boolean check(int[] arr, int[] sortArr) {
	   for(int k = 0 ;k < sortArr.length; k++){
			if(arr[k] != sortArr[k])return false;
		}
		return true;
	}
private static void sort(int[] arr, int start, int end, int[] temp) {
	    int i = start, j = (start + end) / 2 + 1;
		int m = (start + end) / 2, n = end;
		int k = 0;
		while (i <= m && j <= n)
		{
			if (arr[i] <= arr[j])
				temp[k++] = arr[i++];
			else
				temp[k++] = arr[j++];
		}
		
		while (i <= m)
			temp[k++] = arr[i++];
		
		while (j <= n)
			temp[k++] = arr[j++];
		
		for (i = 0; i < k; i++)
			arr[start + i] = temp[i];

		
	}
	private static void insertionSort(int[] sortArr, int k) {
		int v = sortArr[k];
		int i = k;
		while(i > 0){
			if(sortArr[i - 1] > v) sortArr[i] = sortArr[i - 1];
			else break;
			i--;
		}
		sortArr[i] = v;
		System.out.println("Insertion Sort");
		for(i = 0; i < sortArr.length - 1; i++)
			System.out.print(sortArr[i] + " ");
		System.out.print(sortArr[sortArr.length - 1]);
	}
}

发表于 2019-08-22 20:25:29 回复(1)