第二章主要讲了一些排序算法。不过分治算法我想放到后面去讲。因为分治算法nlog2n级别的，感觉和快速排序、堆排序放在一起讲会有很有趣的现象发生。
我们这里就主要介绍选择排序、冒泡排序和插入排序。
其实C++里面我们几乎不会写排序算法。而是很无脑的选择这个方法：
sort(a+1,a+1+n,cmp)
sort用到的是快速排序的算法，算法复杂度是Nlog2N的，非常优秀，因此我们可能也不需要再学习别的排序算法？
其实排序算法很有趣。我们可以通过数学方法证明排序算法的最优时间复杂度为Nlog2N，但是有过了解的小伙伴们可能知道有一个异类：桶排序。N级别的。当然，桶排序这类排序在算法导论里面有，我们之后会讲到。
堆排序用到的是堆这个数据结构，分治排序用到的是分治思想，而普通的冒泡之类的排序是很棒的帮助我们理解数组、循环的工具。排序算法肯定有自己的意义。
我们看一下，假如有下面几个数字，我们要从小到大排序。
9 27 38 19 27 291 93 27 1
首先我们想到的是什么？
我想到的是每次找最小值。什么意思？
首先我们找一下这9个数字的最小值。很明显是1。那我们把1放在第一位，和9交换。
1 27 38 19 27 291 93 27 9
之后我们找第2-9个数字中最小的那个。很明显是9。我们让9和27交换。
1 9 38 19 27 291 93 27
…
经过8次操作之后容易我们能得到最优排列。代码如下：
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]>a[j]) swap(a[i],a[j]);
我们将这个算法叫做选择排序。很明显是O(n^2)级别的。
现在不用想有没有更优的解法。我们可以想一想，有没有其他的O(n^2)的排序算法？
其实很容易就能想到一个。我们只要每次寻找最大值放到最后一位就行了。
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[j]>a[j+1])
swap(a[j],a[j+1]);
观察上面程序，每次比较相邻两个数字，然后前面数字如果大于后面一个就交换。很明显，每轮这样操作之后，最大值都会被推到最后面。
这个排序称为冒泡排序，时间复杂度也是O(n^2)
然后我们看看下面这种方法。还是这个序列。
9 27 38 19 27 291 93 27 1
我们从第2位开始。第二位和第一位比较，比第一位大，因此保留。
9 27
我们再进入38，判断38比27大，保留。
9 27 38
之后是19，19比27和38都大，很明显，19应该插入27和38之间。
9 19 27 38
…
可能你已经发现这个算法的关键了。这个算法的过程其实就是每次保证1~i个数是从小到大排列的。相当于每次把新的数字插入进去。代码如下：
for(int i=2;i<=n;i++)
while(a[i]<a[i-1]){
swap(a[i],a[i-1];i--;
}
接下来我们计算时间复杂度。最好的情况当然是while循环直接不进去，那么时间复杂度为O(n)。while循环不进去的条件其实就是每次新进来的数字是最大的。也就是说原本的数组本来就是从小到大排列的。最坏的情况就是每次while循环都得全部转一圈。差不多O(n^2)但严格来说，时间复杂度总归略微比选择排序小一点。
今天内容比较短，但也确实讲了三种算法了。其实本来在《算法导论》中篇幅就不算长。不过作为基础还是希望大家好好掌握，而不是盲目使用sort一刀切。
记住，学习算法时思想比算法本身重要得多。
有问题可以在评论区留言。谢谢大家支持~！