个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
27
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现的归并排序算法详解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文实例讲述了C++实现的归并排序算法。分享给大家供大家参考，具体如下:
归并排序 。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法。 该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列； 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并.
归并过程 。
1、比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到temp[k]中，并令i和k分别加上1； 2、否则将第二个有序表中的元素a[j]复制到temp[k]中，并令j和k分别加上1. 3、如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元.
归并排序的算法我们通常用递归实现，先把待排序区间[first, last]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[first,last].
归并操作的工作原理 。
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置 第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针超出序列尾，将另一序列剩下的所有元素直接复制到合并序列尾.
算法复杂度 。
时间复杂度为O(nlogn) 这是该算法中最好、最坏和平均的时间性能。 空间复杂度为 O(n) 比较操作的次数介于(nlogn) / 2和nlogn - n + 1。 赋值操作的次数是(2nlogn)。 归并排序比较占用内存，但却是一种效率高且稳定的算法.
算法C++代码 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
//合并两个序列
void
mergeArray(
int
arr[],
int
first,
int
mid,
int
last,
int
temp[])
{
int
i = first;
int
j = mid + 1;
int
m = mid ;
int
n = last;
int
k = 0;
while
(i <= m && j<=n)
{
if
(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while
(i <= m)
temp[k++] = arr[i++];
while
(j <= n)
temp[k++] = arr[j++];
for
(i = 0; i < k; i++)
arr[first + i] = temp[i];
}
void
mySort(
int
arr[],
int
first,
int
last,
int
temp[])
{
if
(first < last)
{
int
mid = (first + last) / 2;
mySort(arr, first, mid, temp);
mySort(arr, mid+1, last, temp);
mergeArray(arr, first, mid, last, temp);
}
}
bool
mergeSort(
int
arr[],
int
len)
{
int
*p =
new
int
[len];
if
(NULL == p)
return
false
;
mySort(arr, 0, len - 1, p);
delete
[] p;
return
true
;
}
|
算法测试 。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <iostream>
using
namespace
std;
//上述归并排序源码
int
main()
{
int
arr[] = { 2, 23, 32, 34, 45, 6, 5, 65, 7, 6, 87, 87, 8, 798, 34, 35, 46, 45, 65, 756, 876, 8, 7, 87, 87, 5, 34, 344, 3, 32 };
int
len =
sizeof
(arr) /
sizeof
(
int
);
mergeSort(arr, len);
for
(
int
i = 0; i < len; i++)
cout << arr[i] <<
" "
;
cout << endl;
system
(
"pause"
);
}
|
运行结果:
|
1
2
|
2 3 5 5 6 6 7 7 8 8 23 32 32 34 34 34 35 45 45 46 65 65 87 87 87 87 344 756 798 876
请按任意键继续. . .
|
希望本文所述对大家C++程序设计有所帮助.
最后此篇关于C++实现的归并排序算法详解的文章就讲到这里了,如果你想了解更多关于C++实现的归并排序算法详解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
27
4
0
本文实例汇总了Java各种排序算法。分享给大家供大家参考，具体如下： 1. 冒泡排序： ?
1.冒泡排序 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。 算法步
前言 平时用惯了高级语言高级工具高级算法，难免对一些基础算法感到生疏。但最基础的排序算法中实则蕴含着相当丰富的优化思维，熟练运用可起到举一反三之功效。 选择排序 选择排序几乎是
我是一名优秀的程序员,十分优秀！