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<int>, then we send it into a quick_sort function, you should return a vector with sorted seqeunces. Here is the thoughts:
- 首先随机拿出一个元素作为基准，比如v(通常会选取最左边的元素)，然后进行一下partition操作，该操作需要两个指针i, j，一个指向开头一个指向结尾，每次i++, j--,每次对比左边指针指向的数比v大就继续，遇到比v小的就调换i和j所指向的元素；
- 经过一次partition操作之后，应该在基准值左边的都是大于它的，右边的都是小于它的；
- 对左右两段在分别重复1，2，直到每段元素的个数为1为止；
咋一看，我曹感觉复杂，没有关系我们先把第一个操作完成，后面就是递归调用这个操作，你懂的。好吧，接下来让我们徒手写快排吧，如果你能够随时随地写一个快排，那么你对算法应该也已经从入门到精通了。
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);
}
这应该是目前来说，最简单的快速排序实现了吧。道理其实也非常简单，首先从后面开始，后面应该是大的，遇到小于标准的，那就复制给前面的，这个时候后面的小的就跑到了前面，前面的继续，遇到大的，就放到后面去，这个时候，大的到后面去了，但是前面的依旧保留着大的数，没有关系，继续后面的，又会有一个小只传到前面来。一直到最后，前面的只会移到后面，但是本身还是一个大值，于是就把标准赋值给它。这样切片完成。递归调用，两块的后面和第二块的前面中间是断点。就是这么简单。如果你能理解那就神奇了，因为我也不知道我在说什么。好我们继续下一个经典算法。
当然，在这里再列举一个冒泡排序，这是最简单的：
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个小时内写出正确无误的二分查找算法。
