Boil's Blog HomeArchivesTagsCategories
递归第三讲
Word count: 1.5k|Reading time: 8 min

合并排序(homework)

题目大意

（采用下列方法之一）实现合并排序，使用PPT上数据
递归
消除递归
自然合并排序

实现思路

在递归实现方法中，首先是类似二分的递归向下拆分，在合并的时候主要是要注意指针的临界问题。

在非递归中，省去了拆这一步，直接每次对步长乘2，达到类似的合并效果，但是需要考虑边界问题

在自然合并当中，是对原本序列中有序的部分加以利用，减少复杂度。这里在处理时候的关键在于记录原本有序区间的起始位置和结束位置，把这些区段看成一个元素进行处理即可，其余的与前面的没什么区别

实现细节

实现细节如上

实现代码

递归

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
//
//  Third homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Topic: MergeSort using recursion algorithm
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/18.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

template<class Type>
void M_S(Type a[], int l, int r)
{
    if (l==r)
        return;
    int mid = (l+r)/2;
    M_S(a,l,mid);
    M_S(a,mid+1,r);
    int b[10010];
    for(int p1=l, p2 = mid+1,pj=l;pj<=r;pj++)
    {
        if (p1>mid)
        {
            b[pj] = a[p2++];
            continue;
        }
        if (p2>r)
        {
            b[pj] = a[p1++];
            continue;
        }
        if (a[p1]<=a[p2])
            b[pj] = a[p1++];
        else b[pj] = a[p2++];
    }
    for (int i=l;i<=r;i++)
        a[i] = b[i];
    return;
}
int main()
{
    int n;
    cin >> n;
    int list[10010];
    for (int i=0;i<n;i++)
        cin >> list[i];
    M_S(list, 0, n-1);
    for (int i=0;i<n;i++)
        cout << list[i] << " ";
    cout << endl;
}

非递归

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
//
//  Third homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Topic: MergeSort without recursion algorithm
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/18.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

template<class Type>
void M_S(Type a[],int n)
{
    int stp =1;
    while(1)
    {
        stp*=2;
        for (int i=0;i<n;i+=stp)
        {
            int l =i, r =min(i+stp-1,n-1);
            int mid = (l+r)/2;
            int b[10010];
            for(int p1=l, p2 = mid+1,pj=l;pj<=r;pj++)
            {
                if (p1>mid)
                {
                    b[pj] = a[p2++];
                    continue;
                }
                if (p2>r)
                {
                    b[pj] = a[p1++];
                    continue;
                }
                if (a[p1]<=a[p2])
                    b[pj] = a[p1++];
                else b[pj] = a[p2++];
            }
            for (int j=l;j<=r;j++)
                a[j] = b[j];
        }
        if (stp>n)
            break;
    }
}
int main()
{
    int n;
    cin >> n;
    int list[10010];
    for (int i=0;i<n;i++)
        cin >> list[i];
    M_S(list,n);
    for (int i=0;i<n;i++)
        cout << list[i] << " ";
    cout << endl;
}

自然排序

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//
//  Third homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Topic: MergeSort using its natural fragments
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/18.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

struct natual_per
{
    int left;
    int right;
};
natual_per se[10010];
template<class Type>
void M_S(Type a[],int n)
{
    int stp =1;
    while(1)
    {
        stp*=2;
        for (int i=1;i<=n;i+=stp)
        {
            int l =se[i].left;
            int r;
            if (i+stp-1>n)
                r = se[n].right;
            else r = se[i+stp-1].right;
            int mid = se[(i+min(i+stp-1,n))/2].right; //core part
            int b[10010];
            for(int p1=l, p2 = se[min((i+min(i+stp-1,n))/2+1,n)].left,pj=l;pj<=r;pj++) //core part
            {
                if (p1>mid)
                {
                    b[pj] = a[p2++];
                    continue;
                }
                if (p2>r)
                {
                    b[pj] = a[p1++];
                    continue;
                }
                if (a[p1]<=a[p2])
                    b[pj] = a[p1++];
                else b[pj] = a[p2++];
            }
            for (int i=l;i<=r;i++)
                a[i] = b[i];
        }
        if (stp>n)
            break;
    }
}
int main()
{
    int n;
    cin >> n;
    int list[10010];
    se[1].left = 0;
    cin >> list[0];
    int tot=1;
    for (int i=1;i<n;i++)
    {
        cin >> list[i];
        if (list[i]<list[i-1])
        {
            se[tot].right = i-1;
            tot++;
            se[tot].left = i;
        }
    }
    se[tot].right = n-1;
    M_S(list,tot);
    for (int i=0;i<n;i++)
        cout << list[i] << " ";
    cout << endl;
}

快速排序(homework)

题目大意

（以下列方式之一）实现快速排序，基准元素可以为：
第一个元素
最后一个元素
中间位置元素
三者取中
随机元素。

实现思路

由于其他几种实现方式会对实现产生很大的麻烦，这里不再舍近求远，只实现以第一个元素为基准元素的方法。思路很经典，取区间第一个为基准，同时在头尾设置low，high指针，分别靠拢，如果high指的比基准小，low覆盖high，low同理

实现细节

见上

实现代码

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
75
76
77
78
79
80
81
82
83
84
85
86
//
//  Third homework of Algorithm Designing and Analyzing in spring semester, 2020
//
//  Topic: QuickSort using thr first element
//
//
//  Author:
//      Yihang Bao
//      2018011890
//  Created by Yihang Bao on 2020/3/18.
//
//
#include <bits/stdc++.h>
#define INF 0x3f3f3f3
#define maxn 100100
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));

template<class Type>
void QS(Type a[],int left, int right)
{
    if (left>=right)
        return;
    Type stan = a[left];
    int low = left, high = right;
    int pos;
    while (1)
    {
        for (int i=high;i>low;i--)
        {
            high = i;
            if (a[i]<stan)
            {
                a[low] = a[i];
                low++;
                break;
            }
            if (low+1==high)
                high--;
        }
        if (low == high)
        {
            a[low] = stan;
            pos = low;
            break;
        }
        for (int i=low;i<high;i++)
        {
            low = i;
            if (a[i]>stan)
            {
                a[high] = a[i];
                high--;
                break;
            }
            if (low+1==high)
                low++;
        }
        if (low == high)
        {
            a[low] = stan;
            pos = low;
            break;
        }
    }
    QS(a,left,pos-1);
    QS(a,pos+1,right);
    return;
}

int main()
{
    int n;
    cin >> n;
    int list[10010];
    for (int i=0;i<n;i++)
        cin >> list[i];
    QS(list, 0, n-1);
    for (int i=0;i<n;i++)
        cout << list[i] << " ";
    cout << endl;
}
Author: YihangBao
Link: https://roarboil.github.io/2020/03/28/cha2-3/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.