C语言 实现 归并排序 算法 头歌 数据结构

#include 
#include 
#include 
using namespace std;
//归并排序
void merge(int *arr, int left, int mid, int right)
{
    int *temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
    {
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid)
    {
        temp[k++] = arr[i++];
    }
    while (j <= right)
    {
        temp[k++] = arr[j++];
    }
    for (int i = 0; i < k; i++)
    {
        arr[left + i] = temp[i];
    }
    delete[] temp;
}

void print_array(int *arr, int n);
// 打印数组

int *merge_array(int *arr1, int n1, int *arr2, int n2);
// 合并数组arr1和arr2，其中 n1是arr1的个数，n2是arr2的个数

int *merge_sort(int *arr, int n);
// 归并排序：自上而下的递归方法，n是arr的个数

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

int main(int argc, const char *argv[])
{
    // insert code here...
    // std::cout << "Hello, World!n";

    int n;
    scanf("%d", &n);

    int *arr;
    arr = (int *)malloc(sizeof(int) * n);
    int *drr = (int *)malloc(sizeof(int) * 4);
    for (int i = 0; i < 4; i++)
    {
        drr[i] = i;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    // arr = merge_array(arr, n, drr, 4);
    arr = merge_sort(arr, n);

    print_array(arr, n);

    return 0;
}

int *merge_array(int *arr1, int n1, int *arr2, int n2)
//  编程实现两个有序数组arr1和arr2合并
//  函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
//  函数返回值：返回从小到大排序后的合并数组
{
    // 请在这里补充代码，完成本关任务
    
    // 合并两个有序数组
    // 创建一个新的数组，用于存放合并后的数组
    // 初始化新数组的个数为arr1和arr2的个数之和
    // 循环遍历arr1和arr2，将小的数字放入新数组
    // 返回新数组

    int *arr = new int[n2 + n1];
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2)
    {
        if (arr1[i] < arr2[j])
            arr[k++] = arr1[i++];
        else
            arr[k++] = arr2[j++];
    }
    while (i < n1)
    {
        arr[k++] = arr1[i++];
    }
    while (j < n2)
    {
        arr[k++] = arr2[j++];
    }
    return arr;
    
}
int *merge_sort(int *arr, int n)

{
    // 请在这里补充代码，完成本关任务
    
    // 归并排序
    // 如果数组长度为1，则返回数组
    // 否则，将数组分成两半，分别进行归并排序，然后将两个排序好的数组合并
    // 返回合并后的数组
    if (n == 1)
    {
        return arr;
    }
    int *arr1 = new int[n / 2];
    int *arr2 = new int[n - n / 2];
    for (int i = 0; i < n / 2; i++)
    {
        arr1[i] = arr[i];
    }
    for (int i = n / 2; i < n; i++)
    {
        arr2[i - n / 2] = arr[i];
    }
    arr1 = merge_sort(arr1, n / 2);
    arr2 = merge_sort(arr2, n - n / 2);
    arr = merge_array(arr1, n / 2, arr2, n - n / 2);
    return arr;

    
}

归并排序

//通关代码
int* merge_array(int *arr1, int n1, int* arr2, int n2)
//  编程实现两个有序数组arr1和arr2合并
//  函数参数：有序数组arr1 数组arr1长度 有序数组arr2 数组arr2长度
//  函数返回值：返回从小到大排序后的合并数组
{
    // 请在这里补充代码，完成本关任务
    
	//定义
	int arr3_length =  n1 + n2;
    int *arr3 = (int *)malloc(sizeof(int)*arr3_length);//注解①
	 
	int i=0 , j=0,t=0;
	//比较两个顺序表中的值，并将小的值放入LC中，当其中一个表比较完成后
	while(i 
将数组arr分成两个子数组，然后对两个子数组进行归并排序，最后将两个子数组归并成一个有序数组
 
函数参数：整数数组arr 数组长度
 
要求输出：调用print_array(int *arr, int n)输出前三次选择操作后的序列，以及最终的升序序列
 
函数实现：
 
1. 分组：将数组分成两个子数组，分别为arr[0..n/2]和arr[n/2+1..n]
 
2. 归并：将两个子数组进行归并排序，最后将两个子数组归并成一个有序数组
 
3. 循环直到数组长度为1，即完成排序
 
4.返回