斯坦福算法课踩坑系列 S01E01

写在正题前

还没开始学算法,数据结构也是半吊子。脑抽在 Coursera 上面跟了这门课,上了几节后听别人说另外一门 Princeton 的讲得更接地气,少了很多数学证明,也多了很多实现细节。总之,已经买了也不能中途弃坑。所以自己打算写个长期系列。

言归正传,这门课主要分为以下四个部分:

  • Divide and Conquer, Sorting and Searching, and Randomized Algorithms.
  • Graph Search, Shortest Paths, and Data Structures.
  • Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming.
  • Shortest Paths Revisited, NP-Complete Problems and What To Do About Them.

目前我上完了第一部分,也就是分治、排序、搜索和随机算法。

第一集先整理这两个部分:归并排序、寻找逆序对。

归并排序(Merge Sort)

一图流,不展开讲
一图流,不展开讲

这个没什么可以记笔记的。顾名思义,归并排序分为两步。
第一,递归的把数组二分;第二,一层一层的把已经排序的两个小数组进行合并。

伪代码大致如下:

1
2
3
4
5
6
7
8
void mergeSort(int a[], int n) {
if (n == 1) return;
mergeSort(a, n / 2);
mergeSort(a + n / 2, n / 2);
merge(a, a + n / 2, n / 2, n - n / 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
#include <stdio.h>
#include <stdlib.h>
void merge(int a[], int b[], int size_a, int size_b, int temp[]) {
int i = 0;
int j = 0;
for (int count = 0; count < size_a + size_b; count++) {
if (a[i] < b[j] && i < size_a || j == size_b)
temp[count] = a[i++];
else if (a[i] >= b[j] && j < size_b || i == size_a)
temp[count] = b[j++];
}
for (int count = 0; count < size_a + size_b; count++) {
a[count] = temp[count];
}
}
void mergeSort(int* a, int n, int* temp) {
if (n == 1) return;
mergeSort(a, n / 2, temp);
mergeSort(a + n / 2, n - n / 2, temp + n / 2);
merge(a, a + n / 2, n / 2, n - n / 2, temp);
}
int main() {
int a[] = {3, 5, 8, 6, 7, 4, 2, 1};
int *temp = (int *)malloc(sizeof(a));
mergeSort(a, 8, temp);
for (int i = 0; i < sizeof(a) / sizeof(int); i++) {
printf("%d ", temp[i]);
}
return 0;
}

寻找逆序对(Counting Inversions)

要求:

Input : array A containing the numbers 1,2,3,..,n in some arbitrary order.

Output : number of inversions = number of pairs(i,j) of array indices with i < j and A[i] > A[j].

分析:要求的逆序对可以分为三种情况。

  • 情况1:i, j都在数组的前半边。
  • 情况2:i, j都在数组的后半边。
  • 情况3:i, j分别位于数组的前、后半边。

对于前两种情况,直接递归即可,然后加上第三种情况的结果即为所求。

伪代码如下:

1
2
3
4
5
6
7
8
count(array A, length n)
if n = 1, return 0;
x = count(half of A, n / 2);
y = count(2nd half of A, n / 2);
z = countSplitInversion(A, n); // Not implemented yet
return x + y + z;

Goal : implement CountSplitInversions in linear (O(n)) time then count will run in O(nlog(n)) time.

寻找 split inversion 的过程和归并排序的合并过程类似。我们不妨看几个例子:

  1. 假如数组中不存在 Split Inversions

    比如:A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    进行分治后,

    1
    2
    A = {0, 1, 2, 3, 4}
    B = {5, 6, 7, 8, 9}

    也就是说,前半个数组中所有的元素都比后半个数组小。对该数组进行归并,使用 i, j 两指针。此时,当 i 走到头时,j 尚未移动。

  2. 假如数组中存在 m 个 Split Inversions

    比如:A = {0, 1, 2, 3, 8, 4, 5, 6, 7, 9}

    进行分治后,

    1
    2
    A = {0, 1, 2, 3, 8}
    B = {4, 5, 6, 7, 9}

    执行归并的过程,i 到终点以后,j 指向7,也就是第4个元素。
    这个数组中有4个逆序对。

规律很显然,当一个指针走到头时,另一个指针的位置就是逆序对的个数。

代码如下:

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
#include <stdio.h>
#include <stdlib.h>
int countSplitInversions(int *a, int *b, int size_a, int size_b, int *temp) {
int i = 0;
int j = 0;
int num = 0;
for (int count = 0; count < size_a + size_b; count++) {
if (a[i] <= b[j] && i != size_a || j == size_b) {
temp[count] = a[i++];
num += j;
} else if(a[i] > b[j] && j != size_b || i == size_a) {
temp[count] = b[j++];
}
}
for (int count = 0; count < size_a + size_b; count++) {
a[count] = temp[count];
}
return num;
}
int countInversions(int *a, int n, int *temp) {
if (n == 1) return 0;
int x = countInversions(a, n / 2, temp);
int y = countInversions(a + n / 2, n - n / 2, temp + n / 2);
int z = countSplitInversions(a, a + n / 2, n / 2, n - n / 2, temp);
return x + y + z;
}
int main() {
int a[] = {1, 5, 6, 4, 10, 2, 11, 22, 8, 7, 9};
int *temp = (int *)malloc(sizeof(a));
int result = countInversions(a, 11, temp);
printf("%d\n", result);
return 0;
}