归并排序之Java实现

我会带着你远行 2022-06-16 06:54 151阅读 0赞

归并排序思路：现先待排序数组划分成两个数组，然后再划分，直至划分后的子数组只有一个元素（一个元素的数组既是有序数组），然后再两两合并（按照顺序合并），最终形成一个完整的有序数组。

所以归并排序核心有两个：两个数组合并排序成一个有序数组；一个数组怎么拆分成N个子数组。

代码实现：

public static void merge(int [] arr) throws Exception{
    		if(arr == null){
    			throw new Exception("输入参数有误");
    		}
    		int first = 0;
    		int last = arr.length-1;
    		merge_1(arr,first,last);
    	}
    	
    	//完成数组的拆分
    	public static void merge_1(int [] arr,int first,int last){
    		int begin = first;
    		int mid = (first+last)/2;
    		int end = last;
    		if(begin < end ){
    			merge_1(arr,begin,mid);
    			merge_1(arr,mid+1,end);
    			conbineSort(arr,begin,end,mid);
    		}
    	}
    	
    	//完成两个数组合并成一个有序数组
    	public static void conbineSort(int [] arr,int first,int last,int mid){
    		int [] p = new int[100];
    		int i = first;
    		int j = mid+1;
    		int k = 0;
    		while(i <= mid && j <= last){
    			if(arr[i] > arr[j]){
    				p[k++] = arr[j++];
    			}else {
    				p[k++] = arr[i++];
    			}
    		}
    		while(i <= mid){
    			p[k++] = arr[i++];
    		}
    		while(j <= last){
    			p[k++] = arr[j++];
    		}
    		for(int m = 0 ; m <k ; m++){
    			arr[first+m] = p[m];
    		}
    	}

测试：

public static void main(String[] args) throws Exception {
    		int [] arr = {5,9,1,3,52,13,2,8,4};
    		merge(arr);
    		for(int i : arr){
    			System.out.println(i);
    		}
    	}

参考资料：http://blog.csdn.net/morewindows/article/details/6678165

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序 JAVA实现

JAVA归并算法实现 import java.lang.reflect.Array; import java.util.Arrays;

妖狐艹你老母/ 2022年12月05日 12:09/ 0 赞/ 139 阅读

相关归并排序----java实现

归并排序归并排序是将两个有序的序列合并成一个新的有序序列。归并排序：（1）递归分解数组；将数组每次折半划分，直到把数组划分为n个长度为1的有序序列。（

旧城等待，/ 2022年09月24日 05:25/ 0 赞/ 164 阅读

相关 Java实现归并排序

本文参考自：http://blog.csdn.net/morewindows/article/details/6678165 归并排序是建立在归并操作上的一种有效的排序算法。

迷南。/ 2022年08月22日 00:04/ 0 赞/ 136 阅读

相关归并排序 java实现

2. //归并排序采用的是分治算法：分治算法的基本思想是将一个规模为N的问题分解为K个规模//较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得

深碍√TFBOYSˉ_/ 2022年08月12日 00:15/ 0 赞/ 151 阅读

相关归并排序之java实现

毕业季在即，一大波面试接踵而来，为了一份好offer，所以最近在重新刷数据结构与算法。正好在博客里面记录一下。今天是归并排序的实现。归并排序是典型的分治模式的实现，对一个

一时失言乱红尘/ 2022年08月05日 11:24/ 0 赞/ 72 阅读

相关归并排序之Java实现

归并排序思路：现先待排序数组划分成两个数组，然后再划分，直至划分后的子数组只有一个元素（一个元素的数组既是有序数组），然后再两两合并（按照顺序合并），最终形成一个完整的有序数组

我会带着你远行/ 2022年06月16日 06:54/ 0 赞/ 152 阅读

相关排序算法之归并排序及Java实现

一、排序算法的分类 1. 选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]） 2. 交换排序（[冒泡排序][Link 3]，[快速排序][Lin

忘是亡心i/ 2022年05月26日 04:07/ 0 赞/ 127 阅读

相关 java实现归并排序

public class MergeSort { public static void merge(int[] arr, int left, int

一时失言乱红尘/ 2022年02月26日 06:24/ 0 赞/ 176 阅读

相关归并排序（java实现）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

￡神魔★判官ぃ/ 2022年02月05日 04:57/ 0 赞/ 201 阅读

相关排序算法之归并排序（Java实现）

归并排序的思想是将局部有序的数组合并为一个大的有序数组，前提是需要保证局部数组有序，如果局部没有顺序，那么就拆分，再合并，最差的情况是，拆到两个数组都只有一个元素的时候，这时候

Dear 丶/ 2022年01月05日 07:21/ 0 赞/ 199 阅读