19.合并两个有序数组-LeetCode-Java

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。 说明: 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例: 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6] /** * 插入排序：1.直接插入排序 2.折半插入排序 3.希尔排序 */ // 方法一：使用直接插入排序 将nums2数组中每个元素插入到已排序数组nums1中 class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int nums1Len = m; for (int num : nums2) { int i; for (i = nums1Len - 1; i >= 0; --i) { if (num >= nums1[i]) { for (int j = nums1Len - 1; j >= i + 1; --j) { nums1[j + 1] = nums1[j]; } nums1[i + 1] = num; nums1Len++; break; } } if (i == -1) { for (int k = nums1Len - 1; k >= 0; k--) { nums1[k + 1] = nums1[k]; } nums1[0] = num; nums1Len++; } } } } /** * 方法二：双指针遍历 从前往后依次遍历nums1、nums2 */ class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] nums1_copy = new int[m]; System.arraycopy(nums1, 0, nums1_copy, 0, m); // nums1_copy 和 nums2 的指针 int p1 = 0, p2 = 0; // nums1的指针 int p = 0; while (p1 < m && p2 < n) { nums1[p++] = nums1_copy[p1] <= nums2[p2] ? nums1_copy[p1++] : nums2[p2++]; } // nums1_copy遍历完,将nums2余下的全部拷贝到nums1中 if (p1 == m && p2 < n) { System.arraycopy(nums2, p2, nums1, p, n - p2); } // nums2遍历完,将nums1_copy余下的全部拷贝到nums1中 if (p2 == n && p1 < m) { System.arraycopy(nums1_copy, p1, nums1, p, m - p1); } } } 数组拷贝：System.arraycopy(Object src,int srcPos,Object dest, int destPos,int length); nums1[p++] = nums1_copy[p1] <= nums2[p2] ? nums1_copy[p1++] : nums2[p2++]; 等价于： nums1[p] = nums1_copy[p1] <= nums2[p2] ? nums1_copy[p1] : nums2[p2]; p1++; p2++; p++;