我的算法日记(1)---2017/1/24

发表于

早就在知乎上听说了《算法导论》的威名，也因为学编程以来大多写的都是工程代码，算法方面接触的太少了，但是算法又是程序员的内功，又是面试必考的一个环节，所以我这个寒假开始准备开始啃《算法导论》。这个系列的博客也权当是一种笔记吧。

算法的正确性

算法的正确性我是第一次听说，之前在学校上数据结构课时老师也没讲过（讲过才奇怪了）。

算法的正确性是由循环不定式来证明的：

Initialization: It is true prior to the first iteration of the loop.

Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.

Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

总结来说就是，由于算法一般会牵扯到循环，那么就要验证这个循环的正确性，在进入这个循环之前，你得是正确的，也就是说在某种条件下，不进行循环，算法也能得出正确的解。进入循环后，在循环过程是正确的，也就是说你这个循环要一次比一次更加接近解，而不是远离解。循环要能正确终止，不能是无限循环，而且退出要是有意义的，能提供有用的性质。

分治法

分治法的思想就是将原问题分解位几个规模较小但类似的问题，将子问题再进行分解知道足够简单解，然后合并解，建立原方程的解。分治模式有三个基本步骤：

  1. 分解。
  2. 解决。
  3. 合并。

归并排序

归并排序就是运用了一个分治递归的思想。

  1. 分解。将原数组通过不停的调用一个函数，将自身一分为二。直到不能再分为止。
  2. 解决。用一个合并函数将两个有序数组合并。最开始是两个数组各只有一个数字。其排序方法可用两堆扑克牌想象。想象左右两堆扑克牌有序，第一次比较左右牌堆顶谁的数小，就把它移到中间牌堆去，第二次，第三次重复比较。。。。。直至比较完或有一个牌堆放完，直接将另一个牌堆的剩余牌依次放置中间牌堆。
  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
#include <iostream>
#include <iomanip>
using namespace std;
void Merge_Sort(int *A, int p, int r);
void Merge(int *A, int p, int q, int r);
int main()
{
    int A[8] = {8, 7, 6, 5, 4, 3, 2, 1};

    Merge_Sort(A, 0, 7);
    for (int i = 0; i < 8; i++)
    {
        cout << A[i] << " ";
    }
    return 0;
}

void Merge_Sort(int *A, int p, int r)
{
    if (p < r)
    {
        int q = (p + r) / 2;
        Merge_Sort(A, p, q);
        Merge_Sort(A, q + 1, r);
        Merge(A, p, q, r);
    }
}

void Merge(int *A, int p, int q, int r)
{
    int n1 = q - p + 1;
    int n2 = r - q;
    int L[n1 + 1];
    int R[n2 + 1];
    for (int i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    for (int i = 0; i < n2; i++)
    {
        R[i] = A[q + i + 1];
    }
    L[n1] = 100;
    R[n2] = 100;
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        } else
        {
            A[k] = R[j];
            j++;
        }
    }
}

注意这里使用了哨兵法避免每次都判断数组是否已用完。哨兵的值应该待排数组的任何一个数都大。（实际使用绝不可能是100，这里只是为了方便）

二分查找

二分查找是指一个有序数组，每次都把这个数组的中间下标值与待查数比较，若相同则返回，若待查数更大（设该有序数组为升序），则将中间下标设为start下标，end下标不变，重新计算新的中间下标与待查数比较。重复此过程。

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
#include <iostream>
#include <iomanip>
using namespace std;
int binary_find(int *num, int key, int start, int end);
int main()
{
    int num[7] = {1, 2, 3, 4, 5, 6, 7};
    int a;
    cin >> a;
    cout<<"in NO "<<binary_find(num,a,0,6)+1<<endl;
    return 0;
}
int binary_find(int *num, int key,int start,int end)
{
    if (start > end)
    {
        return -2;
    }
    int mid = (start + end) / 2;
    if(key>num[mid])
    {
        binary_find(num, key, mid+1, end);
    } else if (key < num[mid])
    {
        binary_find(num, key, start, mid-1);
    } else if(key==num[mid])
    {
        return mid;
    }
}

如果start下标都比end下标大了，这就说明没有找到，返回一个无意义的值或者返回false就行了。

题目：假设A[1…n]是一个有n个不同数的数组。若i < j且A[i] > A[j],则称其为一个逆序对。 给出一个确定在n个元素的任何排列中逆序对数量的算法，最坏情况需要θ（nlogn）的时间。

这道题通过修改归并排序的代码就可以完成。考虑到排序的过程有两种情况，一是待排数组本来就有序，这种情况就不存在逆序对。二是待排数组无序，这就存在逆序对。那我们所要做的就是将需要进行排序操作的下标记下来。

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
#include <iostream>
#include <iomanip>
using namespace std;
int Merge_Sort(int *A, int p, int r);
int Merge(int *A, int p, int q, int r);
int main()
{
    int A[8] = {7, 8, 6, 5, 4, 3, 2, 1};
    cout<<Merge_Sort(A, 0, 7);
    return 0;
}

int Merge_Sort(int *A, int p, int r)
{

    if (p < r)
    {
        int inversion = 0;
        int q = (p + r) / 2;
        inversion+=Merge_Sort(A, p, q);
        inversion+=Merge_Sort(A, q + 1, r);
        inversion+=Merge(A, p, q, r);
        return inversion;
    } else
    {
        return 0;
    }
}

int Merge(int *A, int p, int q, int r)
{
    int inversion = 0;
    int n1 = q - p + 1;
    int n2 = r - q;
    int L[n1 + 1];
    int R[n2 + 1];
    for (int i = 0; i < n1; i++)
    {
        L[i] = A[p + i];
    }
    for (int i = 0; i < n2; i++)
    {
        R[i] = A[q + i + 1];
    }
    L[n1] = 100;
    R[n2] = 100;
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; k++)
    {
        if (L[i] <= R[j])
        {
            A[k] = L[i];
            i++;
        } else
        {
            A[k] = R[j];
            j++;
            inversion += n1 - i;
        }
    }
    return inversion;
}

我们设左牌堆（即左边的数组）为较小堆，右边为较大堆。代码中最为关键的一行是

inversion += n1 - i; 为什么呢？因为当我们要将右边的牌放到中间（即排序后的数组）去时，右边的这张牌比左边牌堆的所有牌都大而右边的这张牌与左边所有牌都构成一对逆序对， n1 - i 就是计算左边一共有多少少张牌的。

由于初学算法，以上全是我的个人理解，代码中的不足错误之处还请各位大牛批评指出。