精华内容
下载资源
问答
  • 递归版package MergeSort;import Utils.SortUtils;... * 归并排序递归版 * @author liguodong */public class Demo02 { public static void mergeSort(int[] a){ mSort(a, a, 0, a.length-1); } /**

    递归版

    package MergeSort;
    
    import Utils.SortUtils;
    /**
     * 归并排序递归版
     * @author liguodong
     */
    
    public class Demo02 {
    
        public static void mergeSort(int[] a){
            mSort(a, a, 0, a.length-1);
        }
        /**
         * 
         * @param SR为待排序的数据
         * @param TR1为排序之后的数据
         * @param s
         * @param t
         */
        public static void mSort(int[] SR,int[] TR1, int s,int t){
            int m;
            int[] TR2 = new int[SR.length];
    
            if(s==t){
                TR1[s] = SR[s];
            }else {
                m = (s+t)/2;//4
                mSort(SR, TR2, s, m);
                mSort(SR, TR2, m+1, t);
                merge(TR2, TR1, s, m, t);//0 4 8
            }
    
        }
    
        //归并两个有序的数组
        /**
         * @param SR 有两个有序数组
         * @param TR 将SR的两个有序数组合并为一个数组TR
         * @param i
         * @param m
         * @param n
         */
        public static void merge(int[] SR,int[] TR,int i,int m,int n){
            int j,k,l;
    
            //i(0~4) j(5~8)
            for(j=m+1,k=i; i<=m && j<=n; k++){
    
                if(SR[i]<SR[j]){
                    TR[k] = SR[i++];
                }else{
                    TR[k] = SR[j++];
                }
            }
    
    
            if(i<=m){
                for (l = 0; l <= m-i ; l++) {
                    TR[k+l] = SR[i+l];
                }
            }
    
            if(j<=n){
                for (l = 0; l <= n-j; l++) {
                    TR[k+l] = SR[j+l];
                }
            }
        }
    
        public static void main(String[] args) {
            int[] a = {2,3,5,4,1,6,9,8,7};
            mergeSort(a);
            SortUtils.printString(a);
        }
    }

    复杂度分析

    迭代版

    package MergeSort;
    import Utils.SortUtils;
    
    /**
     * 递归排序迭代版
     * @author liguodong
     *
     */
    
    public class Demo03 {
    
        public static void mergeSort(int[] a){
            int[] TR = new int[a.length];//用于存放归并结果
    
            int k=1;//起始,子序列长度为1
            while(k<a.length){
                mergePass(a, TR, k, a.length);//将原先无序的数据两两归并入TR
                k = 2*k;//子序列长度加倍
                mergePass(TR, a, k, a.length);//将TR中已经两两归并的有序序列再归并回数组a
                k = 2*k;//子序列长度加倍
            }
        }
    
        public static void mergePass(int[] SR, int [] TR,int s,int len){
    
            int i=0;
            while (i < len-2*s+1) {//8
                merge(SR,TR,i,i+s-1,i+2*s-1);//两两归并
                i=i+2*s;
            }
    
            //处理最后的尾数
            //i=8
            if(i< len-s+1){//9
                merge(SR, TR, i, i+s-1, len-1);//归并最后两个序列
            }else {
                for (int j = i; j < len; j++) {//若最后只剩下单个子序列
                    TR[j] = SR[j];
                }
            }   
        }
    
        public static void merge(int[] SR,int[] TR,int i,int m,int n){
            int j,k,l;
    
            //i(0~4) j(5~8)
            for(j=m+1,k=i; i<=m && j<=n; k++){
    
                if(SR[i]<SR[j]){
                    TR[k] = SR[i++];
                }else{
                    TR[k] = SR[j++];
                }
            }
    
    
            if(i<=m){
                for (l = 0; l <= m-i ; l++) {
                    TR[k+l] = SR[i+l];
                }
            }
    
            if(j<=n){
                for (l = 0; l <= n-j; l++) {
                    TR[k+l] = SR[j+l];
                }
            }
        }
    
        public static void main(String[] args) {
            int[] a = {2,3,5,4,1,6,9,8,7,10,20,45,32,28,44,31,55,43,23,21,23,21,33,21};
            mergeSort(a);
            SortUtils.printString(a);
        }
    }

    展开全文
  • 归并排序_java

    2021-06-28 10:11:12
     可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。 合并相邻有序子序列  再来看看.

    基本思想

      归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

    分而治之

       可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。阶段可以理解为就是递归拆分子序列的过程,递归深度为log2n。

    合并相邻有序子序列

      再来看看阶段,我们需要将两个已经有序的子序列合并成一个有序序列,比如上图中的最后一次合并,要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列,合并为最终序列[1,2,3,4,5,6,7,8],来看下实现步骤。

    代码实现

    package sortdemo;
    
    import java.util.Arrays;
    
    
    public class MergeSort {
        public static void main(String []args){
            int []arr = {9,8,7,6,5,4,3,2,1};
            sort(arr);
            System.out.println(Arrays.toString(arr));
        }
        public static void sort(int []arr){
            int []temp = new int[arr.length];//在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
            sort(arr,0,arr.length-1,temp);
        }
        private static void sort(int[] arr,int left,int right,int []temp){
            if(left<right){
                int mid = (left+right)/2;
                sort(arr,left,mid,temp);//左边归并排序,使得左子序列有序
                sort(arr,mid+1,right,temp);//右边归并排序,使得右子序列有序
                merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
            }
        }
        private static void merge(int[] arr,int left,int mid,int right,int[] temp){
            int i = left;//左序列指针
            int j = mid+1;//右序列指针
            int t = 0;//临时数组指针
            while (i<=mid && j<=right){
                if(arr[i]<=arr[j]){
                    temp[t++] = arr[i++];
                }else {
                    temp[t++] = arr[j++];
                }
            }
            while(i<=mid){//将左边剩余元素填充进temp中
                temp[t++] = arr[i++];
            }
            while(j<=right){//将右序列剩余元素填充进temp中
                temp[t++] = arr[j++];
            }
            t = 0;
            //将temp中的元素全部拷贝到原数组中
            while(left <= right){
                arr[left++] = temp[t++];
            }
        }
    }

    最后

      归并排序是稳定排序,它也是一种十分高效的排序,能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法,就是归并排序的优化版本。从上文的图中可看出,每次合并操作的平均时间复杂度为O(n),而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且,归并排序的最好,最坏,平均时间复杂度均为O(nlogn)。

     

    参考资料:https://www.cnblogs.com/chengxiao/p/6194356.html

    展开全文
  • 归并排序——Java

    2020-01-29 17:34:32
    文章目录归并排序原地归并的抽象方法 归并排序 两个有序数组归并成一个更大的有序数组,就叫归并。 归并排序是一种递归排序算法,就对一个数组来说,可以先将它(递归地)分成两半分别排序,然后将结果归并起来。 ...

    归并排序

    两个有序数组归并成一个更大的有序数组,就叫归并。

    归并排序是一种递归排序算法,就对一个数组来说,可以先将它(递归地)分成两半分别排序,然后将结果归并起来。

    原地归并的抽象方法

    两个不同的有序数组如何实现归并?
    一个最简单直接地方法就是创建一个最够大的第三数组,然后将两个有序数组的元素从大到小的排到第三数组中,这就叫原地归并。

    /**
    * 原地归并的抽象方法
    * 归并,数组两边一定要是有序的
    */
    public static void merge(Comparable[] a, int lo, int mid, int hi){
            //将a[lo..mid]和a[mid+1..hi]归并
            int i = lo, j = mid+1;
    
            //将a[lo..hi]复制到aux[lo..hi]
            for(int k=lo; k<=hi; k++){
                aux[k] = a[k];
            }
    
            //归并回到a[lo..hi]
            for(int k=lo; k<=hi; k++){
                if(i>mid){
                    a[k] = aux[j++];
                }else if(j>hi){
                    a[k] = aux[i++];
                }else if(less(aux[j], aux[i])){
                    a[k] = aux[j++];
                }else{
                    a[k] = aux[i++];
                }
            }
        }
    

    主要操作就是第二个for循环里的四个判断:

    1、数组1走完(将数组2当前元素放入数组3)

    2、数组2走完(将数组1当前元素放入数组3)

    3、数组1当前元素小于数组2当前元素(将数组1当前元素放入数组3)

    4、数组2当前元素小于等于数组1当前元素(将数组2当前元素放入数组3)
    在这里插入图片描述

    自顶向下的归并排序

    基于原地归并的抽象实现一种递归归并。

    这段递归代码是归纳证明算法能正确地将数组排序的基础:**如果能将两个子数组排序,就能通过归并两个子数组来对整个数组排序。**这一切是通过递归实现的,也叫递归归并。

    完整代码:

    public class 归并排序 {
    
        private static Comparable[] aux;
    
        public static void sort(Comparable[] a)
        {
            aux = new Comparable[a.length];//一次性分配空间
            sort(a,0,a.length-1);
        }
        private static void sort(Comparable[] a, int lo, int hi)
        {
            if (hi<=lo)
                return;
            int mid = lo + (hi-lo)/2;
            //将左半边排序
            sort(a,lo, mid);
            //将右半边排序
            sort(a,mid+1, hi);
            //左右归并
            merge(a, lo, mid, hi);
        }
        //归并,数组两边一定要是有序的
        public static void merge(Comparable[] a, int lo, int mid, int hi) {
            int i = lo, j = mid + 1;
            Comparable[] aux = new Comparable[hi + 1];
            for (int k = lo; k <= hi; k++) {
                aux[k] = a[k];
            }
            for (int k = lo; k <= hi; k++) {
                if (i > mid) {
                    a[k] = aux[j++];
                } else if (j > hi) {
                    a[k] = aux[i++];
                } else if (less(aux[i], aux[j])) {
                    a[k] = aux[i++];
                } else {
                    a[k] = aux[j++];
                }
            }
        }
        public static boolean less(Comparable v, Comparable w){
            //对元素进行比较
            return v.compareTo(w)<0;
        }
    
        public static void exch(Comparable[] a,int i,int j){
            //交换元素
            Comparable t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    
        public static void show(Comparable[] a){
            //在单行中打印数组
            for(int i=0;i<a.length;i++){
                System.out.print(a[i]+"");
                System.out.println();
            }
        }
    
        public static boolean isSorted(Comparable[] a){
            //测试数组元素是否有序
            for(int i=0;i<a.length;i++){
                if(less(a[i],a[i-1])){
                    return false;
                }
            }
            return true;
        }
    
        public static  void main(String[] args){
            String[] a={"4","2","5","2","7","5","3","2"};
            sort(a);
            assert isSorted(a);
            show(a);
        }
    }
    

    以一个数组为例展示调用过程:
    在这里插入图片描述
    sort(a,0,7)

    将左半部分排序

    左sort(a,0,3)
    ->左sort(a,0,1)
    ->>左sort(a,0,0)
    ->>右sort(a,1,1)
    ->>merge(a,0,0,1)
    ->右sort(a,2,3)
    ->>左sort(a,2,2)
    ->>右sort(a,3,3)
    ->>merge(a,2,2,3)
    ->merge(a,0,1,3)
    右sort(a,4,7)
    ->左sort(a,4,5)
    ->>左sort(a,4,4)
    ->>右sort(a,5,5)
    ->>merge(a,4,4,5)
    ->右sort(a,6,7)
    ->>左sort(a,6,6)
    ->>右sort(a,7,7)
    ->>merge(a,6,6,7)
    ->merge(a,4,5,7)
    merge(a,0,3,7)

    算法第四版的配图:
    在这里插入图片描述
    对于长度为N的任意数组,自顶向下的归并排序需要 1/2NlogN 至 NlogN次比较
    在这里插入图片描述
    对于长度为N的任意数组,自顶向下的归并排序最多需要访问数组 6NlogN次
    每次归并最多需要访问数组6N次,2N次复制,2N次将排好的元素移动回去,另外最多比较2N次,另最多有logN次归并。

    自底向上的归并排序

    先归并小数组,再归并大数组

    public static void sort(Comparable[] a) {
            int n = a.length;
            aux = new Comparable[n];
            for (int sz = 1; sz < n; sz = sz + sz) //sz子数组的大小
                for (int lo = 0; lo < n - sz; lo += sz + sz) //lo子数组索引
                    merge(a, lo, lo + sz - 1, Math.min(lo + 2 * sz - 1, n - 1));
        }
    

    自底向上的归并排序会多次遍历整个数组,根据子数组大小进行两两归并。子数组的大小sz的初始值为1,每次加倍。最后一个子数组的大小只有在数组大小是sz的偶数倍的时候才会等于sz(否则它会比sz小)。

    在这里插入图片描述
    对于长度为N的任意数组,自底向上的归并排序需要1/2NlgN至NlgN次比较,最多访问数组6NlgN次。

    复杂度

    时间复杂度:NlogN
    空间复杂度:
    对数组来说,空间复杂度为N;对链表来说,递归方法空间复杂度为N,迭代方法为O(1)

    三项优化

    ①对小规模子数组使用插入排序

    用不同的方法处理小规模数组能改进大多递归算法的性能,在小数组上上,插入排序可能比并归排序更快。

    ②测试数组是否有序

    根据归并排序的特点,每次归并的两个小数组都是有序的,当a[mid]<=a[mid+1]时我们可以跳过merge方法,这样并不影响排序的递归调用。

    ③不将元素复制到辅助数组

    我们可以节省将数组复制到辅助数组的时间,这需要一些技巧。先克隆原数组到辅助数组,然后在之后的递归交换输入数组和辅助数组的角色(通过看代码更容易理解)

    参考文章:
    《算法第四版》
    https://www.cnblogs.com/Unicron/p/9637488.html

    展开全文
  • 归并排序(java实现)

    2019-04-20 15:27:14
    归并排序基本思想:将待排序的序列看成n个长度为1的表,两两合并,得到长度为2的有序序列,再对这些子序列进行合并,得到长度为4的有序序列...重复上述过程,直到最后一个子序列长度为n即可。 package SortRank; ...

    归并排序基本思想:将待排序的序列看成n个长度为1的表,两两合并,得到长度为2的有序序列,再对这些子序列进行合并,得到长度为4的有序序列...重复上述过程,直到最后一个子序列长度为n即可。

    package SortRank;
    
    /**
     * 归并排序:两两合并数组
     * 分两种:递归+迭代
     * @author 18322
     *
     */
    
    public class MergeSort {
    	public static void main(String[] args) {
    		int arr[] = {87,45,78,32,17,65,53,9,122,133};
    		MergeSort ms = new MergeSort();
    		System.out.println("数组排序前的顺序:");
    		ms.printArray(arr);
    		ms.sort(arr);
    		System.out.println("数组最终排序的顺序:");
    		ms.printArray(arr);
    	}
    	
    	private void sort(int[] arr) {
    		sortRecursion(arr, 0 ,arr.length-1);
    	}
    	
    //递归方式
    	private void sortRecursion(int[] arr, int left, int right) {
    		if(left == right) return;
    		int middle = left + (right - left) / 2;
    		sortRecursion(arr, left, middle);
    		sortRecursion(arr, middle+1, right);
    		mergeArr(arr, left, middle, right);
    	}
    	
    	private void mergeArr(int[] arr, int left, int middle, int right) {
    		int[] num = new int[right-left+1];
    		int i = left;
    		int j = middle + 1;
    		int k = 0;
    		while(i <= middle && j <= right) {
    			num[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    		}
    		
    		while(i <= middle) {
    			num[k++] = arr[i++];
    		}
    		
    		while(j <= right) {
    			num[k++] = arr[j++];
    		}
    		int index = 0;
    		while(left <= right) {
    			arr[left++] = num[index++];
    		}
    	}
    	
    	private void printArray(int arr[]) {
    		for(int in : arr) {
    			System.out.print(in + "\t");
    		}
    		System.out.println();
    	}
    	
    
    //迭代方式
    	/*private void sort(int[] arr) {
    		int len = 1;   //长度
    		while(len < arr.length) {
    			for(int i = 0; i < arr.length; i += 2*len) {
    				sortIterator(arr, i, len);
    			}
    			System.out.println("长度为" + len + "时数组的顺序:");
    			printArray(arr);
    			len *= 2;
    		}
    	}
    	
    	private void sortIterator(int[] arr, int start, int len) {
    		int[] num = new int[len+len];
    		int i = start;
    		int j = start + len;
    		int k = 0;
    		while(i < start+len && (j < start+len+len && j < arr.length)) {
    			num[k++] = arr[i]<arr[j] ? arr[i++] : arr[j++];
    		}
    		while(i < start+len && i < arr.length) {
    			num[k++] = arr[i++];
    		}
    		
    		while(j < start+len+len && j < arr.length) {
    			num[k++] = arr[j++];
    		}
    		int index = 0;
    		int right = start + len + len;
    		while(start < arr.length && start < right) {
    			arr[start++] = num[index++];
    		}
    	}**/
    }

     

    展开全文
  • 归并排序java实现

    2015-09-15 23:15:57
    今天是归并排序的实现。 归并排序是典型的分治模式的实现,对一个数组A,采取三步实现:分解,解决,合并 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列 解决:使用归并排序递归地排序两个子序列 ...
  • //使用非递归的方式来实现归并排序 int len = arr.length; int k = 1;//为什么要从1开始?一开始对长度为1的序列进行两两合并 while (k ) { MergePass(arr, k, len); k *= 2; } } //MergePass方法负责将...
  • 归并排序Java实现)

    2020-11-07 23:07:30
    归并排序既可以采用递归思想,也可以采用迭代思想,无论采用哪种思想,其大致都可以分为三大步骤: 分解序列:将序列进行二分 序列排序:将二分后的各个子序列进行排序 序列排序:合并各个子序列 算法图示(递归...
  • —— 约翰·冯·诺伊曼归并排序简介归并排序(Merge Sort),是创建在归并操作上的一种有效的排序算法。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治...
  • 归并排序java实现

    2017-09-26 18:08:00
    本着溯本求源的精神,我先去看了下归并排序JAVA的实现,虽然一直以来对归并排序的原理清楚的,但不曾自己写过。网上找了别人实现好的代码,然后自己理解后填上了注释,记录如下以供日后回顾(此代码的尾递归理论上...
  • 归并排序java

    2021-05-14 19:52:38
    归并排序 归并排序就是将两个有序序列合并成为一个有序序列。因此,将两个有序子序列合并成一个有序序列是归并排序的基础算法。 两个有序子序列合并 void Merge(int a[],int b[],int l,int m,int h){ int i,j,k; ...
  • 归并排序-java实现

    2018-09-13 16:10:53
    基本思想: 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-...可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。...
  • 归并排序Java

    2019-06-05 23:36:31
    图解排序算法(四)之归并排序 注明:转自博客园 作者:dreamcatcher-cx 出处:<http://www.cnblogs.com/chengxiao/> 本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在页面明显...
  • 35. 排序算法(8):归并排序迭代实现

    千次阅读 多人点赞 2018-03-10 16:48:43
    归并排序迭代方法的原理及实现
  • 归并排序 - Java实现

    2018-08-27 11:51:02
    归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"...
  • 本文主要介绍十大经典排序算法中的“归并排序”,并附上冒泡排序算法的Java、JavaScript、PHP、Python、Go语言实现。 1、十大经典排序算法介绍 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中...
  •  归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各...
  • 归并排序(java描述)

    2019-08-10 17:43:56
    注:该代码中并没有在每次迭代的合并过程中申请与待合并数组相同大小的空间而是在外面直接一次性给他分配N的空间,后续操作只依赖下标即可。 这是由于前者的做法需在每次执行merge时不断 分配空间结束时并且释放...
  • 归并排序java实现)

    2018-11-28 13:11:37
    思路 算法属性 ...分阶段:可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程,递归深度为log2...
  • 归并排序java实现

    2020-02-28 16:34:35
    归并排序使用递归算法实现比较简单,但是递归调用比较浪费资源,所以使用循环迭代实现了一下java代码
  • 归并排序java)笔记

    2020-06-04 11:38:15
    } } //迭代排序数组 public static void mergeIteration(int arr[],int low,int hight) { int mid=(low+hight)/2; if (low) { mergeIteration(arr, low, mid); mergeIteration(arr, mid+1, hight)...
  • 归并排序原理 归并排序建立在归并操作上的一种有效,稳定的排序算法,是采用分治法的一个非常典型的应用。将集合数据拆分成若干个子序列,并使各个子序列有序,依次合并,并进行排序,直到合并为整个数据集合有序...
  • 归并排序(merge sort)算法的思想是
  • 归并排序 递归实现 分析 归并排序:分治、递归思想 将一个数组A分成左右两部分A1、A2,那么对A的排序可以分为以下两步 1.将A1、A2分别排好序 2.将A1、A2两个各自有序的数组合并成一个有序数组,这个过程叫做归并...
  • 八大排序算法 一、直接插入 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 二、希尔排序 - 1.基本思路 - 2.代码实现 - 3.时间复杂度和空间复杂度 三、简单选择 - 1.基本思路 - 2.代码实现 - 3.时间复杂度...
  • 什么情况使用归并排序? 假设有一个已经按照职位排序的员工列表,现在要按照工资排序。若两个员工工资相等,此时采用归并排序(稳定),将会保留职位排列的顺序。即首先按照工资排序,工资同者按职位排序。 package ...
  • 文章目录堆排序java代码实现单元测试归并排序java代码实现单元测试 堆排序 java代码实现 package csdn.dreamzuora.sort; import java.util.List; /** * Title: 抽象出排序类 * Description: * * @version 1.0 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,212
精华内容 3,684
关键字:

归并排序迭代java

java 订阅