文档章节

排序算法学习之归并排序

xfan001
 xfan001
发布于 2014/05/05 13:33
字数 496
阅读 9
收藏 0

1. 归并排序原理:有长度为n的子序列a[n],可以将其看做n个长度为1的子序列,将相邻子序列两两归并后子序列数量减少一半,再对子序列进行两两归并,数量又减少一般,重复直到得到一个长度为n的子序列

2. 实现归并操作的代码如下:

/*array[s…m]和array[m+1…t]均已各自有序,合并使得array[s…t]有序*/
void Merge(int s, int m, int t, int *array)
{
	int temp[t-s+1];/*设临时数组存放排序后的元素*/
	int i=s, j=m+1, k=0;
	while(i<=m && j<=t)
	{
		if(array[i] < array[j])
			temp[k++] = array[i++];
		else
			temp[k++] = array[j++];
	}
	while(i<=m)
		temp[k++] = array[i++];
	while(j<=t)
		temp[k++] = array[j++];

	for(i=s, k=0; i<=t && k<=t-s; i++, k++)    /*将临时数组里的元素复制到原数组*/
	{
		array[i] = temp[k];
	}
}

3. 递归调用代码如下:

void MSort (int s, int t, int *array)	/*递归调用*/
{
	if(s == t)
		return ;
	int m = (s+t)/2;    /*设置中间数*/
	MSort(s, m, array);    /*左边序列有序*/
	MSort(m+1, t, array);    /*右边序列有序*/
	Merge(s, m, t, array);    /*将左右有序序列归并*/
}
void MergeSort1(int n, int *array)
{
	MSort(0, n-1, array);
}

4. 归并排序非递归调用的实现

    由于大量引入递归造成时间和空间上性能的损耗,所以我们考虑引入迭代来代替递归,效率必然要高于递归,如下:

void MergeSort2(int n, int *array)
{
	int k, i;
	for (k=1; 2*k<n; k *= 2)	/*设置每段待归并的有序序列的长度:1,2,4,8,16……*/
	{
		for (i=0; i+k-1<n; i += 2*k)/*考虑待归并的左右两段序列,[i+k-1]是左序列末尾元素下标*/
		{			    /*[end=i+2*k-1]是右序列末尾元素下标,end不应该超过n-1*/
			int end=i+2*k-1;
			if(end > n-1)
				end = n-1;
			Merge(i, i+k-1, end, array);
		}
	}
}


© 著作权归作者所有

xfan001
粉丝 1
博文 6
码字总数 3062
作品 0
武汉
私信 提问
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

1. 前言 算法为王。 想学好前端,先练好内功,只有内功深厚者,前端之路才会走得更远。 笔者写的 JavaScript 数据结构与算法之美 系列用的语言是 JavaScript ,旨在入门数据结构与算法和方便...

天明夜尽
07/24
0
0
六种排序算法的JavaScript实现以及总结

最近几天在系统的复习排序算法,之前都没有系统性的学习过,也没有留下过什么笔记,所以很快就忘了,这次好好地学习一下。 首先说明为了减少限制,以下代码通通运行于Node V8引擎而非浏览器,...

DM.Zhong
2018/05/24
0
0
归并排序与快速排序的简明实现及对比

前言 归并排序与快速排序是两种有实际应用的排序算法,它们有一些共同的特点,整体思路上也比较相近。本文会从更简单的一些排序算法开始,过渡到归并排序和快速排序的实现,并对它们做一些简...

天方夜
2018/10/30
0
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
算法基础:五大排序算法Python实战教程

本文为 AI 研习社编译的技术博客,原标题 : A tour of the top 5 sorting algorithms with Python code 作者 | George Seif 翻译 | 邓普斯•杰弗 校对 | shunshun 整理 | 菠萝妹 原文链接:...

雷锋字幕组
01/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mysql概览

学习知识,首先要有一个总体的认识。以下为mysql概览 1-架构图 2-Detail csdn |简书 | 头条 | SegmentFault 思否 | 掘金 | 开源中国 |

程序员深夜写bug
今天
9
0
golang微服务框架go-micro 入门笔记2.2 micro工具之微应用利器micro web

micro web micro 功能非常强大,本文将详细阐述micro web 命令行的功能 阅读本文前你可能需要进行如下知识储备 golang分布式微服务框架go-micro 入门笔记1:搭建go-micro环境, golang微服务框架...

非正式解决方案
今天
6
0
前端——使用base64编码在页面嵌入图片

因为页面中插入一个图片都要写明图片的路径——相对路径或者绝对路径。而除了具体的网站图片的图片地址,如果是在自己电脑文件夹里的图片,当我们的HTML文件在别人电脑上打开的时候图片则由于...

被毒打的程序猿
今天
8
0
Flutter 系列之Dart语言概述

Dart语言与其他语言究竟有什么不同呢?在已有的编程语言经验的基础上,我们该如何快速上手呢?本篇文章从编程语言中最重要的组成部分,也就是基础语法与类型变量出发,一起来学习Dart吧 一、...

過愙
今天
5
0
rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部