归并排序算法

任务描述

本关任务：实现归并排序算法，并将乱序数列变成升序。

相关知识

为了完成本关任务，你需要掌握：1.归并排序算法。

归并排序算法

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，是采用分治法Divide and Conquer的一个非常典型的应用。分Divide：将问题分成一些小的问题然后递归求解；治Conquer：将分的阶段得到的各答案合并在一起。

• 算法步骤：

1. 把长度为n的输入序列分成两个长度为n/2的子序列；

2. 对这两个子序列分别采用归并排序；

3. 将两个排序好的子序列合并成一个最终的排序序列。

编程要求

本关的编程任务是补全右侧代码片段merge_array和merge_sort中Begin至End中间的代码，具体要求如下：

• 在merge_array中，实现两个有序数组arr1和arr2合并。
• 在merge_sort中，实现归并排序：自上而下的递归方法。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。

以下是平台的测试样例：

测试输入：

10

7 1 4 6 8 9 5 2 3 10

预期输出：

1 2 3 4 5 6 7 8 9 10

测试输入：

15

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48

预期输出：

2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

---

//
//  sort_.cpp
//  Sort
//
//  Created by ljpc on 2018/4/20.
//  Copyright ? 2018年 ljpc. All rights reserved.
//

#include "sort_.h"

void print_array(int *arr, int n)
// 打印数组
{
    if(n==0){
        printf("ERROR: Array length is ZERO\n");
        return;
    }
    printf("%d", arr[0]);
    for (int i=1; i<n; i++) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}

int* merge_array(int *arr1, int n1, int* arr2, int n2)
//  编程实现两个有序数组arr1和arr2合并
//  函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
//  函数返回值：返回从小到大排序后的合并数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
int* arr = (int*)malloc(sizeof(int)*(n1+n2));
    int p = 0;
    int p1 = 0;
    int p2 = 0;
    while (p1<n1 || p2<n2) {
        if(p1<n1 && p2<n2){
            // 自上而下的递归方法使得这两个数组各自是有序的
            // 选择两个数组较小的给arr
            if (arr1[p1]<arr2[p2]) {
                arr[p++] = arr1[p1++];
            }else{
                arr[p++] = arr2[p2++];
            }
        }else if(p1<n1){
            // arr2排完了，余下arr1
            arr[p++] = arr1[p1++];
        }else if(p2<n2){
            // arr1排完了，余下arr2
            arr[p++] = arr2[p2++];
        }
    }
    return arr;
    
    /********** End **********/
}
int* merge_sort(int *arr, int n)
//  基于merge_array函数编程实现归并排序：自上而下的递归方法
//  函数参数：有序数组arr 数组arr长度
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
if(n==1){
        return arr;
    }
    int m = n/2;
    int* arr1 = (int*)malloc(sizeof(int)*(m));
    int* arr2 = (int*)malloc(sizeof(int)*(n-m));
    for (int i=0, j=0; i<m; i++, j++) {
        // 左半边数组给arr1
        arr1[j] = arr[i];
    }
    for (int i=m, j=0; i<n; i++, j++) {
        // 右半边数组给arr2
        arr2[j] = arr[i];
    }
    // 递归子数组
    arr1 = merge_sort(arr1, m);
    arr2 = merge_sort(arr2, n-m);
    // 合并子数组
    return merge_array(arr1, m, arr2, n-m);
    
    /********** End **********/
}