#include <cstdio>#include <algorithm>#include <iostream>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 ZERO\n");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长度// 函数返回值：返回从小到大排序后的合并数组{// 请在这里补充代码，完成本关任务/********** Begin *********/// 合并两个有序数组// 创建一个新的数组，用于存放合并后的数组// 初始化新数组的个数为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++];elsearr[k++] = arr2[j++];}while (i < n1){arr[k++] = arr1[i++];}while (j < n2){arr[k++] = arr2[j++];}return arr;/********** End **********/}int *merge_sort(int *arr, int n){// 请在这里补充代码，完成本关任务/********** Begin *********/// 归并排序// 如果数组长度为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;/********** End **********/}
归并排序
//通关代码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;//比较两个顺序表中的值，并将小的值放入LC中，当其中一个表比较完成后while(i<n1&&j<n2){if(arr1[i]<=arr2[j])arr3[t++] = arr1[i++];elsearr3[t++] = arr2[j++];}//直接将另一个未比较完成的表中的剩余值全部放到LC中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)//注解② {//从mid将数组分成两部分 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 **********/}
将数组arr分成两个子数组，然后对两个子数组进行归并排序，最后将两个子数组归并成一个有序数组
函数参数：整数数组arr 数组长度
要求输出：调用print_array(int *arr, int n)输出前三次选择操作后的序列，以及最终的升序序列
函数实现：
1. 分组：将数组分成两个子数组，分别为arr[0..n/2]和arr[n/2+1..n]
2. 归并：将两个子数组进行归并排序，最后将两个子数组归并成一个有序数组
3. 循环直到数组长度为1，即完成排序
4.返回
