Introduce something about C++ Classic Algorithm Implementation

C++ Classic Algorithm Implementation

This article was original written by Jin Tian, welcome re-post, but please keep this copyright info, thanks, any question could be asked via wechat: jintianiloveu

Preface

this series is the many implementation of C++ classic algorithm, such as quick sort, binary search, Red-black tree. Let’s start the fucking jurney of algorithm!

Algorithm 1. 快速排序

ok, this the simplest but classic algorithm, we were given a vector, then we send it into a quick_sort function, you should return a vector with sorted seqeunces. Here is the thoughts:

  1. 首先随机拿出一个元素作为基准，比如v(通常会选取最左边的元素)，然后进行一下partition操作，该操作需要两个指针i, j，一个指向开头一个指向结尾，每次i++, j–,每次对比左边指针指向的数比v大就继续，遇到比v小的就调换i和j所指向的元素；
  2. 经过一次partition操作之后，应该在基准值左边的都是大于它的，右边的都是小于它的；
  3. 对左右两段在分别重复1，2，直到每段元素的个数为1为止；

咋一看，我曹感觉复杂，没有关系我们先把第一个操作完成，后面就是递归调用这个操作，你懂的。好吧，接下来让我们徒手写快排吧，如果你能够随时随地写一个快排，那么你对算法应该也已经从入门到精通了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quick_sort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left;
    int j = right;
    int key = a[i];
    while (i < j) {
        while (i < j && a[j] >= key) {
            --j;
        }
        a[i] = a[j];
        while (i < j && a[i] <= key) {
            ++i;
        }
        a[j] = a[i];
    }
    a[i] = key;
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

这应该是目前来说，最简单的快速排序实现了吧。道理其实也非常简单，首先从后面开始，后面应该是大的，遇到小于标准的，那就复制给前面的，这个时候后面的小的就跑到了前面，前面的继续，遇到大的，就放到后面去，这个时候，大的到后面去了，但是前面的依旧保留着大的数，没有关系，继续后面的，又会有一个小只传到前面来。一直到最后，前面的只会移到后面，但是本身还是一个大值，于是就把标准赋值给它。这样切片完成。递归调用，两块的后面和第二块的前面中间是断点。就是这么简单。如果你能理解那就神奇了，因为我也不知道我在说什么。好我们继续下一个经典算法。

当然，在这里再列举一个冒泡排序，这是最简单的：

1
2
3
4
5
6
7
8
9
10
11
12
void bubble_sort(int a[], int l) {
    // 最简单的冒泡排序法
    for (int i = 0; i < l; ++i) {
        for (int j = 0; j < l - i; ++j) {
            if (a[j+1] < a[j]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

Algorithm 2. 求子数组最大和

现在有个问题是求子数组最大和，这是我来腾讯实习面试的问题，其实要解决也很简单，这个就是在一个包含正数和负数的数组中，求取一个连续的子数组，使得其和在所有可能的子数组中最大。这个问题能够被解决的前提

Algorithm 3. 堆排序

这也是一种排序算法，但是由于名字比较牛逼所以我们今天就来实现以下它。它的基本原理是这样的：
先挖个坑，后面再来填。

Algorithm 4. 二分查找

这里我将提供简单实现和递归实现。曾经有人说过90%的计算机工程师无法再2个小时内写出正确无误的二分查找算法。