非递归归并排序详细分析

非递归归并排序详细分析

前言

以前做的一个分析，今天把它发出来了

代码

import java.util.Arrays;import java.util.Random;import java.util.Scanner;/** * 归并排序的非递归实现，主要是思想 用 int 数组模拟 * 要先理解思路： 将待排序集合一分为二，直到 待排序集合只剩下 1 个元素为止 。 然后不断合并2个排好序的数组段。 * 用合并算法将它们排序，构成n/2组长度为2的排序序的数组段，然后再将它们排序成长度为4的排好序的子数组段 * 如此继续，直到整个数组排好序 * @authorpublic class UnRecursiveMergeSort /** * 并归算法 合并 c[left:mid] 和 c[mid+1:right] 到 d[left:right] * 数组 c 的left 到 mid 部分已经排好序 mid+1 到 right 部分也排好序 * @param c 待合并的数组c * @param d * @param left 数组 c 的left 下标 * @param mid 数组 c 的 middle 下标 * @param private static void merge(int [] c,int [] d,int left,int mid,int right){ int i = left, j = mid+1, k = left; //两边进行比较，哪个更小就把哪个放入数组d while((i<=mid)&&(j<=right)){ if(c[i]<=c[j]) d[k++] = c[i++]; else d[k++] = c[j++]; } //如果数组左边部分最大的几个元素值 大于右边部分的 ，左边就会剩下还未放入数组d的元素 //或者理解为 上面while循环中 j>right 跳出while循环了 ，而 i < mid while(i<=mid) d[k++] = c[i++]; //i>mid 而 j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。