归并排序非递归(想得通不写通还是空,懒病要治)

原理

现在有两个数组a, b,都是有序的,要你将他们合并成一个数组,你会怎么做呢,当然不会直接合并再排序了,而是如下操作:

  1. 设两标志指针分别指向a,b的首元素。
  2. 比较当前a,b当前首位元素,选择较小的加入临时数组t,相应的标志指针后移。
  3. 重复2过程,知道a.b任一方已全部加入t,然后到步骤4
  4. 将未完全加入的数组剩余元素全部加入。

这样合并两个数组的时间复杂度是O(len(a) + len(b))
那么联想到归并排序,我们已经能大致猜出来他的排序的流程啦。如下图所示:

没错, 归并排序就是不断的将数组二分,直到元素数为1,然后再合并(如上面说到的合并数组),形成有序的序列,是一个快速且稳定的排序算法

思路

原理很好理解,不做赘述,明白原理后,写出递归的归并排序是很容易的,后面会贴出递归的代码。
今天主要说下非递归的思路。
递归式的思想是先二分再合并的一个流程。而我们非递归时可以直接对它们进行合并,而不必二分(事实上每个元素都在各自下标处,完全可以当作已经二分好了),当然,这里的边界什么的需要自己用循环来规定了。
而且非递归相比递归还有一个特殊的地方,比如下面这个序列

8 3 4 5 7 2 1 3

递归的情况下,不会考虑它们的数值,而是直接进行二分,我们最终会进行4+2+1=7次合并操作。
但我们在非递归下就可以趁机对此改进。比如3 4 5 7,我们完全没有必要去将它们二分,因为它们已经是有序的了,只需要将其与相邻序列串合并就好。
那么我们会将其分为这些序列

8 | 3 4 5 7 | 2 | 1 3

然后将83 4 5 7 合并为 3 4 5 7 8
同理,21 31 2 3
再合并即为

1 2 3 3 4 5 7 8

我们只用了3次合并操作,对比递归已经好了很多。

代码

非递归

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue>

using namespace std;
#define LL long long

const int N = 21;
int d[N];
int t[N];

void func(const pair<int, int> &a, const pair<int, int> &b)
{
int i=0;
for(int sa = a.first, sb = b.first; sa<=a.second || sb<=b.second;)
{
if(sa <= a.second && sb <= b.second)
{
if(d[sa] <= d[sb])
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
else if(sa <= a.second)
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
for(int j=0; j<i; j++)
d[j+a.first] = t[j];
}

void merge_sort(int st, int end)
{
while(1)
{
int l = st;
vector<pair<int, int>> v;
for(int i=st+1; i<=end; i++)
{
if(d[i] < d[i-1])
{
v.push_back(pair<int, int>(l, i-1));
l = i;
}
}
if(l == st)
break;
v.push_back(pair<int, int>(l, end));
for(int i=1; i<v.size(); i+=2)
func(v[i-1],v[i]);
}
}

int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>d[i];
merge_sort(0, n-1);
for(int i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
return 0;
}

递归

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<queue>

using namespace std;
#define LL long long

const int N = 21;
int d[N];
int t[N];

void func(const pair<int, int> &a, const pair<int, int> &b)
{
int i=0;
for(int sa = a.first, sb = b.first; sa<=a.second || sb<=b.second;)
{
if(sa <= a.second && sb <= b.second)
{
if(d[sa] <= d[sb])
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
else if(sa <= a.second)
t[i++] = d[sa++];
else
t[i++] = d[sb++];
}
for(int j=0; j<i; j++)
d[j+a.first] = t[j];
}
void merge_sort(int st, int ed)
{
if(st >= ed)
return;
int mid = st+(ed-st)/2;
tmerge_sort(st, mid);
tmerge_sort(mid+1, ed);
func(pair<int, int>(st, mid), pair<int, int> (mid+1, ed));
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
cin>>d[i];
merge_sort(0, n-1);
for(int i=0; i<n; i++)
cout<<d[i]<<" ";
cout<<endl;
return 0;
}
如果本文对你有用,可以请作者喝杯茶~
0%