09-排序2 Insert or Merge

題目

• 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?

Input Specification:

• 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 NN numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

• 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 resuling 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.

Sample Input 1:

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

Sample Output 1:

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

Sample Input 2:

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

Sample Output 2:

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

中文題目：

根據維基百科的定義：

插入排序是疊代算法，逐一獲得輸入資料，逐漸産生有序的輸出序列。每步疊代中，算法從輸入序列中取出一進制素，将之插入有序序列中正确的位置。如此疊代直到全部元素有序。

歸并排序進行如下疊代操作：首先将原始序列看成N個隻包含1個元素的有序子序列，然後每次疊代歸并兩個相鄰的有序子序列，直到最後隻剩下1個有序的序列。

現給定原始序列和由某排序算法産生的中間序列，請你判斷該算法究竟是哪種排序算法？

輸入格式：

輸入在第一行給出正整數N (<=100)；随後一行給出原始序列的N個整數；最後一行給出由某排序算法産生的中間序列。這裡假設排序的目标序列是升序。數字間以空格分隔。

輸出格式：

首先在第1行中輸出“Insertion Sort”表示插入排序、或“Merge Sort”表示歸并排序；然後在第2行中輸出用該排序算法再疊代一輪的結果序列。題目保證每組測試的結果是唯一的。數字間以空格分隔，且行末不得有多餘空格。

      

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

typedef int ElementType;

//判斷兩個數組是否一樣
bool JudgeTheSame(int origin[],int changed[],int len) 
{
    for(int i=0;i<len;i++)
    {
        if(origin[i]!=changed[i])
            return false;
    }
    return true;
}

//進行一次插入排序，參數：待排序數組，數組長度，目前排序次數，已有序元素Nums-1個
void InsertSort(ElementType origin[],int N,int Nums)
{
    int i;
    ElementType temp=origin[Nums]; //取出未排序列中的第一個元素
    for(i=Nums;i>0&&origin[i-1]>temp;i--)
    {
        origin[i]=origin[i-1];   //從小到大排序，未找到插入位置，元素依次向後移動
    }
    origin[i]=temp;
}

void Insert_Sort(int origin[],int N,int changed[])
{
    for(int i=1;i<N;i++) //從第二個元素開始插入排序
    {
        InsertSort(origin,N,i);
        if(JudgeTheSame(origin,changed,N)) //一輪插入排序後判斷結果
        {
            cout<<"Insertion Sort"<<endl;
            InsertSort(origin,N,i+1);
            for(int j=0;j<N-1;j++)
                cout<<origin[j]<<" ";
            cout<<origin[N-1]<<endl;
            return;
        }
    }
}

/*L=左邊的起始位置，R=右邊起始位置，RightEnd=右邊終點位置*/
void Merge(ElementType A[],ElementType TempA[],int L,int R,int RightEnd)
{
    /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]歸并成一個有序序列 */
    int LeftEnd=R-1;
    int temp=L; //有序序列的起始位置
    int NumElements=RightEnd-L+1;

    while(L<=LeftEnd&&R<=RightEnd)
    {
        if(A[L]<=A[R])
            TempA[temp++]=A[L++]; /*注意下标的使用temp*/
        else 
            TempA[temp++]=A[R++];
    }
    while(L<=LeftEnd)
        TempA[temp++]=A[L++];
    while(R<=RightEnd)
        TempA[temp++]=A[R++];

    //for(int i=0;i<NumElements;i++,RightEnd--) //由于L，R等數組下标已經改變，RightEnd沒有變
    //    A[RightEnd]=TempA[RightEnd]; //拷貝資料到原始數組中
}

/*length = 目前有序子列的長度，兩兩歸并相鄰有序子列*/
void Merge_pass(ElementType A[],ElementType TempA[],int N,int length)
{
    int i,j;
    for(i=0;i<=N-2*length;i+=2*length)
        Merge(A,TempA,i,i+length,i+2*length-1);
    if(i+length<N)  //歸并最後2個子列
        Merge(A,TempA,i,i+length,N-1);
    else  //最後隻剩一個子列
    {
        for(j=i;j<N;j++)
            TempA[j]=A[j];
    }
}

void Merge_Sort(ElementType A[],int N,int changed[])
{
    int length=1; //初始化子序列長度
    ElementType *TempA;
    TempA=(ElementType*)malloc(N*sizeof(ElementType)); //提前配置設定好空間

    if(TempA!=NULL)
    {
        while(length<N)
        {
            Merge_pass(A,TempA,N,length);
            if(JudgeTheSame(TempA,changed,N)) //歸并排序後的結果
            {
                cout<<"Merge Sort\n";
                length*=2;
                Merge_pass(TempA,A,N,length); //再歸并一次,交換了順序,節約空間，反複利用A,TempA
                for(int i=0;i<N-1;i++)
                    cout<<A[i]<<" ";
                cout<<A[N-1]<<endl;
                return;
            }

            length*=2;
            Merge_pass(TempA,A,N,length);
            if(JudgeTheSame(TempA,changed,N)) //歸并排序後的結果
            {
                cout<<"Merge Sort\n";
                length*=2;
                Merge_pass(A,TempA,N,length); //再歸并一次,交換了順序
                for(int i=0;i<N-1;i++)
                    cout << TempA[i] << " ";
                cout << TempA[N - 1] << endl;
                return;
            }

            length*=2;
        }
        free(TempA);
    }
    else
    {
        cout<<"空間不足"<<endl;
    }
}

int main()
{
    int N;
    int origin[105],origin_copy[105],changed[105];
    cin>>N;
    for(int i=0;i<N;i++)
    {
        cin>>origin[i];
        origin_copy[i]=origin[i];
    }

    for(int i=0;i<N;i++)  //中間排序結果
        cin>>changed[i];

    Insert_Sort(origin,N,changed);
    Merge_Sort(origin_copy,N,changed);

    return 0;
}

      

Reference

• ​
• 09-排序2 Insert or Merge

C/C++基本文法學習

STL

C++ primer