建网站去哪里备案,廊坊网络推广优化公司,企业建站官网,网页图片素材归并#xff1a;将两个有序的数组归并成一个更大的有序数组。 要将一个数组排序#xff0c;可以先递归的将它分成两半分别排序#xff0c;然后将结果归并起来#xff0c;这就是归并排序。归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比将两个有序的数组归并成一个更大的有序数组。 要将一个数组排序可以先递归的将它分成两半分别排序然后将结果归并起来这就是归并排序。归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比它的主要缺点是它需要额外的与N成正比的空间。 实现归并的一种直接了当的方法是将两个不同的有序数组归并到第三个数组中。实现的方法很简单创建一个适当大小的数组然后将两个输入数组的元素一个个从小到大放入这个数组中。 当归并将一个大数组排序时我们需要进行很多次归并因此在每次归并时都创建一个新数组来存储排序结果会带来问题。 原地归并的数据抽象
public static void merge(int[] a,int lo,int mid,int hi){int ilo,jmid1;for (int klo;khi;kk1)aux[k]a[k];for (int klo;khi;kk1)if (imid) a[k]aux[j];else if (jhi) a[k]aux[i];else if (aux[j]aux[i]) a[k]aux[j];else a[k]aux[i];list_deal.printArray(a);} 基于原地归并的抽象实现了一种递归归并
public class Merge {private static int [] aux;public static void sort(int[] a){auxnew int[a.length];sort(a,0,a.length-1);}public static void merge(int[] a,int lo,int mid,int hi){int ilo,jmid1;for (int klo;khi;kk1)aux[k]a[k];for (int klo;khi;kk1)if (imid) a[k]aux[j];else if (jhi) a[k]aux[i];else if (aux[j]aux[i]) a[k]aux[j];else a[k]aux[i];list_deal.printArray(a);}private static void sort(int[] a ,int lo,int hi){if (hilo) return;int midlo(hi-lo)/2;sort(a,lo,mid);sort(a,mid1,hi);merge(a,lo,mid,hi);}public static void main(String[] args) {int[] a{534,745,264,864,136,967,254,745,734,269,538,265,825,158,139,100};list_deal.printArray(a);sort(a);list_deal.printArray(a);}
}排序过程
534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100
534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100
534 745 264 864 136 967 254 745 734 269 538 265 825 158 139 100
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100
264 534 745 864 136 967 254 745 734 269 538 265 825 158 139 100
264 534 745 864 136 254 745 967 734 269 538 265 825 158 139 100
136 254 264 534 745 745 864 967 734 269 538 265 825 158 139 100
136 254 264 534 745 745 864 967 269 734 538 265 825 158 139 100
136 254 264 534 745 745 864 967 269 734 265 538 825 158 139 100
136 254 264 534 745 745 864 967 265 269 538 734 825 158 139 100
136 254 264 534 745 745 864 967 265 269 538 734 158 825 139 100
136 254 264 534 745 745 864 967 265 269 538 734 158 825 100 139
136 254 264 534 745 745 864 967 265 269 538 734 100 139 158 825
136 254 264 534 745 745 864 967 100 139 158 265 269 538 734 825
100 136 139 158 254 264 265 269 534 538 734 745 745 825 864 967 通过过程可以看到递归归并的过程是将大数组不断分割为小数组然后循环进行小数组排序、归并。 对于长度为N的任意数组自顶向下的归并排序需要进行1/2*NlogN至NlogN次比较。 对于长度为N的任意数组自顶向下的归并排序最多需要访问数组6NlogN次。 对于小数组上有可能插入排序或者选择排序比归并排序更快所以插入递归归并有可能比全递归归并排序快但是代码也更复杂。
