[数据结构与算法][PAT练级笔记] 35 Basic Level 1035 插入与归并

乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。

PAT乙级BasicLevelPractice 1035

问题分析

题设给定两组数, 第二组数是第一组数用插入排序或归并排序进行排序的某个中间状态,
要求判断使用的是哪种排序, 并用这种排序算法对排序的中间状态再排序一次并输出.

从题设中我们识别到两个功能需求:
- 判断所使用的排序算法
- 使用对应排序算法再进行一次排序

如果区分插入排序和归并排序

根据插入排序的特征, 排序过程中数组左半部分为排序部分, 右半部分为未排序部分.
而归并排序会同时变动整个数组.
题设保证了每组测试结果唯一, 所以不用担心出现插入排序和归并排序中间状态一致的情况.

我们只需要检查排序中间状态的数组是否符合"左边最长有序部分之外的另一部分是否是未排序部分(即与原数组对应部分完全西昂同)"
即, 检查第二个序列升序部分的末尾索引, 然后从该位置开始检查直到数组末尾是否都和原数组一致

得到插入排序的下一个结果

插入排序第n次的结果和第n+1次的结果, 差别在于: 左边有序部分的长度.
所以我们只需要对左起的n个元素进行排序, 其余部分不变, 排序的结果就是插入排序n次后的结果.

得到归并排序的下一个结果

归并排序第n次的结果和第n+1次的结果, 差别在于: 有序区块的长度.
比如对于数列 [3, 1, 2, 8, 7, 5, 9, 4, 6, 0]
第1次排序是以区块长度为1, 即 对[3], [1], [2], [8], [7], [5], [9], [4], [6], [0]的排序结果
第2次排序是以区块长度为2, 即 对[3, 1], [2, 8], [7, 5], [9, 4], [6, 0]的排序结果.
所以要得到第n次归并排序的结果, 我们只需要对每个长度为n的子数组进行排序, 末尾不足n的部分单独排序即可得到预期结果

完整描述步骤

1. 获取两组数列
2. 计算第二组数列从左起开始有序部分的末尾索引 k,
   检查从有序部分末尾索引开始直到整个数组结束, 是否每个值都跟原数组一致.
   如果一致, 说明右边部分没有被排序过, 则为 插入排序
   否则, 为归并排序
3. 如果是插入排序, 则将前k+1个元素进行排序(k为当前左边有序部分的长度)
   如果是归并排序, 则以k2为区块长度, 从左往右对每个区块进行排序. 末尾不足k2的部分也要单独排序

伪代码描述

1. get input of two array:

   • numbers_amount
   • numbers
   • numbers_sorted_partially

2. set current_sorted_amount = 1, sorting_method = InsertionSort;

3. for (; current_sorted_amount < numbers_amount; current_sorted_amount++):
   if numbers_sorted_partially[current_sorted_amount - 1] > numbers_sorted_partially[current_sorted_amount]:
   break;

4. for (int i = current_sorted_amount; i < numbers_amount; i++):
   if (numbers_sorted_partially[i] != numbers[i]):
   sorting_method = MergeSort

5. if sorting_method == InsertionSort:
   print “Insertion Sort”
   sort(numbers, numbers + current_sorted_amount + 1)
   else:
   print “Merge Sort”
   current_sorted_amount *= 2
   for (int i = 0; i < numbers_amount / current_sorted_amount; i++):
   sort(numbers + i * current_sorted_amount, numbers + (i+1) * current_sorted_amount)

   sort(numbers + i * current_sorted_amount, numbers + numbers_amount)

6. print numbers

完整提交代码

/*
# 问题分析
题设给定两组数, 第二组数是第一组数用插入排序或归并排序进行排序的某个中间状态,
要求判断使用的是哪种排序, 并用这种排序算法对排序的中间状态再排序一次并输出.

从题设中我们识别到两个功能需求:
    - 判断所使用的排序算法
    - 使用对应排序算法再进行一次排序

# 如果区分插入排序和归并排序
根据插入排序的特征, 排序过程中数组左半部分为排序部分, 右半部分为未排序部分.
而归并排序会同时变动整个数组.
题设保证了每组测试结果唯一, 所以不用担心出现插入排序和归并排序中间状态一致的情况.

我们只需要检查排序中间状态的数组是否符合"左边最长有序部分之外的另一部分是否是未排序部分(即与原数组对应部分完全西昂同)"
即, 检查第二个序列升序部分的末尾索引, 然后从该位置开始检查直到数组末尾是否都和原数组一致

# 得到插入排序的下一个结果
插入排序第n次的结果和第n+1次的结果, 差别在于: 左边有序部分的长度.
所以我们只需要对左起的n个元素进行排序, 其余部分不变, 排序的结果就是插入排序n次后的结果.

# 得到归并排序的下一个结果
归并排序第n次的结果和第n+1次的结果, 差别在于: 有序区块的长度.
比如对于数列 [3, 1, 2, 8, 7, 5, 9, 4, 6, 0]
第1次排序是以区块长度为1, 即 对[3], [1], [2], [8], [7], [5], [9], [4], [6], [0]的排序结果
第2次排序是以区块长度为2, 即 对[3, 1], [2, 8], [7, 5], [9, 4], [6, 0]的排序结果.
所以要得到第n次归并排序的结果, 我们只需要对每个长度为n的子数组进行排序, 末尾不足n的部分单独排序即可得到预期结果

# 完整描述步骤
1. 获取两组数列
2. 计算第二组数列从左起开始有序部分的末尾索引 k,
    检查从有序部分末尾索引开始直到整个数组结束, 是否每个值都跟原数组一致.
    如果一致, 说明右边部分没有被排序过, 则为 插入排序
    否则, 为归并排序
3. 如果是插入排序, 则将前k+1个元素进行排序(k为当前左边有序部分的长度)
    如果是归并排序, 则以k*2为区块长度, 从左往右对每个区块进行排序. 末尾不足k*2的部分也要单独排序

# 伪代码描述
1. get input of two array:
    - numbers_amount
    - numbers
    - numbers_sorted_partially
2. set current_sorted_amount = 1, sorting_method = InsertionSort;
3. for (; current_sorted_amount < numbers_amount; current_sorted_amount++):
    if numbers_sorted_partially[current_sorted_amount - 1] > numbers_sorted_partially[current_sorted_amount]:
        break;
4. for (int i = current_sorted_amount; i < numbers_amount; i++):
    if (numbers_sorted_partially[i] != numbers[i]):
        sorting_method = MergeSort
5. if sorting_method == InsertionSort:
    print "Insertion Sort"
    sort(numbers, numbers + current_sorted_amount + 1)
   else:
    print "Merge Sort"
    current_sorted_amount *= 2
    for (int i = 0; i < numbers_amount / current_sorted_amount; i++):
        sort(numbers + i * current_sorted_amount, numbers + (i+1) * current_sorted_amount)

    sort(numbers + i * current_sorted_amount, numbers + numbers_amount)

6. print numbers
*/

#include <stdio.h>
#define InsertionSortFlag 0
#define MergeSortFlag 1

int cmp(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}

void merge_sort_once(int number_amount, int *numbers, int *numbers_sorted_partially)
{
    for (int len = 1, i = 0; i < number_amount && len <= number_amount; len *= 2)
    {
        for (i = 0; i < number_amount && numbers[i] == numbers_sorted_partially[i]; i++)
            ;
        int j;
        for (j = 0; j < number_amount / len; j++)
        {
            qsort(numbers + j * len, len, sizeof(int), cmp);
        }
        qsort(numbers + j * len, number_amount % len, sizeof(int), cmp);
    }
}

int main()
{
    int number_amount;
    scanf("%d", &number_amount);

    int numbers[number_amount];
    int numbers_sorted_partially[number_amount];

    for (int i = 0; i < number_amount; i++)
    {
        scanf("%d", &numbers[i]);
    }

    for (int i = 0; i < number_amount; i++)
    {
        scanf("%d", &numbers_sorted_partially[i]);
    }

    int check_result = InsertionSortFlag;
    int sorted_amount = 1;
    for (; sorted_amount < number_amount; sorted_amount++)
    {
        if (numbers_sorted_partially[sorted_amount] < numbers_sorted_partially[sorted_amount - 1])
            break;
    }

    for (int i = sorted_amount; i < number_amount; i++)
    {
        if (numbers[i] != numbers_sorted_partially[i])
        {
            check_result = MergeSortFlag;
            break;
        }
    }

    if (check_result == MergeSortFlag)
    {
        printf("Merge Sort\n");
        merge_sort_once(number_amount, numbers, numbers_sorted_partially);
    }
    else
    {
        printf("Insertion Sort\n");
        qsort(numbers, sorted_amount + 1, sizeof(int), cmp);
    }

    for (int i = 0; i < number_amount; i++)
    {
        printf("%d", numbers[i]);
        if (i + 1 != number_amount)
        {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}