归并排序Java实现

冷不防 2022-03-11 20:49 241阅读 0赞

思路：将一个数组左右均分，两侧排好序，再利用外排整体排序

//归并排序从小到大
    public class MergeSort {
    	public static void merge(int[] arr, int l, int m, int r) {
    		int[] help = new int[r - l + 1];// 辅助数组，用于外排
    		int p1 = l, p2 = m + 1;// 定义两个指针，分别对左右两边的数遍历
    		int i = 0;
    		while (p1 <= m && p2 <= r) {// 左右两边第一个数谁小把谁放到help，然后它的指针向后移动
    			if (arr[p1] <= arr[p2]) {
    				help[i] = arr[p1];
    				i++;
    				p1++;
    			} else {
    				help[i] = arr[p2];
    				i++;
    				p2++;
    			}
    		}
    		while (p1 <= m) {// 右边已经为空
    			help[i] = arr[p1];
    			i++;
    			p1++;
    		}
    		while (p2 <= r) {// 左边为空
    			help[i] = arr[p2];
    			i++;
    			p2++;
    		}
    		for (int j = l; j < help.length; j++) {
    			arr[j] = help[j];
    		}
    	}
    
    	public static void mergeSort(int[] arr, int l, int r) {
    		if (l == r) {// 递归中止条件
    			return;
    		}
    		int mid = (l + r) / 2;
    		mergeSort(arr, l, mid);// 对左边递归排序
    		mergeSort(arr, mid + 1, r);// 右边递归排序
    		merge(arr, l, mid, r);// 左右进行归并
    	}
    
    	public static void main(String[] args) {
    		int arr[] = { 3, 1, 5, 7, 22, 11, 77, 34, 65 };
    		mergeSort(arr, 0, arr.length - 1);
    		for (int i : arr) {
    			System.out.println(i);
    		}
    	}
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 java实现归并排序

思路：将两个或两个以上的有序序列合并成一个有序序列代码如下： public class MergeS { private static void mer

绝地灬酷狼/ 2023年05月30日 04:56/ 0 赞/ 23 阅读

相关归并排序 JAVA实现

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

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

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

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

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

相关 Java实现归并排序

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

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

相关归并排序 java实现

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

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

相关归并排序之java实现

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

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

相关归并排序之Java实现

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

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

相关归并排序Java实现

思路：将一个数组左右均分，两侧排好序，再利用外排整体排序 //归并排序从小到大 public class MergeSort { public st

冷不防/ 2022年03月11日 20:49/ 0 赞/ 242 阅读

相关 java实现归并排序

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

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

相关归并排序（java实现）

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

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