《算法基础》打开算法之门(Algorithms Unlocked) 读书笔记

递归

阶乘函数

  1. n == 0 ? n! = 1
  2. n > 0 ? n! = n * (n - 1) * (n - 2) … 2 * 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    #define __STDC_WANT_LIB_EXT1__ 1
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdarg.h>

    long factory(int);

    int main(int argc, char *argv[])
    {
    int n = 0;
    printf("input a number: ");
    scanf("%d", &n);
    long res = factory(n);
    printf("factory: %ld\n", res);
    return 0;
    }

    long factory(int n) {
    if (n == 0) {
    return 1;
    }
    return n * factory(n - 1);
    }

递归查找

  1. 数组长度计算: sizeof nums / sizeof(int);
  2. 索引变化值保存到 int idx = 0; 将 idx 指针传进去
  3. *pi 先取值在 ++
  4. 找到的条件 nums[i] == x
  5. 未找到的提交 i >= len
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
#include <stdio.h>
#include <stdlib.h>

int recursive_find(int [], int, int, int *);

int main(int argc, char *argv[]) {

int nums[] = {1, 2, 3, 4, 5};
int len = sizeof nums / sizeof(int);

for (int i = 0; i < len; i++) {
printf("%d: %d\n", i, nums[i]);
}

int idx = 0;
int val = 0;
printf("input a num to find: ");
scanf("%d", &val);
int res = recursive_find(nums, len, val, &idx);

printf("found x at %d\n", res);

return 0;
}

int recursive_find(int nums[], int len, int x, int *pi) {

int i = *pi;
if (nums[i] == x) {
return i;
}

// not found
if (i >= len) {
return -1;
}

printf("recursive_find x: %d, i: %d, el: %d\n", x, i, nums[i]);
(*pi)++;

return recursive_find(nums, len, x, pi);
}

查找

二分查找法

初级版

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
#include <stdio.h>
#include <unistd.h>

int binary_search(int [], int, int);

int main(int argc, char *argv[]) {

int nums[5] = {0};

for (int i = 0; i < 5; i++) {
nums[i] = 2 * i + 1;
}

int len = sizeof(nums) / sizeof(int);
int n = 0;

while(1) {
printf("input value to find: ");
scanf("%d", &n);
binary_search(nums, n, len);
}

return 0;
}

int binary_search(int nums[], int target, int len) {
int start = 0;
int end = len - 1;
int mid = len / 2;
int res = 0;
int i = 0;

printf("%d,%d,%d\n", target, nums[start], nums[end]);
if (target < nums[start] || target > nums[end]) {
printf("beyond, not found.\n");
return -1;
}

while (end != start && target != nums[mid]) {
printf("[%d] len: %d, start: %d, mid: %d, res: %d, end: %d\n", i++, len, start, mid, nums[mid], end);
if (target < nums[mid]) {
end = mid;
mid = (mid - start) / 2 + start;
} else if (target > nums[mid]) {
start = mid;
mid = (end - mid) / 2 + mid;
}

// 剩下最后两个值了
if (mid == start || mid == end) {
if (target == start) {
mid = start;
} else if (target == end) {
mid = end;
}
start = end;
}

sleep(1);
}

if (nums[mid] == target) {
printf("found %d at %d\n", nums[mid], mid);
} else {
printf("not found %d\n", target);
}
printf("----------------------------------\n");

return nums[mid];
}
  1. 非法值判断,超出数组值得范围了不用进入循环查找了
  2. 结束条件:找到值了 targetnums[mid] 相等 , 循环结束了 start == end
  3. 剩下最后两个值得临界点: mid, start 相等或 midend 相等。

优化版

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

int binary_search(int nums[], int target, int len) {
int start = 0;
int end = len - 1;
int mid = len / 2;
int res = 0;
int i = 0;

if (target < nums[start] || target > nums[end]) {
return -1;
}

while (start <= end) {
i++;
mid = (start + end) / 2;

int val = nums[mid];
if (val == target) {
printf("found step: %d\n", i);
return mid;
}

if (target < val) {
end = mid - 1;
} else if (target > val) {
start = mid + 1;
}
}
printf("not found step: %d\n", i);

return -1;
}

优化版原理是排除了中间 nums[mid] 元素,因为这个元素本身已经被比较过了,所以在中间索引发生变化的时候只需要

mid 向前后移动一位即可得到正确的未比较的范围。

这样就省去了 初级版 中的 mid, start, end 之间的互相比较,因为 mid +- 1 之后必然会有一个会碰到 startend 的值。

然后就是在循环体内部如果找到了目标值,直接返回下标即可。

递归版

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

int binary_search(int nums[], int start, int end, int target) {

printf("start[%d] - end[%d]\n", start, end);

// 取中值比较,找到了退出
int mid = (start + end) / 2;
int val = nums[mid];
if (val == target) {
return mid;
}

// 没找到,判断是否循环结束,结束了退出
if (start >= end) {
printf("over not found.\n");
return -1;
}

// 两者都不是,则还可以继续找
if (target < val) {
end = mid - 1;
} else if (target > val) {
start = mid + 1;
}
// 下一次查找
return binary_search(nums, start, end, target);
}

递归版,需要改进下传递进入的参数。

这个时候需要将 start, end 两个变动的索引值保存起来,便下次传入 binary_search 使用,

这里面有三个关键地方:

  1. 找到的条件, nums[mid]target 值相等,表示找到了
  2. 没找到,但是没有更多的元素需要遍历的,这属于最差的情况
  3. 进入下一次递归的准备工作,即改变 start-end 的值,进入下一次循环查找

排序

选择排序

选择排序原理:总以从 i = 0 未排序的元素作为参考,查找后面比它小的元素,找到了就替换,直到数组最后一个元素为止,

如果没找到就将 i + 1 往前推进,查找后面比 i + 1 位置的元素小的,找到替换,如此往复,知道 i + 1 到达

数组末尾,排序结束。

递归示例

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

int select_sort_recursive(int nums[], int count, int *step, int *total) {
int tmp = 0;

if (*step > count - 1) {
return -1;
}

for (int i = *step + 1; i < count; i++) {
int curr = nums[*step];
// 交换
if (nums[i] < curr) {
tmp = curr;
nums[*step] = nums[i];
nums[i] = tmp;
}
(*total)++;
}

(*step)++;

select_sort_recursive(nums, count, step, total);

return 0;
}

上面的程序,需要执行的步骤计算方式:

step: 1 需要循环 count - 1 次,

step: 2 需要循环 count - 2 次,

step: count - 1 需要循环 1 次。

最后得出结论: (n - 1) + (n - 2) + ... + 1 -> (n - 1) * n / 2

例子中数组长度为: 7,即需要执行 6 * 7 / 2 = 21

时间复杂度即为: O(n^2)

双重循环示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int select_sort_for(int nums[], int count) {

int tmp = 0, times = 0;

for (int i = 0; i < count; i++) {
for (int j = i + 1; j < count; j++) {

times++;
if (nums[j] < nums[i]) {
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
}

printf("times: %d\n", times);

return 0;
}

插入排序

通过比较前 n - 1 个元素与 n 的元素值,如果大就往后挪一位,然后继续比较前 n - 2 个值,如此往复,直到找不到

比它大的值为止,最后使用当前的值去填充最后被替换走的那个元素所在为止,一轮排序结束。

n++ 往后如上继续比较,直到超出数组长度,结束排序。

这里关键点在于:

  1. 当前被比较的元素要保存起来(比如:key中)
  2. 与前 n - 1 个元素比较结束的条件有两个,

    • 一个是 n - 1 < 0 了,前面没有元素了,
    • 另一个是前一个元素比 key 值还小

      因为前面的元素总是已经排好序的,只要比它前一个大,那就没必要再与 n - 2 那个更小的去比较了

  3. 一轮比较结束后,不要忘记了将最后一个被挪走的那个值所在的位置赋值为 key。

递增方式

递增的方式是以 i 为自增量参考值, j 总是取 i 后面的值,然后通过比较 A[j] 和 前 i 个值,找出大值

然后与 A[j] 互换位置方式,进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void insert_sort(int nums[], int count, int *step) {

int val = 0;
for (int i = 0; i < count - 1; i++) {
int j = i + 1;
val = nums[j];
while (j > 0 && nums[j - 1] > val) {
nums[j] = nums[j - 1];
nums[j - 1] = val;
sleep(1);
j--;
(*step)++;
print_nums(nums, count, step);
}
}
print_nums(nums, count, step);
}

递减方式

递减方式其实和递增方式原理是一样的,只不过区别在于

递增: i = 0, j = i + 1

递减: i = 1, j = i - 1

其实对比之下是一样的,因为总有一个值在前,一个值在后,然后一个值在外层递增遍历数组,一个值在内层递减找出更大的值往后挪。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void insert_sort2(int nums[], int count, int *step) {

int val = 0;
for (int i = 1; i < count; i++) {
int j = i - 1;
val = nums[i];
// 取当前的与之前的所有的元素比较,碰到比之大的就交换
// 小的就不变,还原值,因为前面的值总是排好序了的,因此只要
// 判断与前一个比较,如果是大于前一个值得值,就可以直接结束本次循环了。
while (j >= 0 && nums[j] > val) {
nums[j + 1] = nums[j];
j--;
(*step)++;
print_nums(nums, count, step);
sleep(1);
}
nums[j + 1] = val;
}
print_nums(nums, count, step);
}

输出结果

递增:

╭─  ~/github/cc-cpp-plus-plus/algorithms-unlocked    master                                           22:55:22 
╰─ ./a.out
[1]0: 9        [1]1: 12        [1]2: 3        [1]3: 7        [1]4: 14        [1]5: 11
[2]0: 9        [2]1: 3        [2]2: 12        [2]3: 7        [2]4: 14        [2]5: 11
[3]0: 3        [3]1: 9        [3]2: 12        [3]3: 7        [3]4: 14        [3]5: 11
[4]0: 3        [4]1: 9        [4]2: 7        [4]3: 12        [4]4: 14        [4]5: 11
[5]0: 3        [5]1: 7        [5]2: 9        [5]3: 12        [5]4: 14        [5]5: 11
[6]0: 3        [6]1: 7        [6]2: 9        [6]3: 12        [6]4: 11        [6]5: 14
[7]0: 3        [7]1: 7        [7]2: 9        [7]3: 11        [7]4: 12        [7]5: 14
[7]0: 3        [7]1: 7        [7]2: 9        [7]3: 11        [7]4: 12        [7]5: 14

递减:

╭─  ~/github/cc-cpp-plus-plus/algorithms-unlocked    master                                           22:55:46 
╰─ ./a.out
[1]0: 12        [1]1: 12        [1]2: 3        [1]3: 7        [1]4: 14        [1]5: 11
[2]0: 9        [2]1: 12        [2]2: 12        [2]3: 7        [2]4: 14        [2]5: 11
[3]0: 9        [3]1: 9        [3]2: 12        [3]3: 7        [3]4: 14        [3]5: 11
[4]0: 3        [4]1: 9        [4]2: 12        [4]3: 12        [4]4: 14        [4]5: 11
[5]0: 3        [5]1: 9        [5]2: 9        [5]3: 12        [5]4: 14        [5]5: 11
[6]0: 3        [6]1: 7        [6]2: 9        [6]3: 12        [6]4: 14        [6]5: 14
[7]0: 3        [7]1: 7        [7]2: 9        [7]3: 12        [7]4: 12        [7]5: 14
[7]0: 3        [7]1: 7        [7]2: 9        [7]3: 11        [7]4: 12        [7]5: 14

结果是一样的。

时间复杂度

两者的时间复杂度是一样,

最好的情况是:顺序已经排好了的,每次 for 循环中,while 条件都不满足 nums[i - 1] > val 而不会进入循环,因此时间复杂度是 O(n)

最坏的情况是:逆序,这种情况每次 for 循环都要在 while 里面执行 i 次的替换操作即: 1 + 2 + 3 + … + (n - 1) 次,时间复杂度为 O(n*n)

PS: 忽略主项系数,和低阶项,得出的时间复杂度

归并排序

归并排序,首先将数组分解至每个范围内只剩一个元素时候,再进行合并。

main 函数

1
2
3
4
5
6
7
8
int main(int argc, char *argv[]) {
int nums[] = { 12, 9, 3, 7, 14, 11, 6, 2, 10, 5};
int count = sizeof(nums) / sizeof(int);
int p = 0, r = count - 1, q = (p + r) / 2;
merge_sort(nums, p, q, r);
print_arr(nums, p, r, 'E');
return 0;
}

排序函数 merge_sort

1
2
3
4
5
6
7
8
void merge_sort(int nums[], int p, int q, int r) {
/* sleep(1); */
/* printf("\n---- start ---- p: %d, q: %d, r: %d\n", p, q, r); */
resolve(nums, p, q, 'L');
resolve(nums, q + 1, r, 'R');
merge(nums, p, q, r);
/* printf("\n---- end ---- \n\n"); */
}

使用了两个 resolve 将数组拆分至最小单元(只包含一个元素),和一个 merge 拆分完成之后的合并,从

最小单元开始合并并且排序。

拆分函数 resolve

1
2
3
4
5
6
7
8
9
void resolve(int nums[], int p, int r, char d) {
/* print_arr(nums, p, r, d); */
int q = (p + r) / 2;

if (p < r) {
merge_sort(nums, p, q, r);
}

}

每次取中间索引值将其拆分成更小的单元。

合并函数 merge

核心函数,拆分成最小单元之后,排序且合并操作。

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

void merge(int nums[], int p, int q, int r) {
/* printf("merge: %d, %d, %d\n", p, q, r); */

int tmp = 0;
int max = nums[q] > nums[r] ? q : r;

// 右边的从 大->小,左边的从 小->大
// 因为无论如何左右两边的数组元素都已经是有序且升序的,即后面的元素总比前面的大
// 那么让右边的数组最后一个元素去比较左边的数组然后替换之后,就能保证右边数组总能以正确的顺序
// 插入到左边的有序数组中去。
// 即:这么做能确保,右边数组越靠后的数总比靠前的数先找到自己的正确位置。
for (int j = r; j > q; j--) {
for (int i = p; i < q + 1; i++) {
tmp = nums[i];
if (nums[i] > nums[j]) {
nums[i] = nums[j];
nums[j] = tmp;
}
}
}

printf("p: %d, q: %d, r: %d\n", p, q, r);
/* print_arr(nums, 0, 9, 'm'); */
}

这里使用了两个 for 循环来处理,是的时间复杂度将达到 O(n^2) 属于不合理方法。

merge 优化

通过动态分配内存,数组拷贝和一个 for 来进行排序,此时的排序操作的其实是拷贝后的内控空间,因此属于非原址排序。

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

void merge(int nums[], int p, int q, int r) {
/* printf("merge: %d, %d, %d\n", p, q, r); */

int tmp = 0;
int max = nums[q] > nums[r] ? q : r;

int nl = q - p + 1;
int nr = r - q;

int *plnums = (int *)malloc((nl + 1) * sizeof(int));
int *prnums = (int *)malloc((nr + 1) * sizeof(int));

if (plnums == NULL || prnums == NULL) {
exit(0);
}

for (int i = 0; i < nl; i++) {
*(plnums + i) = nums[p + i];
}
*(plnums + nl) = INT_MAX;

for (int j = 0; j < nr; j++) {
*(prnums + j) = nums[q + j + 1];
}
*(prnums + nr) = INT_MAX;

for (int k = 0, i = 0, j = 0; k < (nl + nr); k++) {
int _k = p + k;

int lv = *(plnums + i);
int rv = *(prnums + j);

if (lv > rv) {
nums[_k] = rv;
j++;
} else {
nums[_k] = lv;
i++;
}
}

free(plnums);
plnums = NULL;
free(prnums);
prnums = NULL;
}
  1. 为左右两个数组元素分配新的空间用来临时存放这些元素

    int *plnums = (int *)malloc((nl + 1) * sizeof(int));

    int *prnums = (int *)malloc((nr + 1) * sizeof(int));

  2. 将左右两边的元素拷贝到分配的新内存中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (int i = 0; i < nl; i++) {
    *(plnums + i) = nums[p + i];
    }
    // ...

    for (int j = 0; j < nr; j++) {
    *(prnums + j) = nums[q + j + 1];
    }
    // ...
  3. 将分配的内存末尾空间的值置为最大值,避免访问意外内存空间,保证循环顺利进行

    *(plnums + nl) = INT_MAX;

    *(prnums + nr) = INT_MAX;

  4. 循环体,使用 _k, k 来获取 p~r 之间元素的地址,将较小的存储到 _k 位置

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15

    for (int k = 0, i = 0, j = 0; k < (nl + nr); k++) {
    int _k = p + k;

    int lv = *(plnums + i);
    int rv = *(prnums + j);

    if (lv > rv) {
    nums[_k] = rv;
    j++;
    } else {
    nums[_k] = lv;
    i++;
    }
    }
其中 `if...else` 以及 `i++, j++` 尤为关键,这里是将,哪个空间内的第 `i/j` 个元素比较小就将其保存到 `nums[_k]`  
位置上,哪一个小就让那一边的索引递增,直到遇到比另一边值大的值则换边。  

因为我们将两边空间的最后一个内容置为了 `INT_MAX` 因此能确保能访问正确范围内的元素值。
  1. 用完记得释放 free(...)

时间复杂度分析

main 里面调用 merge_sort()

这个函数调用里面包含三个步骤

  1. 第一个 resolve()
  2. 第二个 resolve()
  3. merge() 回溯合并函数

那么下面开始分析三个步骤的时间复杂度

调用 resolve() 的目的是为了将数组平均拆分,最后拆分的结果是左右两边均只有一个元素,

即每个 resolve() 加起来将最多执行 n/2 次拆分,那么所需要的时间记为: T(n/2),得出两次

resolve() 时间为 2T(n/2)。

进行 merge() 需要往回回溯,且需要对所有当前的元素进行拷贝,那么假设 p = 1, r = n,那么

意味着最大的拷贝个数为 n 个,拷贝的次数为 lgn,得到总次数为 nlgn 即时间复杂度为 O(nlgn)。

快速排序

快速排序的原理和归并排序基本是一样,因为都需要使用

  1. 递归将数组拆分成最小单元
  2. 进行遍历比较。

不同点:

*归并排序*:在每次置换的过程中需要重新分配新的内存空间,用来存放当前拆分单元的数组元素,它实际进行置换操作的并非

原数组本身,而是心分配的内存空间,非原址排序。

*快速排序*: 进行置换的一直都是原始数据本身,不需要重新分配内存,使用拆分单元的最后一个元素作为参考值,然后遍历整个拆分

单元,目的是将所有比参考值小的都放到其左边,比它大的都放到右边,以此往复最终递归完成,数据便已排好序了。

因此快速排序的重点在:

  1. 递归拆分
  2. 最后一个作为参考值
  3. 遍历置换

main

1
2
3
4
5
6
7
8
9
10

int main(int argc, char *argv[])
{
int nums[10] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int len = sizeof(nums) / sizeof(int);
printf("len: %d\n", len);
int p = 0, r = len - 1;
quick_sort(nums, p, r);
return 0;
}

main 函数中,初始化 p, r, len 的值,起始调用 quick_sort(nums, p, r) 给的值是

p = 0, r = len - 1, 分别为头和尾,启动快速排序。

quick_sort(int nums[], int p, int r)

这个函数首先由三个参数:

  1. nums[] 这个始终不变,使我们需要排序的数组原始数据
  2. p 每段分割之后数组的起始索引(这里的数组都是针对原始数组,下同)
  3. r 每段分割之后数组的结束索引

这里面的核心部分有三个地方:

  1. 递归结束条件: if (p >= r) 此时说明左右两边已经没可比较的元素了
  2. 置换条件: if (nums[p + i] <= last)

    这里采用循环,加上这个条件判断,判断当前区间的元素是否比参考元素小,如果是则将其逐一

    置换 j 指定位置索引的数组元素,从而达到将该区间数组排序的目的。

    注意: nums[p + i] 中采用的是 p + i 作为索引,目的是为了能正确取出 nums 数组中的元素进行置换。

  3. 获得断点 q 的值,即下次递归用来分割数组的中间位置,这个位置由上一次递归结束时决定的。

    计算方式为上一次递归结束,最后一个参考元素被放置的位置所在的索引值。

  4. 两次递归

    左递归: quick_sort(nums, p, q - 1)

    有递归: quick_sort(nums, q + 1, r)

    递归不需要包含参考元素的位置,因为该位置的元素必定是排序正确的元素,因为左边必定是比它小的

    而右边必定是比它大的元素,即它的位置正是它应该在的位置,不需要再次参与下次递归。

时间复杂度分析

假设是最坏的情况,即数组为逆序数组,即最后一个参考值为最小的值。

那么就有(比如: [5, 4, 3, 2, 1]):

  1. 最小拆分单元为一个元素的数组,因为两次调用 quick_sort ,因此最坏情况下最大拆分次数即为 lgn
  2. 进行置换,属于最坏的情况,每次都需要置换需要遍历的次数为 (n - i) ,i(0 ~ n) 为未排序的元素个数

比如: 由于每次置换的数组没有比最后一个更小的数,所以每次都需要遍历当前数组的整个数组。

  1. i = 0 次置换([5, 4, 3, 2, 1]):

    1. 遍历整个数组([5, 4, 3, 2, 1])
    2. 将最小的值 1 放到第一个位置上去,这需要 n
    3. 最后数组变成 [1, 4, 3, 2, 5]
    4. 拆分得到左: [1], 右: [4, 3, 2, 5] 左边结束,进入右边递归 quick_sort(nums, q + 1, r)
  2. i = 1 次置换([4, 3, 2, 5]):

    1. 发现 5 是最大,遍历了 n - 1 = 4 次,但由于都比 5 小,因此只是做了原位替换而已
    2. 最后数组变成 [4, 3, 2, 5]
    3. 拆分的到左: [4, 3, 2], 右: 5 ,进入左边递归 quick_sort(nums, p, q - 1)
  3. i = 2 次置换([4, 3, 2]):

    1. 发现 2 ,遍历 n - 2 = 3 次,发现前面的都比它大,然后遍历到自己满足条件,与 4 置换。
    2. 最后数组变成 [2, 3, 4]
    3. j = 3 到了最后一个位置
    4. 拆分得到左: [2, 3], 右: [4], 进入左边递归 quick_sort(nums, p, q - q)
  4. i = 3 次置换([2, 3]):

    1. 发现 3, 遍历 n - 3 = 2 次后,发现 3 最大,不需要置换。
    2. 最后数组依旧是 [2, 3]
    3. 由于没有置换,因此 j = 0
    4. 拆分得到左: [2], 右 [3] ,最后发现 [3] 只有一个元素,退出 quick_sort 结束。
  5. 计算结果:

    每次遍历的次数为 n - i 次, i 范围: 0 ~ (n - 2) 即 O(n) = n + (n -1) + (n - 2) + … + 2

    S(n) = n(n + 1)/2 => O(n) = S(n) -1 = n(n + 1)/2 - 1

    加上拆分的 lgn

    忽略低阶项 lgn + n/2 - 1,忽略常数倍 1/2 得到 O(n) = n^2。


    上面是最坏的情况分析,最好的情况是已经排序好了的数组 [1, 2, 3, 4, 5]

    每次取最后一个值参考,最后都不会发生置换,因此所花费的时间都只是在递归拆分上。

输出结果分析

len: 10

#1
[0]: 5    [1]: 2    [2]: 3    [3]: 6    [4]: 12    [5]: 7    [6]: 14    [7]: 9    [8]: 10    [9]: 11
<0>: 5    <1>: 2    <2>: 3    <3>: 6    <4>: 12    <5>: 7    <6>: 14    <7>: 9    <8>: 10    <9>: 11

#2
[0]: 2    [1]: 3    [2]: 5
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 12    <5>: 7    <6>: 14    <7>: 9    <8>: 10    <9>: 11

#3
[0]: 2
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 12    <5>: 7    <6>: 14    <7>: 9    <8>: 10    <9>: 11

#4
[0]: 5
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 12    <5>: 7    <6>: 14    <7>: 9    <8>: 10    <9>: 11

#5
[0]: 7    [1]: 9    [2]: 10    [3]: 11    [4]: 14    [5]: 12
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#6
[0]: 7    [1]: 9    [2]: 10
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#7
[0]: 7    [1]: 9
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#8
[0]: 7
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#9
null
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#10
null
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 14    <9>: 12

#11
[0]: 12    [1]: 14
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 12    <9>: 14

#12
null
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 12    <9>: 14

#13
[0]: 14
<0>: 2    <1>: 3    <2>: 5    <3>: 6    <4>: 7    <5>: 9    <6>: 10    <7>: 11    <8>: 12    <9>: 14

逐步分析:

#1
[0]: 5 [1]: 2 [2]: 3 [3]: 6 [4]: 12 [5]: 7 [6]: 14 [7]: 9 [8]: 10 [9]: 11

<0>: 5 <1>: 2 <2>: 3 <3>: 6 <4>: 12 <5>: 7 <6>: 14 <7>: 9 <8>: 10 <9>: 11

这一步是第一次在 main 中调用 quick_sort(nums, p, r) 结果

用 nums[9] = 6, 作为参考,遍历一遍数组之后将比它小的排到前面,大的排到后面,等于它的值排到中间,

得出 #1 的结果,显然左右两边的顺序依旧是乱的,但是左边都比 6 小,右边都比 6 大,这正是我们想要的

结果。


#2
[0]: 2 [1]: 3 [2]: 5

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 12 <5>: 7 <6>: 14 <7>: 9 <8>: 10 <9>: 11

经历了 #1 需要以 <3>: 6 为界进行两次递归,得到左边: 5, 2, 3 和右边:12, 7, 14, 9, 10, 11

首先对左边递归,得到 #2 结果:2, 3, 5。

且此刻,参考值位置在 [1] 上,即 q = 1,然后进行 #3。


#3
[0]: 2

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 12 <5>: 7 <6>: 14 <7>: 9 <8>: 10 <9>: 11

经过 #2: 2, 3, 5 分割出来得到左边 2, p == r 满足结束递归条件,然后执行右边即 #4


#4
[0]: 5

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 12 <5>: 7 <6>: 14 <7>: 9 <8>: 10 <9>: 11

同 #3,p == r 结束递归,到此第一个 quick_sort(nums, p, q - 1) 结束。


#5
[0]: 7 [1]: 9 [2]: 10 [3]: 11 [4]: 14 [5]: 12

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

这里执行的结果是第一次执行第二个 quick_sort(nums, q + 1, r) 的结果。

这里是以 #4 中最后一个元素 [9] = 11 作为参考值进行置换的结果,完成之后 11 将在 <7> 位置上,

左边是: 7, 9, 10 右边是: 14, 12

进入下一次递归。


#6
[0]: 7 [1]: 9 [2]: 10

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

这里会发现 7,9,10 已经排好序了,无序置换操作,则有了 #7, #8 的输出结果

#7
[0]: 7 [1]: 9

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

#8
[0]: 7

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

这里结束,则进入右边的 14, 12 递归处理。


#9
null

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

#10
null

<0>: 2 <1>: 3 <2>: 5 <3>: 6 <4>: 7 <5>: 9 <6>: 10 <7>: 11 <8>: 14 <9>: 12

但是会发现 #9, #10 输出的结果里面第一行是 null,因为传递给 print_arr 的 n 是 0,那来分析下为什么是 0???

我们从 #5 回顾,执行的是 quick_sort(nums, q + 1, r) 结合这里执行 #9 的时候其实是将右边的: 14,12

进行置换排序,此时 p = q + 1 (8 的位置),r (9的位置),

显然不满足退出递归的条件,则进行下面的置换操作得到结果: 12, 14

虽然发生了置换,但是此时 p = 8, r = 9, q 却发生改变了值为 12 所在的位置 8 即 q = 8。

随即执行左边 quick_sort(nums, 8, 7) 满足递归结束条件,因此输出了 #9 和 #10 包含 null

这里的 #9 是 q = j - 1; 后面的 print_arr 输出的, #10 是退出递归是输出的。

随即执行右边 quick_sort(nums, 9, 9) 满足递归结束条件,因此输出了 #11 和 #12 中的结果

这里的 #11 是 q = j - 1; 后面输出的,因为此时的 q = 8, p = 8, r = 9,因此输出了 12, 14 结果

#12 是以 quick_sort(nums, 8 + 1, 9) 进入下次递归而满足条件是输出的结果

由此我们就得到了所有输出结果的分析。

本文标题:《算法基础》打开算法之门(Algorithms Unlocked) 读书笔记

文章作者:ZhiCheng Lee

发布时间:2019年05月09日 - 22:59:12

最后更新:2019年06月26日 - 22:27:40

原始链接:http://blog.gcl666.com/2019/05/09/c_algorithm_unlocked/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%