文档章节

归并排序

memristor
 memristor
发布于 2014/04/11 09:58
字数 607
阅读 70
收藏 1

归并排序采用分治法,是一种稳定的排序,先分段使每一段序列都有序,将已有序的子序列合并,得到完全有序的序列。

    1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。

    2、Conquer: 对这两个子序列分别采用归并排序。

    3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。

时间复杂度:

由于归并的趟数,等于树的高度Logn,每趟归并需要移动记录n次,因此归并排序的时间复杂度为nlogn.

空间复杂度:

从上面的算法可以看出,需要一个辅助空间num2,其长度等于n,所以归并排序的辅助空间为O(n).

稳定性:

归并排序不涉及到交换,因此它是一种稳定的排序算法。 

归并排序是典型的用空间去换取时间,它的时间开销比简单排序要优越,但需要与序列等长的辅助空间。

import java.util.Arrays;

public class MergeSort {
	/**
	 * 归并排序
	 * 简介:将两个(或两个以上)有序表合并成一个新的有序表 即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
	 * 时间复杂度为O(nlogn)
	 * 稳定排序方式
	 * @param nums 待排序数组
	 * @return 输出有序数组
	 */
	public static int[] sort(int[] nums, int low, int high) {
		if (low < high) {
			int mid = (low + high) / 2;
			// 左边
			sort(nums, low, mid);
			// 右边
			sort(nums, mid + 1, high);
			// 左右归并
			merge(nums, low, mid, high);
		}
		return nums;
	}

	public static void merge(int[] nums, int low, int mid, int high) {
		int[] temp = new int[high - low + 1];
		int i = low;// 左指针
		int j = mid + 1;// 右指针
		int k = 0;

		// 把较小的数先移到新数组中
		while (i <= mid && j <= high) {
			if (nums[i] < nums[j]) {
				temp[k++] = nums[i++];
			} else {
				temp[k++] = nums[j++];
			}
		}

		// 把左边剩余的数移入数组
		while (i <= mid) {
			temp[k++] = nums[i++];
		}

		// 把右边边剩余的数移入数组
		while (j <= high) {
			temp[k++] = nums[j++];
		}

		// 把新数组中的数覆盖nums数组
		for (int k2 = 0; k2 < temp.length; k2++) {
			nums[k2 + low] = temp[k2];
		}
	}

	
	// 归并排序的实现
	public static void main(String[] args) {

		int[] nums = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };

		MergeSort.sort(nums, 0, nums.length-1);
		System.out.println(Arrays.toString(nums));
	}
}


© 著作权归作者所有

上一篇: 二分查找
下一篇: 快速排序
memristor
粉丝 45
博文 203
码字总数 176319
作品 0
长沙
程序员
私信 提问
java泛型中使用的排序算法——归并排序及分析

一、引言 我们知道,java中泛型排序使用归并排序或TimSort。归并排序以O(NlogN)最坏时间运行,下面我们分析归并排序过程及分析证明时间复杂度;也会简述为什么java选择归并排序作为泛型的排序...

9龙
04/29
0
0
排序算法之归并排序

一、分治法的思想 把复杂的问题分解,再分解,成为很小的问题,解决这些小问题之后合并,再合并。这就是分治法的思想。 通常分治法是递归的。 二、归并排序 归并排序就是利用分治法,把无序的...

Lubby
2015/10/08
99
0
排序算法(7) -- 归并排序

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/87947485 一、前言 归并排序是建立...

dby_freedom
02/26
0
0
归并排序——“递归+合并”(Java版)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

十一11
2016/04/07
80
0
白话经典算法系列之五 归并排序的实现

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 首先考虑下如何将将二个有序数列合并。这个非常简单,只要从比较二个数...

长平狐
2012/12/10
53
0

没有更多内容

加载失败,请刷新页面

加载更多

DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
今天
3
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
今天
4
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
今天
6
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
今天
5
0
Python机器学习之数据探索可视化库yellowbrick

背景介绍 从学sklearn时,除了算法的坎要过,还得学习matplotlib可视化,对我的实践应用而言,可视化更重要一些,然而matplotlib的易用性和美观性确实不敢恭维。陆续使用过plotly、seaborn,...

yeayee
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部