数据结构-十大经典排序算法 第5关：归并排序

目录

任务描述

相关知识

归并排序算法

编程要求

测试说明

参考代码 

任务描述

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

相关知识

为了完成本关任务，你需要掌握：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 arr3_length =  n1 + n2;
    int *arr3 = (int *)malloc(sizeof(int)*arr3_length);
	int i=0 , j=0,t=0;
	while(i<n1&&j<n2)
		{
			if(arr1[i]<=arr2[j])
				arr3[t++] = arr1[i++];
			else
				arr3[t++] = arr2[j++];	
		}
	if(i==n1)
		{
			while(t<arr3_length)
				arr3[t++] = arr2[j++];	
		}
	else
		{
			while(t<arr3_length)
			arr3[t++] = arr1[i++];
		}
	return arr3; 
    /********** End **********/
}
int* merge_sort(int *arr, int n)
//  基于merge_array函数编程实现归并排序：自上而下的递归方法
//  函数参数：有序数组arr 数组arr长度
//  函数返回值：返回从小到大排序后的数组
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    int mid ;
    int left = 0 ,right = n;
	mid = (left+right)/2;
    if(right!=1)
    {
        int *Arr_1 = &arr[left],*Arr_2 = &arr[mid];
        Arr_1 = merge_sort(Arr_1,mid);
        Arr_2 = merge_sort(Arr_2,right-mid);
        arr = merge_array(Arr_1,mid,Arr_2,right-mid);
    }
    return arr;
    /********** End **********/
}