前言
在”脉脉APP”上看到了字节跳动的福利真的好好啊。免费食堂，吃的东西比我“小柯基”的收费食堂好了N倍XD。对于字节跳动顿时向往了起来。可是一想到字节对算法要求很高，我就蛋疼了，怪自己大学没好好上算法课XD。而且今年貌似大环境不好，各家的招聘都比较严？对算法要求比较高？
于是就老老实实开始刷算法题吧，买了《剑指offer》这本书（其实大学开始找工作的时候这本书我也买过，不过买来基本没看。。。），到现在才看了80页真的有够慢的，看到了排序算法相关的章节，于是就“复习”(学习)下常见的排序算法，并将各个算法的特点在这遍blog里记录下（好记性不如烂笔头，虽然这些排序算法都已经代码敲过一遍了，但是感觉过段时间还是会很容易就忘记了）。
常见的排序算法有以下7中：冒泡排序，选择排序，插入排序，希尔排序，归并排序，快速排序，堆排序。下面就一一讲一下这几种排序算法的特点。
冒泡排序
一句话简单概括，每遍历一次都会将第n大的数字上浮到顶端第n个数字（冒泡最小的也可以，改下算法里比较两个元素大小并交换顺序的代码就可以了，easy）。
时间复杂度 O(n^2), 最坏时间复杂度O(n^2),最好时间复杂度O(n)（配合标志位flag，当已经全局有序，提前跳出循环结束排序）,空间复杂度O(1).
选择排序
从N个数中选择最小的数字放到第1位，然后从接下来的N-1个数中选择最小的数字放到第2位，一直到将剩下的最后一个数字，放到第N位。 时间复杂度 O(n^2),最坏时间复杂度O(n^2),最好时间复杂度O(n),空间复杂度O(1).
插入排序
N个数字，将第一个数组放到第一位，然后从第二位数字开始迭代。每位数字，都与前面的数字从后往前比较，并插入到合适的位置。
时间复杂度 O(n^2),最坏时间复杂度O(n^2),最好时间复杂度O(n),空间复杂度O(1).
希尔排序
插入排序的升级版。插入排序时，每次比较只能相邻的数字之间进行比较，并有可能相互换位置，所以数字如果要移动到它最终的位置上，要进行多次比较，效率较低。希尔排序在插入排序的基础上进行了优化。插入排序只能相邻的数字之间进行比较，希尔排序先可以自定义先从相距n的数字开始比较，再从相距n/2的数字进行比较，最后比较相距1（即相邻）的数字，最后相距1相当于就是插入排序，但是因为之前的比较，一些数字已经被高效的移动到目标位置或者目标位置附近，之后进行相距1的数字之间的比较时就可以通过少量的比较和交换即可完成排序，所以说希尔排序是插入排序的升级哦。
时间复杂度 O(n^1.3),最坏时间复杂度O(n^2),最好时间复杂度O(n),空间复杂度O(1).
归并排序
归并排序采用了分治的思想来处理问题，通过递归，将一个N个数子的排序，拆分成了N/2组。每组两个或1个数字，每组之内的数字进行排序，然后相邻组之间两两合并并排序，一直合并到只剩下两组分别排序好的数字，最后将这两组有序数字再合并为一组数字并排序，这就是归并算法。 时间复杂度O(nlog2n),最坏时间复杂度O(nlog2n)，虽好时间复杂度O(nlog2n)，空间复杂度O(n)。
快速排序
快速排序和归并排序都用到了递归，但是区别在于归并排序侧重的是怎么合并，而快速排序侧重的是怎么分,所以也可以称快速排序为归分排序。那快速排序是要分什么呢？就是要分左区间和又区间。快速排序的流程大致如下：选择一个数字作为中轴数(pivot)，将大于该数的值移动到pivot的右边，反之移动到pivot的左边，然后针对pivot的左、右区间重复上述，直到左右区间的个数都小于2，这个时候就不需要在基于pivot排序了。在基于pivot移动数据到左右区间时，我们可以通过双指针来实现代码。
时间复杂度O(nlogn)，最坏时间复杂度O(n^2)，最好时间复杂度O(nlogn)，空间复杂度O(nlogn)。
堆排序
堆是一种特殊的完全二叉树，满足每个父节点的大小均大于(小于)叶子节点，这种完全二叉数被称之为最大堆（最小堆）。因为完全二叉树中，子节点和父节点之间的关系可以通过节点的序号计算出来，所以完全二叉树也可以用数组来表示。堆排序，就是利用根节点是整个“树”中的最大(小)值这一特点来进行排序的。详细的代码实现和要注意的点请见：github.com/ambition080…
时间复杂度O(nlogn)，最坏时间复杂度O(nlogn)，最好时间复杂度O(nlogn)，空间复杂度O(nlogn)。