首页 > 试题广场 >

Insert or Merge (25)

[编程题]Insert or Merge (25)
  • 热度指数：2751 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
According to Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration,
insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts
it there. It repeats until no input elements remain.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is
considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1
sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some
sorting method, can you tell which sorting method we are using?

输入描述:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are 
given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target 
sequence is always ascending. All the numbers in a line are separated by a space.


输出描述:
For each test case, print in the first line either "Insertion Sort" or "Merge Sort" to indicate the method used to obtain the partial result. 
Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is 
unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the 
line.
示例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
算法知识视频讲解
添加回答
推荐
orgcheng头像 orgcheng
根据插入排序的特点，先判断迭代后的数组是否为插入排序产生的，
即前K个数组如果是有序的，那么剩余的N-K个数保存原来的顺序和位置。
例如：
原：3 1 28 7 5 9 4 6 0
新：1 2 3 7 8 5 9 4 6 0
在新数组中，{1，2，3}是有序的，｛5，9，4，6，0｝保持原样，因此它是插入排序后的的部分过程，否则为归并排序的部分过程。

如果是插入排序，接着从5开始调用插排序即可。

如果是归并排序，那么开头2^x个数据是有序，接着把数组每2^(x+1)个数据排序即可。

import java.io.PrintStream;
import java.text.ParseException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static Scanner in = new Scanner(System.in);
    public static PrintStream out = System.out;
 
    /**
     * @param array 要排序数组
     * @param len	array[0 - len]是有序的
     * @param val	待插入的值
     */
    public static void insertSort(int[] array,int len, int val){
        int i;
        for(i=0;i<=len;++i){
            if(array[i]>val){
                break;
            }
        }
        while(len>=i){
            array[len+1]=array[len];
            --len;
        }
        array[i]=val;
    }
    /**
     * 判断数组array[left ~ right]是否是有序的
     */
    public static boolean beSorted(int[] array,int left,int right){
        for(int i=left;i<right;++i){
            if(array[i]>array[i+1])
                return false;
        }
        return true;
    }
    
    /**
     * 修改后的归并排序
     * @param array
     * @param left
     * @param right
     */
    public static void mergeSort(int[] array,int left, int right){
        int range = 2;
        // 求出已经排序的范围
        while(beSorted(array, left, left+range-1)){
            range*=2;
        }
        
        for(int i=0;i<=right;i+=range){
            if(i+range<=right){
                Arrays.sort(array,i,i+range);
            }else{
                Arrays.sort(array,i,right+1);
            }
        }
         
    }
    public static void main(String[] args) throws ParseException {
        int N = in.nextInt();
        int[] array = new int[N];
        int[] sorted = new int[N];
         
        int i,index;
        for(i=0;i<N;++i)
            array[i]=in.nextInt();
        for(i=0;i<N;++i)
            sorted[i]=in.nextInt();
        for(i=0;i<N-1;++i){
            if(sorted[i]>sorted[i+1]){
                break;
            }
        }
        index=i;
        for(i+=1;i<N;++i){
            if(array[i]!=sorted[i]){
                break;
            }
        }
        if(i>=N){
            out.println("Insertion Sort");
            insertSort(sorted, index, sorted[index+1]);
            for(i=0;i<N-1;++i)
                out.print(sorted[i]+" ");
            out.println(sorted[N-1]);
            
        }else{
            out.println("Merge Sort");
            mergeSort(sorted, 0,sorted.length-1);
            for(i=0;i<N-1;++i)
                out.print(sorted[i]+" ");
            out.println(sorted[N-1]);
        }
    }
}

编辑于 2015-08-18 22:53:24 回复(0)
提交观点

问题信息

数组 排序
难度：
0条回答 8751浏览

热门推荐

通过挑战的用户

相关试题

Insert or Merge (25)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号