笔者刚刚学习自己的的一门编程语言（C语言）的时候，正在runoob上面刷经典一百道题。
第一次见到排序问题，我内心是不屑的，
“这™不是张口就来？”
然后我就贡献了一整个下午的时间在一个简单的排序上面。
初学者不知到排序的时候可以有交换两个值这样的操作，所以基本的选择排序都没想出来，深陷于“找出最小值，放入新数组，再擦除这个值…”的死胡同里面。不仅贡献了一下午的时光，还顺带自尊心极度受挫。
其实当时我的这种思路非常接近一种叫选择排序的算法，只需要一点点指点就可以马上取得拨云见日的效果。
如果你也是这样子的，那最好看完本文。本文系我读《算法导论》的一份笔记，希望可以给还不懂排序的你带来帮助。
本文代码都是在Windows10下，使用64位GCC编译器编译，编译标准为C++17。
我本来想让代码兼容C11标准，让只会使用C语言的同学们也可以流畅阅读。但无奈人太懒，半途而废了……
为还不会C++或者C++不够熟练的同学们附上参照表：
| 本文的表达 | C | 解释 |
|---|---|---|
_Bool, bool |
_Bool |
布尔类型 |
using compare = bool (*)(const Type &a, const Type &b); |
typedef _Bool (*compare)(Type a, Type b); |
给函数指针取别名 |
auto |
无可替换 | 自动推导类型 |
auto i{123} |
int i=123 |
初始化 |
Now， Let’s GO！
大多数地方都把冒泡排序作为第一种教授的排序算法。其实我认为选择排序才是新人最容易理解的排序算法。还记得我当时的思路吗？从还没排序的数组内找出最小值，然后放到第一个，如次往复。选择排序就是这样的。我们只需要设置循环来实现就好了。
typedef bool (*compareFunction)(int, int);
typedef unsigned int size_t;
// 待会会以函数指针的方式将其传入排序函数内
_Bool df_compare(int a, int b){ return a<b; }
// 使用两个指针来标记数组内要排序的部分
void Selection_sort(int *begin, int *end, compareFunction compare) {
size_t size{end - begin};
for (size_t i{0}; i < size - 1; ++i) {// i是已排序部分和未排序部分的分界
for (size_t j{i + 1}; j < size; ++j) {// j不断找出未排序部分的最小值
if (compare(begin[j], begin[i])) {
// 交换二值
int tmp{begin[j]};
begin[j] = begin[i];
begin[i] = tmp;
}
}
}
}
上面这一个函数就演示了指针、数组的使用，还演示了使用函数指针一定程度上实现多态。基本语法还不熟悉的同学们得加油啦。
其实这个排序方法也可以在对链表使用，而且还不会有过多麻烦。实在觉得难，起码也要把这一种算法记住。
插入排序很像打扑克牌的时候，你抓了一手凌乱的扑克牌然后排序的时候的样子。手里是已经按照从大到小排号的扑克，然后你每次抓一张新的牌就把它插入到合适位置，然后你手里的牌就永远是有序的。
当然，有经验的对手可能会据此猜测你抽到了什么牌。。
有了扑克牌这个例子应该好理解了，不过应用到算法上面，就又可以难倒一大票萌新。为什么？因为数组不是你手里的扑克牌，要往静态数组内插入一个值或者移除一个值，这样的操作是有一点难度的！使用Python或者C++或者Java的同学也还别得意，就算别人帮你封装好了这样的操作，你还是需要自己处理一大票问题。看下面的代码：
int arr[]={1, 2, 4, 3, 2, 6, 8};
int i=3, j=4;
printf("%d\t%d", arr[i], arr[j]);
目前是会输出3 2字样，但你如果向前面插入一个什么数，后面的内容就都向后推了一格，所以你还要让i，j同步变化。这样不说做不到排序，起码写出来的代码不会很优雅了。
如果你使用链表，那确实没那样的问题了。不过我猜，来看这篇文章的人，还真就不一定都能写得出链表。。。
还不会链表的同学，可以来看看我写的链表教程。
如果仍然像之前一样，把数组分为已排序和未排序两部分，我们可以这样做：
void Insertion_sort(int *begin, int *end, compareFunction compare) {
for (auto i{1}; i < end - begin; ++i) {// i把数组分割为了两个部分
int tmp{begin[i]};// 把begin[i]的内容保存下来，之后插入到合适的地方去
int j{i-1};
while (j >= 0 && compare(tmp, begin[j])) {// 从后往前查找已排序部分里合适的位置来插入
begin[j + 1] = begin[j];// 顺便把后面的内容向后移，空出来位置
--j;
}
begin[j + 1] = tmp;// 注意j代表的意义
}
}
穷鬼没钱做高端大气的动画来演示原理，就…勉强看看吧。
当然，如果你闲的蛋疼，也可以弄个递归版本出来（除了可以让你熟悉一下递归没有任何好处）：
void Insertion_sort_Recurition(int *begin, int *end,
compareFunction compare = df_compare) {
if (--end - begin > 1) {
Insertion_sort_Recurition(begin, end);
}
int *p = end - 1;
int tmp = *end;
while (p >= begin && compare(tmp, *p)) {
*(p + 1) = *p;
p--;
}
*(p + 1) = tmp;
}
感觉这个递归和傻逼一样。。。
冒泡排序原理很相似，不过不同于选择排序，它是让待排序的值像泡泡一样浮到它该去的地方。不多讲。
void Bubble_sort(int *begin, int *end, compareFunction compare) {
size_t size{end - begin};
for (size_t i{0}; i < size - 1; ++i) {
for (size_t j{size - 1}, k{j - 1}; j > i; --j, --k) {// The Bubble
if (compare(begin[j], begin[k])) {
// Swap 2 values.
int tmp{begin[j]};
begin[j] = begin[k];
begin[k] = tmp;
}
}
}
}
上面的排序方法虽然好理解，但如果数据一多起来，那就会很慢。你看看它们基本上都用上了两层嵌套循环，数据一增加，消耗时间就是平方级别增长。我们想要的，是那种力速双A的强大算法。
归并排序采用了分治法这种极为玄学的思想。它的思路倒是非常朴素：数组里面元素越少，排序起来不就越容易？
如果等待排序的数组有10个元素，它的想法是这样的：
把它对半分，不就只需要排序5个元素两次了？
再对半分，就只需要对2~3个元素排序四次。
。。。。
一直分到10份，只剩下一个元素，不就不用排序了？
虽然现在这个想法看起来跟傻狍子一样，但其实它说的没错，问题在于，如何把两个已经排序的数组再组合为一个？
这就是归并排序的核心，合并两个已排序的数组。
//这里假定这两个数组相邻，mid左右都是已经排序好的数组。
void merge(int *begin, int *mid, int *end,
compareFunction compare = df_compare) {
const auto n1{mid - begin}, n2{end - mid}; // 2 new arrays' length.
// 把两个数组内容复制一次
int l1[n1], l2[n2];
for (int i{0}; i < n1; ++i) {
l1[i] = begin[i];
}
for (int i{0}; i < n2; ++i) {
l2[i] = mid[i];
}
// 归并
int i{0}, j{0}, k{0}; // i在l1内运动，j在l2内，k在l3内
// 两个数组不一定等长，所以还不能一步到位
for (; i < n1 && j < n2; ++k) {
if (compare(l1[i], l2[j])) {
begin[k] = l1[i];
++i;
} else {
begin[k] = l2[j];
++j;
}
}
// 合并剩下的部分
if (i == n1) {
for (; j < n2; ++j, ++k) {
begin[k] = l2[j];
}
}
if (j == n2) {
for (; i < n1; ++i, ++k) {
begin[k] = l1[i];
}
}
}
代码有点多，但确实做到了。接下来我们只需要使用递归，来把数组无限分割为个体就好了：
void Merge_sort(int *begin, int *end, compareFunction compare = df_compare) {
if (begin < end - 1) { // 当begin和end已经相邻就停下来
auto mid{begin + (end - begin) / 2};// 因为指针不支持相加，所以出此下策
Merge_sort(begin, mid, compare);
Merge_sort(mid, end, compare);
// 归并！
merge(begin, mid, end, compare);
}
}
**归并排序是没有嵌套循环的！**归并两个总共有n个元素的数组，只需要先复制n个元素一次，然后遍历一次。随着n增加，消耗时间t还只是an+b的样子。不过因为要先从最散的状态下开始归并，如果还是10个元素的数组：
也就是先把1个元素的归并5次，变成4个有2~3个元素的有序序列；
2~3个元素的归并2次，变成两个有5个元素的有序序列；
5个元素的归并一次，变成一个有10个元素的有序序列；
完成。
数学好的同学就会发现，这是个指数-对数模型，如果有n个元素，这样的归并需要执行大概
l
o
g
2
n
log_2n
log2n次。演算如下：
假
设
数
组
内
含
n
个
数
据
，
需
要
归
并
t
次
n
=
2
t
所
以
t
=
l
o
g
2
n
消
耗
总
时
间
f
(
n
)
=
A
n
l
o
g
2
n
+
B
假设数组内含n个数据，需要归并t次\\ n=2^t\\ 所以t=log_2n\\ 消耗总时间f(n)=Anlog_2n+B
假设数组内含n个数据，需要归并t次n=2t所以t=log2n消耗总时间f(n)=Anlog2n+B
当然，这个公式只能描述个大概走势，并非准确（怎么可能执行 l o g 2 10 log_210 log210次归并呢？）。不过这已经可以说明归并排序比前几种方式有明显优势。如果数据输入量足够大，这几种算法消耗时间的差距会非常恐怖。
快速排序，顾名思义，就是一个字快。它和归并排序一样采用了分治法原理，消耗总时间也是 n l o g 2 n nlog_2n nlog2n级别，但事实上它比归并排序快一些，算法竞赛卡时间选手的最爱。
找到一个某数，尽量把大于某数的都扔去一边，小于的扔去另一边。然后就形成了大于这个数的都在右边，小于这个数的都在左边。再对两左右部分再重复相同操作，一直到不能再分为两部分为止。
这个某数是什么？答案是随便。我一般会选择数组正中间的那个数。这样最终结果就刚好会以这个数为分界点。
但在我看来，快排比归并还要难理解一些，使用的时候是依靠记忆多于依靠理解的。。
void Quik_sort(int *begin, int *end, compareFunction compare = df_compare) {
if (begin < end-1) {// 递归终点，到两指针相邻就说明只还剩一个元素，就不必继续排序了。
auto mid{begin + (end - begin) / 2};
auto left{begin}, right{end - 1};
while (left < right) {
//寻找左边的、大于某数的值
while (compare(*left, *mid) && left < right) {
left++;
}
while (!compare(*right, *mid) && left < right) {
right--;
}
// 交换，同时再把left向右推一格，right向左推一格。没有这一步就会陷入死循环。
auto tmp{*left};
*left++ = *right;
*right-- = tmp;
}
// 递归排序
Quik_sort(begin, mid);
Quik_sort(mid, end);
}
}
};
快速排序比归并排序代码量少不少，适合速用。但快速排序是不稳定的算法。什么叫不稳定？比如说我排序下面的结构体数组，再用不同的排序打印结果：
struct Obj {
int i;
string label;
};
Obj objarr[] = {{2, "B"}, {2, "A"}, {4, "D"}, {3, "C"}, {3, "F"}};
但目前我们的函数只接受int类型数组，为了让我们的算法可以适应这样的数据类型，我们需要先做一下泛型：
template <class Type>
using compare = bool (*)(const Type &a, const Type &b);
template<class Type = int>
void Quik_sort(Type *begin, Type *end, compare<Type> compare ) {
if (begin < end-1) {
auto mid{begin + (end - begin) / 2};
auto left{begin}, right{end - 1};
while (left < right) {
while (compare(*left, *mid) && left < right) {
left++;
}
while (!compare(*right, *mid) && left < right) {
right--;
}
auto tmp{*left};
*left++ = *right;
*right-- = tmp;
}
Quik_sort<Type>(begin, mid, compare);
Quik_sort<Type>(mid, end, compare);
}
}
排序打印出结果：
Quik_sort<Obj>(
objarr, objarr + 5,
[](const Obj &a, const Obj &b) -> bool { return a.i < b.i; });// 这是个lambda表达式
for (auto &i : objarr) {
cout<<i.label<<" ";
}
输出：B A F C D。你看，都具有一样的索引的情况下，C，F的顺序被颠倒了，但B，A并没有。所以一旦对这样的数组使用快速排序，结果将会是无法预料的！！
欲戴王冠，必承其重。正因如此，才更有必要根据实际需求选择不同的排序算法。如果要求高稳定性，可以使用归并排序代替。
毕竟，算法也是有极限的嘛~~
排序算法非常多，而且各有各的特色。这里只介绍了简单一些的排序算法。许多算法利用了二叉树这样的数据结构，还有的则是几种算法的复合或者改进来达到特殊目的（如改进插入排序的希尔排序）。这些算法我会在排序篇（二）里面详细介绍的！所以你若觉得自己有时间等我鸽的，不妨点个关注，没准下星期我就更了呢……
