中国保密在线网站培训系统,郴州新网官网,宝宝身上出现很多小红疹怎么办,网络销售渠道归并排序#xff1a;
排序原理#xff1a;
1、尽可能的一组数据拆分成两个元素相等的子组#xff0c;并对每一个子组继续拆分#xff0c;知道拆分后的每个子组的元素个数是1为止。
2、将相邻的两个子组进行合并成一个有序的大组
3、不断重复步骤2#xff0c;直到最终只…归并排序
排序原理
1、尽可能的一组数据拆分成两个元素相等的子组并对每一个子组继续拆分知道拆分后的每个子组的元素个数是1为止。
2、将相邻的两个子组进行合并成一个有序的大组
3、不断重复步骤2直到最终只有一个组为止 代码实现
package demo02.sort;//排序代码
public class Merge {private static Comparable[] assist;//归并所需要的辅助数组/*对数组a中的元素进行排序*/public static void sort(Comparable[] a) {assist new Comparable[a.length];int lo 0;int hi a.length-1;sort(a, lo, hi);}/*对数组a中从lo到hi的元素进行排序*/private static void sort(Comparable[] a, int lo, int hi) {if (hi lo) {return;}int mid lo (hi - lo) / 2;//对lo到mid之间的元素进行排序sort(a, lo, mid);//对mid1到hi之间的元素进行排序sort(a, mid1, hi);//对lo到mid这组数据和mid到hi这组数据进行归并merge(a, lo, mid, hi);}/*对数组中从lo到mid为一组从mid1到hi为一组对这两组数据进行归并*/private static void merge(Comparable[] a, int lo, int mid, int hi) {//lo到mid这组数据和mid1到hi这组数据归并到辅助数组assist对应的索引处int i lo;//定义一个指针指向assist数组中开始填充数据的索引int p1 lo;//定义一个指针指向第一组数据的第一个元素int p2 mid 1;//定义一个指针指向第二组数据的第一个元素//比较左边小组和右边小组中的元素大小哪个小就把哪个数据填充到assist数组中while (p1 mid p2 hi) {if (less(a[p1], a[p2])) {assist[i] a[p1];} else {assist[i] a[p2];}}//上面的循环结束后如果退出循环的条件是p1mid则证明左边小组中的数据已经归并完毕如果退出循环的条件是p2hi,则证明右边小组的数据已经填充完毕//所以需要把未填充完毕的数据继续填充到assist中,//下面两个循环只会执行其中的一个while(p1mid){assist[i]a[p1];}while(p2hi){assist[i]a[p2];}//到现在为止assist数组中从lo到hi的元素是有序的再把数据拷贝到a数组中对应的索引处for (int indexlo;indexhi;index){a[index]assist[index];}}/*比较v元素是否小于w元素*/private static boolean less(Comparable v, Comparable w) {return v.compareTo(w) 0;}/*数组元素i和j交换位置*/private static void exch(Comparable[] a, int i, int j) {Comparable t a[i];a[i] a[j];a[j] t;}
}package demo02.test;
import demo02.sort.Merge;
import java.util.Arrays;
public class TestMerge {public static void main(String[] args) throws Exception {Integer[] arr {8, 4, 5, 7, 1, 3, 6, 2};Merge.sort(arr);System.out.println(Arrays.toString(arr));}
} 运行结果 归并排序时间复杂度分析
归并排序是分治思想的最典型的例子上面的算法中对a[lo…hi]进行排序先将它分为a[lo…mid]和a[mid1…hi] 两部分分别通过递归调用将他们单独排序最后将有序的子数组归并为最终的排序结果。该递归的出口在于如果 一个数组不能再被分为两个子数组那么就会执行merge进行归并在归并的时候判断元素的大小进行排序。
归并排序的时间复杂度为log2(n)* 2^(log2(n))log2(n)*n,根据大O推导法则忽略底 数最终归并排序的时间复杂度为O(nlogn); 归并排序的缺点
需要申请额外的数组空间导致空间复杂度提升是典型的以空间换时间的操作。
