問題描述
根據(jù)維基百科的定義：
插入排序是迭代算法逛艰，逐一獲得輸入數(shù)據(jù)造成，逐步產(chǎn)生有序的輸出序列。每步迭代中榕莺，算法從輸入序列中取出一元素俐芯，將之插入有序序列中正確的位置。如此迭代直到全部元素有序钉鸯。歸并排序進(jìn)行如下迭代操作：首先將原始序列看成 N 個只包含 1 個元素的有序子序列吧史，然后每次迭代歸并兩個相鄰的有序子序列，直到最后只剩下 1 個有序的序列唠雕。
現(xiàn)給定原始序列和由某排序算法產(chǎn)生的中間序列贸营，請你判斷該算法究竟是哪種排序算法？
輸入格式：
輸入在第一行給出正整數(shù) N (≤100)岩睁；隨后一行給出原始序列的 N 個整數(shù)钞脂；最后一行給出由某排序算法產(chǎn)生的中間序列。這里假設(shè)排序的目標(biāo)序列是升序捕儒。數(shù)字間以空格分隔冰啃。輸出格式：
首先在第 1 行中輸出Insertion Sort表示插入排序、或Merge Sort表示歸并排序刘莹；然后在第 2 行中輸出用該排序算法再迭代一輪的結(jié)果序列阎毅。題目保證每組測試的結(jié)果是唯一的。數(shù)字間以空格分隔点弯，且行首尾不得有多余空格扇调。
解決方法
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 105;
//a用來做插入 b用來做結(jié)果的對比 c用來做歸并
int a[maxn], b[maxn], c[maxn];
bool cmp(int a[], int b[], int n);
//二路歸并
void mergeSort(int A[], int n)
{
/*
flag用于在選擇相同的序列后在進(jìn)行一次歸并排序
因為題目一定有結(jié)果不是插入一定是歸并所以不用返回值
*/
int flag = 1;
for (int step = 2; step / 2 < n; step *= 2)
{
for (int i = 0; i < n; i += step)
{
int mid = i + step / 2 - 1;
if (mid + 1 < n)
{
//直接使用sort來代替?zhèn)鹘y(tǒng)的merge函數(shù)
sort(A + i, A + min(i + step - 1, n - 1) + 1);
}
}
if (flag == 0)
return;
if (cmp(c, b, n))
flag--;
}
}
bool insertSort(int A[], int n)
{
int j = 0;
/*
flag用于在選擇相同的序列后在進(jìn)行一次插入排序
*/
int flag = 1;
for (int i = 1; i < n; i++)
{
int temp = A[i];
j = i;
while (j > 0 && temp < A[j - 1])
{
A[j] = A[j - 1];
j--;
}
A[j] = temp;
if (flag == 0)
return true;
if (cmp(a, b, n))
{
flag--;
}
}
return false;
}
/*
比較兩個數(shù)組是否相同
*/
bool cmp(int a[], int b[], int n)
{
for (int i = 0; i < n; i++)
{
if (a[i] != b[i])
return false;
}
return true;
}
/*
輸出數(shù)組的元素
*/
void printArr(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d", a[i]);
if (i != n - 1)
printf(" ");
}
}
int main(void)
{
//獲取輸入
int m = 0;
scanf("%d", &m);
for (int i = 0; i < m; i++)
{
scanf("%d", a + i);
c[i] = a[i];
}
for (int i = 0; i < m; i++)
{
scanf("%d", b + i);
}
//先看看是否是插入排序是就不用去執(zhí)行歸并了
bool res1 = insertSort(a, m);
if (res1)
{
printf("Insertion Sort\n");
printArr(a, m);
}
else
{
//執(zhí)行歸并
printf("Merge Sort\n");
mergeSort(c, m);
printArr(c, m);
}
return 0;
}
基本策略
- 寫出插入排序和歸并排序的非遞歸方法來記錄每一次歸并或者插入的序列做對比
結(jié)果展示
PatB1035.png
日期問題
- 因為把注釋版的提交了一遍所以顯示的是8/19
