宽带动态ip如何做网站访问,国内外网站建设比较,游戏币网站怎么做,做市场推广应该掌握什么技巧题目
归并排序也是一种基于分治法的排序算法。为了排序长度为n的数组#xff0c;需要先排序两个长度为n/2的子数组#xff0c;然后合并这两个排序的子数组#xff0c;于是整个数组也就排序完毕。
分析
归并排序可以用迭代代码实现。例如#xff0c;输入一个长度为8的数组…题目
归并排序也是一种基于分治法的排序算法。为了排序长度为n的数组需要先排序两个长度为n/2的子数组然后合并这两个排序的子数组于是整个数组也就排序完毕。
分析
归并排序可以用迭代代码实现。例如输入一个长度为8的数组[41562783]
可以先合并相邻的长度为1的子数组得到4个排序的长度为2的子数组。然后合并相邻的长度为2的子数组得到2个排序的长度为4的子数组最后合并相邻的长度为4的子数组此时整个数组排序完毕
解迭代
public class Test {public static void main(String[] args) {int[] nums {4, 1, 5, 6, 2, 7, 8, 3};int[] result sortArray(nums);for (int item : result) {System.out.println(item);}}public static int[] sortArray(int[] nums) {int length nums.length;int[] src nums;int[] dst new int[length];for (int seg 1; seg length; seg seg) {// 合并分段的长度for (int start 0; start length; start seg * 2) {int mid Math.min(start seg, length);// i,j两个游标在遍历的时候j可能先到达end因为end可能取的是length的值int end Math.min(start seg * 2, length);int i start, j mid, k start;while (i mid || j end) {if (j end || (i mid src[i] src[j])) {dst[k] src[i];}else {dst[k] src[j];}}}int[] temp src;src dst;dst temp;}return src;}}解递归
public class Test {public static void main(String[] args) {int[] nums {4, 1, 5, 6, 2, 7, 8, 3};int[] result sortArray(nums);for (int item : result) {System.out.println(item);}}public static int[] sortArray(int[] nums) {int[] dst new int[nums.length];dst Arrays.copyOf(nums, nums.length);mergeSort(nums, dst, 0, nums.length);return dst;}private static void mergeSort(int[] src, int[] dst, int start, int end) {if (start 1 end) {return;}int mid (start end) / 2;mergeSort(dst, src, start, mid);// 注意src和dst反过来了两个数组来回颠倒mergeSort(dst, src, mid, end);int i start, j mid, k start;while (i mid || j end) {if (j end || (i mid src[i] src[j])) {dst[k] src[i];}else {dst[k] src[j];}}}}
