科技: 人物 企业 技术 IT业 TMT
科普: 自然 科学 科幻 宇宙 科学家
通信: 历史 技术 手机 词典 3G馆
索引: 分类 推荐 专题 热点 排行榜
互联网: 广告 营销 政务 游戏 google
新媒体: 社交 博客 学者 人物 传播学
新思想: 网站 新书 新知 新词 思想家
图书馆: 文化 商业 管理 经济 期刊
网络文化: 社会 红人 黑客 治理 亚文化
创业百科: VC 词典 指南 案例 创业史
前沿科技: 清洁 绿色 纳米 生物 环保
知识产权: 盗版 共享 学人 法规 著作
用户名: 密码: 注册 忘记密码?
    创建新词条
科技百科
  • 人气指数: 4396 次
  • 编辑次数: 1 次 历史版本
  • 更新时间: 2009-03-18
admin
admin
发短消息
相关词条
数学
数学
数论
数论
工业设计
工业设计
智慧产业
智慧产业
符号位
符号位
算法设计与分析
算法设计与分析
银行家算法
银行家算法
比例计算法
比例计算法
关键路径
关键路径
先来先服务
先来先服务
推荐词条
希拉里二度竞选
希拉里二度竞选
《互联网百科系列》
《互联网百科系列》
《黑客百科》
《黑客百科》
《网络舆情百科》
《网络舆情百科》
《网络治理百科》
《网络治理百科》
《硅谷百科》
《硅谷百科》
2017年特斯拉
2017年特斯拉
MIT黑客全纪录
MIT黑客全纪录
桑达尔·皮查伊
桑达尔·皮查伊
阿里双十一成交额
阿里双十一成交额
最新词条

热门标签

微博侠 数字营销2011年度总结 政务微博元年 2011微博十大事件 美国十大创业孵化器 盘点美国导师型创业孵化器 盘点导师型创业孵化器 TechStars 智能电视大战前夜 竞争型国企 公益型国企 2011央视经济年度人物 Rhianna Pratchett 莱恩娜·普莱契 Zynga与Facebook关系 Zynga盈利危机 2010年手机社交游戏行业分析报告 游戏奖励 主流手机游戏公司运营表现 主流手机游戏公司运营对比数据 创建游戏原型 正反馈现象 易用性设计增强游戏体验 易用性设计 《The Sims Social》社交亮 心理生理学与游戏 Kixeye Storm8 Storm8公司 女性玩家营销策略 休闲游戏的创新性 游戏运营的数据分析 社交游戏分析学常见术语 游戏运营数据解析 iPad风行美国校园 iPad终结传统教科书 游戏平衡性 成长类型及情感元素 鸿蒙国际 云骗钱 2011年政务微博报告 《2011年政务微博报告》 方正产业图谱 方正改制考 通信企业属公益型国企 善用玩家作弊行为 手机游戏传播 每用户平均收入 ARPU值 ARPU 游戏授权三面观 游戏设计所运用的化学原理 iOS应用人性化界面设计原则 硬核游戏 硬核社交游戏 生物测量法研究玩家 全球移动用户 用户研究三部曲 Tagged转型故事 Tagged Instagram火爆的3大原因 全球第四大社交网络Badoo Badoo 2011年最迅猛的20大创业公司 病毒式传播功能支持的游戏设计 病毒式传播功能 美国社交游戏虚拟商品收益 Flipboard改变阅读 盘点10大最难iPhone游戏 移动应用设计7大主流趋势 成功的设计文件十个要点 游戏设计文件 应用内置付费功能 内置付费功能 IAP功能 IAP IAP模式 游戏易用性测试 生理心理游戏评估 游戏化游戏 全美社交游戏规模 美国社交游戏市场 全球平板电脑出货量 Facebook虚拟商品收益 Facebook全球广告营收 Facebook广告营收 失败游戏设计的数宗罪名 休闲游戏设计要点 玩游戏可提高认知能力 玩游戏与认知能力 全球游戏广告 独立开发者提高工作效率的100个要点 Facebook亚洲用户 免费游戏的10种创收模式 人类大脑可下载 2012年最值得期待的20位硅谷企业家 做空中概股的幕后黑手 做空中概股幕后黑手 苹果2013营收 Playfish社交游戏架构

 

目录

归并排序编辑本段回目录

并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

归并操作

归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。

算法描述

并操作的工作原理如下:
申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

定两个指针,最初位置为别为两个已经排序序列的起始位置
比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

示例代码

下示例代码实现了归并操作。array【】是元素序列,其中从索引p开始到q位置,按照升序排列,同时,从(q+1)到r也已经按照升序排列,merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。/**

* 0 <= p <= q < r, subarray array【p..q】 and array【q+1..r】 are already sorted.

* the merge() function merges the two sub-arrays into one sorted array.

*/

static void merge(int array【】, int p, int q, int r)

{

int i,k;

int begin1,end1,begin2,end2;

int* temp = (int*)malloc((r-p)*sizeof(int));

begin1= p;     end1 = q;

begin2 = q+1;  end2 = r;

k = 0;

while((begin1 <= end1)&&( begin2 <= end2))

{

if(array【begin1】<array【begin2】)

{

temp【k】 = array【begin1】;  begin1++;

}

else

{

temp【k】 = array【begin2】;  begin2++;

}

k++;               

}

while(begin1<end1)

{

temp【k++】 = array【begin1++】;

}

while(begin2<end2)

{

temp【k++】 = array【begin2++】;

}

for (i = 0; i < (r - p); i++)

array【p+i】 = temp;

free(temp);

}

归并排序

归并排序具体工作原理如下(假设序列共有n个元素):

将序列每相邻两个数字进行归并操作(merge),形成floor(n/2)个序列,排序后每个序列包含两个元素

将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素

重复步骤2,直到所有元素排序完毕

示例代码

示例代码为C语言,输入参数中,需要排序的数组为array【】,起始索引为first,终止索引为last。调用完成后,array【】中从first到last处于升序排列。

void merge_sort(int array【】, unsigned int first, unsigned int last)

{

int mid = 0;

if(first<last)

{

mid = (first+last)/2;

merge_sort(array, first, mid);

merge_sort(array, mid+1,last);

merge(array,first,mid,last);

}

}

算法复杂度

比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。归并算法的空间复杂度为:Θ (n)

 

相关他们编辑本段回目录

→如果您认为本词条还有待完善,请 编辑词条

词条内容仅供参考,如果您需要解决具体问题
(尤其在法律、医学等领域),建议您咨询相关领域专业人士。
0

标签: 归并排序

收藏到: Favorites  

同义词: 暂无同义词

关于本词条的评论 (共0条)发表评论>>

对词条发表评论

评论长度最大为200个字符。