二路归并排序
基本思想
二路归并排序就是将两个有序子表归并成一个有序表。首先我们得有一个算法用于归并：两个有序表放在同一数组的相邻位置上，arr[left]到arr[center-1]为第一个有序表，arr[center]到arr[right]是第二个有序表。每次从两端中取出一个进行比较，小的先放在一个temp数组，最后将比较剩下的直接放到temp中去，最后将temp又复制回arr。这是“治”。
所谓“分”，就是递归地将前半部分和后半部分的数据各自归并排序即可。
算法分析
每一趟归并的时间复杂度为O(n)，共需要进行⌈log2n⌉趟。对应的算法的时间复杂度为O(nlog2n)。归并排序的空间复杂度O(n)。另外，归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。
二路归并排序的前提是两个序列本身有序。
|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
void Merger(int *arr, int len, int width)
{
int *temp =(int *)malloc(sizeof(int) * (len));
//首先对两路下标分别进行初始化
int l1 = 0;
int h1 = l1 + width - 1;
int l2 = h1 + 1;
int h2 = l2 + width - 1 < len - 1 ? l2 + width - 1 : len - 1;
int temppos = 0;
//判断所在下标位置的值
while (l1 < len && l2 < len)
{
while (l1 <= h1 && l2 <= h2)
{
if (arr[l1] < arr[l2])
{
temp[temppos++] = arr[l1++];
}
else
{
temp[temppos++] = arr[l2++];
}
}
//l1有剩余
while (l1 <= h1)
{
temp[temppos++] = arr[l1++];
}
//l2有剩余
while (l2 <= h2)
{
temp[temppos++] = arr[l2++];
}
//l1 l2向后移动
l1 = h2 + 1;
h1 = (l1 + width - 1) < (len - 1) ? (l1 + width - 1) : (len - 1);
l2 = h1 + 1;
h2 = (l2 + width - 1) < (len - 1) ? (l2 + width - 1) : (len - 1);
}
//奇数归并块 剩下的一个单都块操作
while (l1 <len)
{
temp[temppos++] = arr[l1++];
}
//用temp覆盖arr
for (int i = 0; i < len ; ++i)
{
arr[i] = temp[i];
}
// free(temp);
}
void MergeSort(int *arr, int len)
{
for (int i = 1; i < len; i *= 2)
{
Merger(arr, len, i);
}
}
void show(int *arr, int len)
{
for (int i = 0; i < len; ++i)
{
cout << arr[i] << " ";
}
}
int main()
{
int array[] = { 12, 51, 1, 36, 98, 21, 38, 47 };
int len = sizeof(array) / sizeof(array[0]);
MergeSort(array, len);
show(array, len);
system("pause");
return 0;
}
|
PS:二路合并排序算法
|
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include<iostream>
using namespace std;
class SortableList
{
public:
SortableList(int mSize)
{
maxSize = mSize;
l= new int[maxSize];
n = 0;
}
~SortableList()
{
delete[]l;
}
void Merge(int, int, int);
void MergeSort(int,int);
void Input();
void Output();
private:
int* l;
int maxSize;
int n;
};
void SortableList::Input()
{
cout << "请输入要排序的数：";
for (int i = 0; i <= maxSize - 1; i++)
cin >> l[i];
}
void SortableList::Output()
{
cout << "排序后的数是：";
for (int i = 0; i <= maxSize - 1; i++)
cout << l[i]<<' ';
}
void SortableList::MergeSort(int left,int right)
{
if (left < right)//如果序列长度大于1则划分
{
int mid = (left + right) / 2;
MergeSort(left, mid);//对左序列进行排序
MergeSort(mid + 1, right);//对右序列进行排序
Merge(left, mid, right);//合并
}
}
void SortableList::Merge(int left, int mid, int right)
{
int* temp= new int[right - left + 1];
int i = left, j = mid + 1, k = 0;
while ((i <= mid) && (j <= right))//判断序列是否为空
if (l[i] <= l[j])
temp[k++] = l[i++];
else temp[k++] = l[j++];
while (i <= mid)
temp[k++] = l[i++];//右序列空了左序列依次写入
while (j <= right)
temp[k++] = l[j++];//左序列空了右序列依次写入
for (i = 0, k = left; k <= right;)
l[k++] = temp[i++];//临时在数组temp中的排列好的数据放入数组l
}
int main()
{
int m;
cout << "请输入要排序的数的数目：";
cin >> m;
SortableList a1(m);
a1.Input();
a1.MergeSort(0, m-1);
a1.Output();
}
|
到此这篇关于c++实现二路归并排序的示例代码的文章就介绍到这了,更多相关c++ 二路归并排序内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://blog.csdn.net/qq_21230831/article/details/95733815