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

发布于:2022-11-07 ⋅ 阅读:(18) ⋅ 点赞:(0) ⋅ 评论:(0)

目录

任务描述

相关知识

归并排序算法

编程要求

测试说明

参考代码 


任务描述

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

相关知识

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

归并排序算法

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

  • 算法步骤:

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

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

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

编程要求

本关的编程任务是补全右侧代码片段merge_arraymerge_sortBeginEnd中间的代码,具体要求如下:

  • merge_array中,实现两个有序数组arr1arr2合并。
  • 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 **********/
}