java实现归并排序算法

归并排序算法思想:
分而治之(divide - conquer);每个递归过程涉及三个步骤
第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
第三, 合并: 合并两个排好序的子序列,生成排序结果.

public static void mergeSort(int[] a, int[] tmp, int left, int right) {
    if (left < right) {
      int mid = left + (right - left) / 2;
      mergeSort(a, tmp, left, mid);// 左排序
      mergeSort(a, tmp, mid + 1, right);// 右排序
      merge(a, tmp, left, mid + 1, right);// 左右合并
    }
  }
public static void merge(int[] a, int[] tmp, int left, int rightPos,
      int right) {
    int leftEnd = rightPos - 1;
    int tmpPos = left;
    int num = right - left + 1;
    while (left <= leftEnd && rightPos <= right) {
      if (a[left] < a[rightPos]) {
        tmp[tmpPos++] = a[left++];
      } else {
        tmp[tmpPos++] = a[rightPos++];
      }
    }
    while (left <= leftEnd) {
      tmp[tmpPos++] = a[left++];
    }
    while (rightPos <= right) {
      tmp[tmpPos++] = a[rightPos++];
    }
    for (int i = 0; i < num; i++, right--) {
      a[right] = tmp[right];
    }
  }

归并算法示意图：

以上所述就是本文的全部内容了，希望大家能够喜欢。

赞 (0)

相关推荐

  • java数据结构排序算法之归并排序详解

    本文实例讲述了java数据结构排序算法之归并排序.分享给大家供大家参考,具体如下: 在前面说的那几种排序都是将一组记录按关键字大小排成一个有序的序列,而归并排序的思想是:基于合并,将两个或两个以上有序表合并成一个新的有序表 归并排序算法:假设初始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个子序列长度为1,然后两两归并,得到n/2个长度为2(n为奇数的时候,最后一个序列的长度为1)的有序子序列.在此基础上,再对长度为2的有序子序列进行亮亮归并,得到若干个长度为4的有序子序列.如此重

  • Java经典排序算法之归并排序详解

    Java经典排序算法之归并排序详解

    一.归并排序 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. 归并过程为:比较a[i]和a[j]的大小,若a[i]≤a[j],则将第一个有序表中的元素a[i]复制到r[k]中,并令i和k分别加上1:否则将第二个有序表中的元素a[j]复制到r[k]中,并令j和k分别加上1,如此循环下去,直

  • 归并排序的原理及java代码实现

    归并排序的原理及java代码实现

    概述 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序采用的是递归来实现,属于"分而治之",将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组"归并"到一起,归并排序最重要的也就是这个"归并"的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间. 效果图: 步骤 申请空间,

  • java 归并排序的实例详解

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

  • 深入探究TimSort对归并排序算法的优化及Java实现

    简介 MergeSort对已经反向排好序的输入时复杂度为O(n^2),而timsort就是针对这种情况,对MergeSort进行优化而产生的,平均复杂度为n*O(log n),最好的情况为O(n),最坏情况n*O(log n).并且TimSort是一种稳定性排序.思想是先对待排序列进行分区,然后再对分区进行合并,看起来和MergeSort步骤一样,但是其中有一些针对反向和大规模数据的优化处理. 归并排序的优化思想 归并排序有以下几点优化方法: 和快速排序一样,对于小数组可以使用插入排序或者选择排

  • java 中归并排序算法详解

    java 中归并排序算法详解

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

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

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

  • 图解Java中归并排序算法的原理与实现

    图解Java中归并排序算法的原理与实现

    目录 一.基本思想 二.算法分析 1.算法描述 2.过程分析 3.动图演示 三.算法实现 一.基本思想 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 二.算法分析 1.算法描述 把长度为n的输入序列分成两个长度为n/2的子序列:对这两个子序列分别采用归并排序:将两个排序好的子序列合并

  • java实现归并排序算法

    java实现归并排序算法

    归并排序算法思想: 分而治之(divide - conquer);每个递归过程涉及三个步骤 第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 第二, 治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作 第三, 合并: 合并两个排好序的子序列,生成排序结果. public static void mergeSort(int[] a, int[] tmp, int left, int right) { if (left < righ

  • Java实现归并排序的示例代码

    Java实现归并排序的示例代码

    目录 1.算法理解 2.实现代码 3.实现效果 1.算法理解 参考:图解Java中归并排序算法的原理与实现 2.实现代码 import java.lang.reflect.Array; import java.util.*; public class MergeSort{ // 我们的算法类不允许产生任何实例 private MergeSort(){} // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Compara

  • Java 归并排序算法、堆排序算法实例详解

    Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • 浅析java 归并排序算法

    浅析java 归并排序算法

    归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))

  • Java轻松入门冒泡 选择 插入 希尔 归并排序算法

    Java轻松入门冒泡 选择 插入 希尔 归并排序算法

    今天我们主要看一些简单的排序 常见的时间复杂度 常数阶Ο(1) 对数阶Ο(log2n) 线性阶Ο(n) 线性对数阶Ο(nlog2n) 平方阶Ο(n²) 立方阶Ο(n³) K次方阶Ο(n^k) 指数阶Ο(2^n) 常见的时间复杂度对应图 Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n²)<Ο(n³)<…<Ο(2^n) <Ο(n!)<O(n^n) 冒泡排序(Quicksort) 算法描述: ①. 比较相邻的元素.如果第一个比第二个大,就交

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

随机推荐