Java 详细讲解分治算法如何实现归并排序

目录
  • 1.什么是分治算法
    • 分治法
    • 基本思想
  • 2.分治算法的体现——归并排序
    • 归并排序
    • 基本思想
  • 3.代码实现

1.什么是分治算法

分治法

分治法，字面意思是“分而治之”，就是把一个复杂的1问题分成两个或多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并，这个思想是很多高效算法的基础，例如排序算法(快速排序，归并排序)，傅里叶变换(快速傅里叶变换)等。

基本思想

分治法的基本思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

2.分治算法的体现——归并排序

归并排序

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

基本思想

流程图（以对数组[8,4,5,7,1,3,6,2]排序为例）

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将

[4,5,7,8］和［1,2,3,6］两个已经有序的子序列，合并为最终序列［1,2,3,4,5,6,7,8]，来看下实现步骤。

3.代码实现

package Sort;

import java.util.Arrays;
/**
 * 归并排序：
 *
 * 利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，
 *
 * 而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
 * @author lenovo
 *
 */
public class MergeSort {
	public static void main(String[] args) {
		int[] a= {5,8,6,3,9,8,7,1,4,21,-8,46};
		int[] temp=new int[a.length];
		mergeSort(a, 0, a.length-1, temp);
		System.out.println(Arrays.toString(a));
	}
	public static void mergeSort(int[] arr,int left,int right,int[] temp) {
		if(left<right) {
			int mid=(left+right)/2;
			mergeSort(arr, left, mid, temp);
			mergeSort(arr, mid+1,right, temp);
			merge(arr, left, mid, right, temp);
		}
	}
	public static void merge(int[] arr,int left,int mid,int right,int[] temp) {
		int l=left;//左边序列的起始位置
		int r=mid+1;//右边序列的起始位置
		int t=0;//中间数组的当前元素下标
		while(l<=mid &&r<=right ) {//左边或右边没结束
			//那边小就将那边的元素放入到临时数组中
			if(arr[l]<=arr[r]) {
				temp[t++]=arr[l++];
			}else {
				temp[t++]=arr[r++];
			}
		}
		//while循环结束，说明有一边已经遍历完毕，将另一边剩余的元素放入到临时数组中
		while(l<=mid) {
			temp[t++]=arr[l++];
		}
		while(r<=right) {
			temp[t++]=arr[r++];
		}
		//将临时数组中的有序序列copy到原数组中
		t=0;
		int templeft=left;
		while(templeft<=right) {
			arr[templeft++]=temp[t++];
		}
	}
}

到此这篇关于Java 详细讲解分治算法如何实现归并排序的文章就介绍到这了,更多相关Java 归并排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • JAVA十大排序算法之归并排序详解

    JAVA十大排序算法之归并排序详解

    目录 归并排序 怎么分 怎么治 代码实现 时间复杂度 算法稳定性 总结 归并排序 归并,指合并,合在一起.归并排序(Merge Sort)是建立在归并操作上的一种排序算法.其主要思想是分而治之.什么是分而治之?分而治之就是将一个复杂的计算,按照设定的阈值进行分解成多个计算,然后将各个计算结果进行汇总.即"分"就是把一个大的通过递归拆成若干个小的,"治"就是将分后的结果在合在一起. 若将两个有序集合并成一个有序表,称为2-路归并,与之对应的还有多路归并. 怎么分 对于

  • java 中归并排序算法详解

    java 中归并排序算法详解

    java 中归并排序算法详解 归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其

  • Java分治归并排序算法实例详解

    本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,

  • java 排序算法之归并排序

    java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • 图解Java排序算法之归并排序

    图解Java排序算法之归并排序

    目录 基本思想 合并相邻有序子序列 代码实现 总结 基本思想 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之). 分而治之 可以看到这种结构很像一棵完全二叉树,本文的归并排序我们采用递归去实现(也可采用迭代的方式去实现).分阶段可以理解为就是递归拆分子序列的过程,递归深

  • java 归并排序的实例详解

    java 归并排序的实例详解 归并排序 归并排序,指的是将两个已经排序的序列合并成一个序列的操作. 归并操作的过程如下: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 Java代码 /** * 归并排序 * * @param ts */ @SuppressWa

  • Java 十大排序算法之归并排序刨析

    目录 归并排序原理 归并排序API设计 归并排序代码实现 归并排序的时间复杂度分析 归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计 类名 Merge 构造方法 Merge():创建Merge对象 成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行

  • Java 详细讲解分治算法如何实现归并排序

    Java 详细讲解分治算法如何实现归并排序

    目录 1.什么是分治算法 分治法 基本思想 2.分治算法的体现--归并排序 归并排序 基本思想 3.代码实现 1.什么是分治算法 分治法 分治法,字面意思是"分而治之",就是把一个复杂的1问题分成两个或多个相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题可以简单地直接求解,原问题的解即子问题的解的合并,这个思想是很多高效算法的基础,例如排序算法(快速排序,归并排序),傅里叶变换(快速傅里叶变换)等. 基本思想 分治法的基本思想:将一个难以直接解决的大问题,分割成一些规模较小

  • Java详细讲解分析双指针法的使用

    Java详细讲解分析双指针法的使用

    目录 前言 1.判断链表是否有环 2.查找链表中间的元素 3.奇偶排序前奇后偶 4.删除排序链表的重复元素 5.三数之和 6.分割链表 7.合并两个有序的数组 8.两数之和—输入有序数组 9.长度最小的子数组 10.排序链表 前言 通常用在线性的数据结构中,比如链表和数组. 指针其实就是数据的索引或者链表的结点.两个指针朝着左右两个方向移动,直到满足搜索条件. 双指针可分为同向双指针.异向双指针.快慢指针.滑动窗口.根据需求选择双指针的模型,比如 删除数组或链表中重复的元素,同向双指针(线性表前

  • Java详细讲解堆排序与时间复杂度的概念

    Java详细讲解堆排序与时间复杂度的概念

    目录 一.堆排序 1.什么是堆排序 2.堆排序思想 3.代码实现 二.时间复杂度分析 1.初始化建堆 2.排序重建堆 3.总结 一.堆排序 1.什么是堆排序 (1)堆排序:堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. (2)堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆:或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

  • Java详细讲解Math和Random类中有哪些常用方法

    Java详细讲解Math和Random类中有哪些常用方法

    java.lang.Math当中提供了一系列的静态方法用于科学计算:其方法的参数和返回值的类型一般为double型. 下来我就简单的介绍一下Math类中常用的方法. public static int abs(double a) 求绝对值 public static double sqrt(double a) 求平方根 public static double pow(double a, double b) 求a的b次幂 public static double max(double a, do

  • C语言超详细讲解排序算法上篇

    C语言超详细讲解排序算法上篇

    目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序 进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序 基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集

  • Java详细讲解不同版本的接口语法和抽象类与接口的区别

    Java详细讲解不同版本的接口语法和抽象类与接口的区别

    目录 什么是接口? 接口的语法: (JDK7.0) 接口的语法: (JDK8.0) 接口的语法: (JDK9.0)—(私有方法) 接口的分类 常量接口: 空接口: 函数式接口: 什么是接口? 说到接口,USB大家肯定不陌生~接口是一种标准.规范.注意:接口一旦制定好,使用者和实现者都必须遵循的标准. 接口的语法: (JDK7.0) (1) 关键字:interface (2) 语法:  interface 接口名{} (3) 接口编译之后会生成对应的 .class文件 (4) 接口不能创建对象,但

  • Java 详细讲解用堆解决Top-k问题

    Java 详细讲解用堆解决Top-k问题

    目录 1.什么是堆? 堆结构 大根堆 VS 小根堆 大根堆(最大堆) 小根堆(最小堆) 优先级队列(PriorityQueue) 2.top-k问题解决思路 要解决 top-k 问题,我们应该先熟悉一种数据结构 - 堆(优先级队列),已经了解的朋友可以跳过哦. 1.什么是堆? 堆结构 堆其实就是一种二叉树,但是普通的二叉树是以链式结构进行储存数据的,而堆是以数组进行顺序存储数据的.那么什么样的二叉树才适合用顺序存储的方式呢? 我们假设一颗普通的二叉树可以用数组存储,那么就可以得到如下结构: 我们

  • Java 详细讲解线程安全与同步附实例与注释

    Java 详细讲解线程安全与同步附实例与注释

    目录 线程安全问题 实例: 存钱取钱问题 买票问题 线程安全问题 分析问题 解决方案 线程同步 同步语句 synchronize(obj)的原理 同步方法 同步方法的本质 线程安全问题 多个线程可能会共享(访问)同一个资源 比如访问同一个对象,同一个变量,同一个文件 当多个线程访问同一块资源时,很容易引发数据错乱和数据安全问题,称为线程安全问题 什么情况下会出现线程安全问题 多个线程共享同一个资源 且至少有一个线程正在执行写的操作 实例: 存钱取钱问题 分别有存钱和取钱2个线程 存钱      

  • Java 详细讲解线程的状态及部分常用方法

    可以通过 Thread.getState 方法获得线程的状态(线程一共有 6 种状态) NEW(新建)new:尚未启动 RUNNABLE(可运行状态)runnable:正在 JVM 中运行:或者正在等待操作系统的其他资源(比如处理器) //有些编程语言会把RUNNABLE分成2种情况//1.running//2.ready//以上2种在Java中都属于RUNNABLE BLOCKED(阻塞状态) blocked:正在等待监视器锁(内部锁) WAITING(等待状态) waiting:在等待另一个

  • Java 详细讲解线程的状态及部分常用方法

    可以通过 Thread.getState 方法获得线程的状态(线程一共有 6 种状态) NEW(新建)new:尚未启动 RUNNABLE(可运行状态)runnable:正在 JVM 中运行:或者正在等待操作系统的其他资源(比如处理器) //有些编程语言会把RUNNABLE分成2种情况//1.running//2.ready//以上2种在Java中都属于RUNNABLE BLOCKED(阻塞状态) blocked:正在等待监视器锁(内部锁) WAITING(等待状态) waiting:在等待另一个

随机推荐