归并排序及其性能分析(动图演示) | 您所在的位置:网站首页 › 冒泡排序的动态图 › 归并排序及其性能分析(动图演示) |
归并排序及其性能分析
十大排序算法及其性能总结基本思路算法介绍算法步骤
动图演示代码实现性能分析时间复杂度空间复杂度稳定性
十大排序算法及其性能总结
十大排序算法及其性能总结 基本思路 算法介绍归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 作为一种典型的分而治之思想的算法应用,归并排序的实现由两种方法: 1.自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法); 2.自下而上的迭代; 算法步骤1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列; 2.设定两个指针,最初位置分别为两个已经排序序列的起始位置; 3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置; 4.重复步骤 3 直到某一指针达到序列尾; 5.将另一序列剩下的所有元素直接复制到合并序列尾。 动图演示 代码实现 public class MergeSort implements IArraySort { @Override static int[] arr; public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝,不改变参数内容 arr =Arrays.copyOf(sourceArray,sourceArray.length); merge(0, arr.length-1); return arr; } public void merge(int left,int right) { if(left==right) { return; } merge(left,left+(right-left)/2); merge(left+(right-left)/2+1, right); int[] arr0=new int[right-left+1]; int flagl=left; int flagr=left+(right-left)/2+1; for(int i=0;i arr0[i]=arr[flagl]; flagl++; } else { arr0[i]=arr[flagr]; flagr++; } } for(int i = 0;i |
CopyRight 2018-2019 实验室设备网 版权所有 |