• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

Merge Sort

AOJ 站点默认 8个月前 (04-11) 383次浏览 已收录 5个评论
文章目录[隐藏]

Question

Write a program of a Merge Sort algorithm implemented by the following pseudocode. You should also report the number of comparisons in the Merge function.

Input
In the first line n is given. In the second line, n integers are given.

Output
In the first line, print the sequence S. Two consequtive elements should be separated by a space character.

In the second line, print the number of comparisons.

Constraints
n ≤ 500000
0 ≤ an element in S ≤ 109
Sample Input 1
10
8 5 9 2 6 3 7 1 10 4
Sample Output 1
1 2 3 4 5 6 7 8 9 10
34

Meaning


实现归并排序,除了输出排序后的数组,下一行输出归并排序在比较过程中的次数

Sloution

归并排序利用了分治的思想,首先先分,给数组全部对半分开,分开后分到不能再分,这时候需要合并,写一个合并函数将其合并

Coding

Summary


归并排序的总体复杂度为0(nlogn)

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:Merge Sort
喜欢 (0)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(5)个小伙伴在吐槽
  1. I think the admin of this website is actually working hard in support of his web site, since here every material is quality based stuff. Valerye Allayne Saidel
    sikis izle2020-11-14 09:32 回复 Windows 10 | Chrome 87.0.4251.0
  2. I am sure this piece of writing has touched all the internet viewers, its really really nice article on building up new website. Benni Mendy Marilin
    erotik2020-11-13 04:33 回复 Windows 10 | Chrome 87.0.4251.0
  3. If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela
    erotik izle2020-11-12 23:12 回复 Windows 10 | Chrome 87.0.4251.0
  4. If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela
    sikis izle2020-11-12 14:29 回复 Windows 10 | Chrome 87.0.4251.0
  5. If you want to use the photo it would also be good to check with the artist beforehand in case it is subject to copyright. Best wishes. Aaren Reggis Sela
    porno2020-11-12 12:12 回复 Windows 10 | Chrome 87.0.4251.0