归并排序Java实现

冷不防 2022-03-11 20:49 194阅读 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 条评论，194人围观）

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

相关阅读

相关归并排序 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实现

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

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

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

1、基本思想归并排序（Merge）是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列

向右看齐/ 2022年06月06日 01:38/ 0 赞/ 201 阅读

相关 java实现归并排序算法

前面我们讲了[归并排序算法][Link 1]，接下来我们来用java代码实现呗，如下 package ttt; import java.util.A

今天药忘吃喽~/ 2022年05月09日 00:28/ 0 赞/ 191 阅读

相关归并排序Java实现

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

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

相关 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 阅读