新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
稍有积蓄, 积分 339, 距离下一级还需 161 积分
论坛徽章:1
本帖最后由 glq2000 于
20:42 编辑
归并排序在平均情况和最坏情况下的时间复杂度都是O(nlogn)，但这个是怎么算出来的呢？ 希望懂的的同学 说下拉 十分感谢！！！！
下面是我写的归并排序的代码，用递归实现的，主要函数是MergeSort(), 代码如下(若感觉下列代码格式不够良好，：
* =====================================================================================
*& && & Filename:&&MergeSort.cpp
*& & Description:&&MergeSort,归并排序,用递归实现
*& && &&&Version:&&1.0
*& && &&&Created:&&日 14时47分14秒
*& && & Revision:&&none
*& && & Compiler:&&gcc
*& && && &Author:&&glq2000 (),
*& && &&&Company:&&HUE ISRC
* =====================================================================================
*/
#include &iostream&
#define N 11
int array[N] = { 4, 67, 456, 23, 1, 78, 26, 222, 34, 432, 12 }; //待排序数组
int other[N]; //辅助空间,用以暂存已经排序的数组元素
void Swap(int &a, int &b)
{
& & int tmp =
& & a =
& & b =
}
/* array 待排序数组
* begin 数组开始的下标
*& &end 数组最后一个元素的下标
*/
void MergeSort(int *array, int begin, int end)
{
& & if(end-begin+1 & 2) //当数组元素个数大于2时,需要继续向下划分(递归)
& & {
& && &&&MergeSort(array, begin, (end+begin)/2);
& && &&&MergeSort(array, (end+begin)/2+1, end);
& && &&&//合并已排序好的两部分(begin,(end+begin)/2) 和 ((end+bigin)/2+1,end)
& && &&&int i = begin, j = (end+begin)/2+1, k=
& && &&&while(i&=(begin+end)/2 && j&=end)
& && &&&{//比较两个下标i和j所代表的元素,选择相对小的元素放入到辅助空间other数组中,并移动下标到下一位置
& && && && &if(array[i] & array[j])
& && && && && & other[k++] = array[i++];
& && && && &else
& && && && && & other[k++] = array[j++];
& && &&&}
& && &&&while(i &= (begin+end)/2)& &//将剩余元素拷贝至other数组
& && && && &other[k++] = array[i++];
& && &&&while(j &= end)& && && && & //将剩余元素拷贝至other数组
& && && && &other[k++] = array[j++];
& && &&&for(k= k&= ++k)& &//将排序好的序列拷贝回数组array中
& && && && &array[k] = other[k];
& & }
& & else //当数组元素个数为2或1时,直接排序
& && &&&if(array[end] & array[begin])&&Swap(array[end], array[begin]);
}
void Output(int *array, int n)
{
& & for(int i=0; i&n; ++i)
& && &&&cout&&array[i]&&& &;
& & cout&&
}
int main()
{
& & MergeSort(array, 0, N-1);
& & Output(array, N);
& & return 0;
}
复制代码格式良好的代码也可以
我明白堆排序的复杂度是O(nlogn)，因为对于数组a[n]中的每一个元素都要到那个二叉完全树中去“筛选”一遍，所以 是 n*logn的复杂度，但归并排序的这个O（nlogn）该如何理解呢？
&&多谢！！！
&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp
丰衣足食, 积分 524, 距离下一级还需 476 积分
论坛徽章:0
算法同你发的另一个帖子：
丰衣足食, 积分 524, 距离下一级还需 476 积分
论坛徽章:0
两者的公式都是一样的，归并是线性的，也就是那个n，然后分治时候是T(n/2)，所以公式是一样的
T(n)=2T(n/2)+n
稍有积蓄, 积分 339, 距离下一级还需 161 积分
论坛徽章:1
daybreakcx
& & “两者的公式都是一样的，归并是线性的，也就是那个n，然后分治时候是T(n/2)，所以公式是一样的
T(n)=2T(n/2)+n”
谢谢，明白了！！！我没有想到公式是一样的这一点。。。。。。。。。。。。。。。。哎。。。。。。。。
多谢指点，这下心里舒服多了，之前一直不明白归并为何是O(nlogn), 数学没学好好吃亏。。。。
多谢！！！！！推荐这篇日记的豆列
······问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
bool Increment(char* number)
bool isOverflow =
int nTakeOver=0;
int nLength = strlen(number);
for(int i = nLength - 1;i &= 0; i--)
int nSum = number[i] - '0' + nTakeO
if(i == nLength - 1)
if(nSum &= 10)
if(i == 0)
isOverflow =
nSum -=10;
nTakeOver = 1;
number[i] = '0' + nS
number[i] = '0' + nS
return isO
同步到新浪微博
分享到微博？
你好！看起来你挺喜欢这个内容，但是你还没有注册帐号。 当你创建了帐号，我们能准确地追踪你关注的问题，在有新答案或内容的时候收到网页和邮件通知。还能直接向作者咨询更多细节。如果上面的内容有帮助，记得点赞 (????)? 表示感谢。
明天提醒我
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：
扫扫下载 App}