Java排序之归并排序

gityuan 发布于2019-08-15 18:10 / 2019人阅读

摘要：排序之归并排序简介归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则成为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合并排序。

Java排序之归并排序 1. 简介

归并排序的算法是将多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表，则成为二路合并。对于一个原始的待排序数列，往往可以通过分割的方法来归结为多路合并排序。

2. 归并排序思路

将长度为n的待排序数组看做是由n个有序长度为1的数组组成

将其两两合并，得到长度为2的有序数组

然后再对这些子表进行合并，得到长度为4的有序数组

重复上述过程，一直到最后的子表长度为n也就完成了排序

3. 代码实例

归并排序有两种实现方式：递归和非递归。在看归并排序的代码之前先来看一下怎么和合并两个有序数组：

// 基础，合并两个有序数组
public static int[] merge2Arr(int[] arr1, int[] arr2) {
  int len1 = arr1.length;
  int len2 = arr2.length;
  int[] res = new int[len1 + len2];  // 使用一个数组用来存储排好序的数组
  int i = 0, j = 0, k = 0;
  while(i < len1 && j < len2) {
    res[k++] = arr1[i] < arr2[j]? arr1[i++] : arr2[j++];
  }
  while(i < len1) {
    res[k++] = arr1[i++];
  }
  while(j < len2) {
    res[k++] = arr2[j++];
  }
  return res;
}

归并排序的递归实现：

// 归并排序，递归实现
public void sortMergeRecursion(int[] nums) {
  sortMergeRecursionHelper(nums, 0, nums.length - 1);
}
public void sortMergeRecursionHelper(int[] nums,int left, int right) {
  if(left == right) return;  // 当待排序的序列长度为1时，递归开始回溯，进行merge
  int middle = left + (right - left) / 2;
  sortMergeRecursionHelper(nums, left, middle);
  sortMergeRecursionHelper(nums, middle + 1, right);
  mergeArr(nums, left, middle, right);
}
public void mergeArr(int[] nums, int left, int middle, int right) {
  int[] tem = new int[right - left + 1];
  int i = left, j = middle + 1, k = 0;
  while(i <= middle && j <= right) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i <= middle) {
    tem[k++] = nums[i++];
  }
  while(j <= right) {
    tem[k++] = nums[j++];
  }
  // 将辅助数组数据写入原数组
  int index = 0;
  while(left <= right) {
    nums[left++] = tem[index++];
  }
}

归并排序的非递归实现（迭代）：

// 归并排序，非递归实现(迭代)
public void sortMergeIteration(int[] nums) {
  int len = 1;  // 初始排序数组的长度
  while(len < nums.length) {
    for(int i = 0; i < nums.length; i += len * 2) {
      sortMergeIterationHelper(nums, i, len);
    }
    len *= 2;  // 每次将排序数组的长度*2
  }
}
/**
 * 辅助函数
 * @param nums  原数组
 * @param start 从start位置开始
 * @param len  本次合并的数组长度
 */
public void sortMergeIterationHelper(int[] nums, int start, int len) {
  int[] tem = new int[len * 2];
  int i = start;
  int j = start + len;
  int k = 0;
  while(i < start + len && (j < start + len + len && j < nums.length)) {
    tem[k++] = nums[i] < nums[j]? nums[i++] : nums[j++];
  }
  while(i < start + len && i < nums.length) {  // 注意：这里i也可能超出长度
    tem[k++] = nums[i++];
  }
  while(j < start + len + len && j < nums.length) {
    tem[k++] = nums[j++];
  }
  int right = start + len + len;
  int index = 0;
  while(start < nums.length && start < right) {
    nums[start++] = tem[index++];
  }
}

归并排序的时间复杂度为O(n*log2n),空间复杂度为O(n)

归并排序是一种稳定的排序方法。

参考：

https://blog.csdn.net/y999666...

专线服务私有云 java归并排序归并排序二路归并排序归并排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69663.html

JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

zhou_you 2019-08-16 10:34 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

caoym 2019-07-31 10:56 评论0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,系列之归并排序

摘要：常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语，或，是创建在归并操作上的一种有效的排序算法，效率为。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

microcosm1994 2019-08-20 16:30 评论0 收藏0
归并排序 - Algorithms, Part I, week 3 MERGESORTS

摘要：两个单元素数组的合并实际就是对这两个数进行了排序，即变为，同样再对后一组的两个数归并排序，即变为，再将两单元数组归并成四单元数组即和归并为。前言本周讲解两个50多年前发明，但今天仍然很重要的经典算法 (归并排序和快速排序) 之一 -- 归并排序，几乎每个软件系统中都可以找到其中一个或两个的实现，并研究这些经典方法的新变革。我们的涉及范围从数学模型中解释为什么这些方法有效到使这些算法...

Jokcy 2019-08-19 11:35 评论0 收藏0
java实现归并排序

摘要：归并排序是一种十分优秀的排序方法，在一开始学习的时候可能会对它的实现思路有点难以理解，不过当你想通了之后就会发现这种方法的绝妙之处。归并排序是一种十分优秀的排序方法，在一开始学习的时候可能会对它的实现思路有点难以理解，不过当你想通了之后就会发现这种方法的绝妙之处。 showImg(https://segmentfault.com/img/bVbctoS?w=941&h=560);sh...

silvertheo 2019-08-16 12:32 评论0 收藏0