算法导论——分治法

山河技术, 程序算法, 软件开发

分治法是十分经典的程序算法应用十分广泛，小到数组排序、查找，大到混沌分形、分布式应用，无处不体现着分而治之的思想。
以一个简单的排序为例，{975， 157， 70， 86， 897， 14， 462， 122}，算法流程如下：

dc_sort

自上而下是算法的递归过程，自下而上是数据的排序过程；
由于算法比较简单就不详细说了，直接上代码：

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
92

/************************************************************************
 * Copyright (c) 2017 dongzhichao@anotherside.cn
 * All rights reserved.
 * @Filedc_sort.cpp
 * @briefdivide & conquer algorithm
 * @version1.0.0
 * @AuthorZhiChao Dong
 * @dateSat. 14 Jan 2017
 ************************************************************************/
#include <string.h>
#include <assert.h>
 
/*
 * @brief merge a and b to c in a sequence
 * @param a array 'a'
 * @param len1 lentgh of array 'a'
 * @param b array 'b'
 * @param len2 lentgh of array 'b'
 * @param c array 'c'
 * @return 0: OK; others: failed
 */
static int _merge(int *a, int len1, int *b, int len2, int *c)
{
    int i, j, k;
 
    assert(a != NULL && b != NULL && c != NULL);
    assert(len1 > 0);
    assert(len2 > 0);
 
    i = j = k = 0;
    while(i < len1 && j < len2){
        if(a[i] <= b[j]){
            c[k++] = a[i++];
        }else{
            c[k++] = b[j++];
        }
    }
    while(i<len1){
        c[k++] = a[i++];
    }
    while(j<len2){
        c[k++] = b[j++];
    }
    return 0;
}
 
/*
 * @brief recursive function of divide & conquer algorithm
 * @param in array needs to be sorted
 * @param len lentgh of array 'in'
 * @param out temporary array
 * @return 0: OK; others: failed
 */
static int _dc_sort(int *in, int len, int *out)
{
    int *pa, *pb, *pc;
    int len1, len2;
    assert(in != NULL && out != NULL);
    assert(len > 0);
 
    if(len <= 1)
        return 0;
    pa = in;
    pb = (in[len/2]);
    pc = out;
    len1 = len/2;
    len2 = len - len/2;
    _dc_sort(pa, len1, out);
    _dc_sort(pb, len2, out);
    _merge(pa, len1, pb, len2, out);
    memcpy((char*)in, (char*)out, len*sizeof(int));
    return 0;
}
 
/*
 * @brief divide & conquer algorithm
 * @param in array needs to be sorted
 * @param len lentgh of array 'in'
 * @return 0: OK; others: failed
 */
int dc_sort(int *in, int len)
{
    int *out;
    assert(in != NULL);
    assert(len > 0);
 
    out = new int[len];
    _dc_sort(in, len, out);
    delete [] out;
 
    return 0;
}

发表评论