归并排序

归并排序 1.归并排序（1）基本思想 确定分界点mid = (low + high) / 2 先对左边进行归并排序，然后对右边进行归并排序 将两个有序子序列归并为一个有序序列 （2）归并排序特性 归并排序时间效率为O（nlog2n） 归并排序空间效率为O（n） 归并排序是一个稳定的排序算法 注：关于2路归并的归并树（倒立的二叉树） 二叉树的第h层最多有2h-1个结点，即满足 n ≤ 2h-1 即为 h - 1 = $\lceil log_2n \rceil$ n个元素进行2路归并，归并趟数为$\lceil log_2n \rceil$ 2.归并排序模板12345678910111213141516171819202122//写法1:for循环写法//[low...mid]和[mid+1...high]各自有序 将两个部分归并void merge(int A[], int n, int low, int mid, int high) {//需要传入数组大小n以节省不必要的空间浪费 int i, j, k; int *B = (int *)malloc(n * sizeof(int));//辅助数组B for (k = low; k <= high; ++k) B[k] = A[k]; for (i = low, j = mid + 1, k = i; i <= mid && j <= high; ++k) {//核心归并操作 if (B[i] <= B[j]) A[k] = B[i++]; else A[k] = B[j++]; } while(i <= mid) A[k++] = B[i++];//未归并完的部分直接复制到尾部 while(j <= high) A[k++] = B[j++];}void mergeSort(int A[], int n, int low, int high) { if (low < high) { int mid = (low + high)/2;//从中间划分 mergeSort(A, n, ...

合并两个有序数组 原题链接：https://leetcode.cn/problems/merge-sorted-array/ 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。 注：最终合并后数组不应由函数返回，而是存储在数组 nums1 中。 为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？ 1.双指针1234567891011121314151617181920212223242526272829//while循环写法class Solution {public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int k = m + n - 1; int i = m - 1, j = n - 1; while (i >= 0 && j >= 0) { if (nums1[i] >= nums2[j]) { nums1[k] = nums1[i]; i--; k--; } else { nums1[k] = nums2[j]; j--; k--; } } while (i >= 0) { nums1[k] = nums1[i]; i--; k--; } ...