搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

MergeSort(归并排序)原理及C++代码实现

[复制链接]
查看: 52|回复: 0

1万

主题

1万

帖子

3万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
32619
发表于 2020-1-15 03:13 | 显示全部楼层 |阅读模式
合并排序操纵分治计谋举行排序。道理以下
分化:分化待排的n个元素的序列成个具n/2个元素的两个子序列。
打点:操纵合并排序递归地排序两个子序列。
合并:合并两个已排序的子序列以发生已排序的答案。
合并排序的时候复杂度是θ(nlgn)。
合并排序是安定排序之一。
合并排序不是原址排序,在合并阶段需要申请额外的数组空间。
代码以下:(仅供参考)
  1. 1 void MergeSort(int * const begin, int * const end) {2     if (begin + 1 >= end)3         return ;4     int m = (end - begin) / 2;5     MergeSort(begin, begin + m);6     MergeSort(begin + m, end);7     Merge(begin, begin + m, end);8 }
复制代码
[code] 1 //倒霉用尖兵的版本,需判定鸿沟条件 2 void Merge(int * const first, int * const mid, int * const last) { 3     vector left(first, mid); 4     vector right(mid, last); 5  6     int i = 0, j = 0, k = 0; 7     while (i != left.size() && j != right.size()) { 8         if (left
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 全椒百姓网-全椒知名**,发布及时新鲜的全椒新闻资讯 生活信息 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表