theme: channing-cyan
常见的有哪几种排序算法呢？这是一个很好的问题。了解排序方法的同时还需要对时间复杂度这些问题一起了解下。
先了解下算法稳定性的概念：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
冒泡排序
冒泡排序是一次性比较相邻的两个元素，一直重复到没有需要交换的时候。步骤如下：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
优点：在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。
缺点：适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。
而在每轮排序中都需要对相邻的两个元素进行比较，在最坏的情况下，每次比较之后都需要交换位置，此时时间复杂度为O(n^2)
选择排序
选择排序（Selection sort）是一种简单直观的排序算法，无论什么数据进去都是 O(n²)的时间复杂度，所以用到它的时候，数据规模越小越好。
思路如下图，在未排序的数列中找到最小的元素放在起始位置，然后在剩下未排列的数列中继续重复之前的操作放到已排序序列的末尾。
用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。
由于其固定的时间复杂度O(n²)，因此不适用于大量数据排序。
插入排序
插入排序的主要思想是，将数据按照顺序一个个的插入到有序的表中，最终的结果就是排序的结果。
最优情况是数组是有序时候，这样只要和前一个数据作比较即可，时间复杂度是O(n)。最坏情况是逆序排序时，需要的时间复杂度是1+2+3+...+N-1,时间复杂度是O(n²)。
因此插入排序算法同样适用于数据量不大的序列，算法稳定性要求高。
归并排序
归并排序的思路是先分再合。
分：数组分成两半，再递归对子数组进行分操作，直至到一个个单独数字。
合：和分的操作相反，先把两个数合成有序数组，再对有序数组进行合并操作，直到全部的子数组合成一个完整的数组。
归并排序时间复杂度为O(nlogn)
归并排序同样是稳定算法。在数据量比较大的时候也有较为出色的表现（效率上）。
快速排序
快速排序（Quick Sort）算法是在冒泡排序的基础上进行改进的一种算法，从名字上看就知道该排序算法的特点是快、效率高，是处理大数据最快的排序算法之一。
基本思想如下：通过一次排序将整个无序表分成相互独立的两部分，其中一部分中的数据都比另一部分中包含的数据的值小，然后继续沿用此方法分别对两部分进行同样的操作，直到每一个小部分不可再分，所得到的整个序列就变成有序序列。
常用步骤：先分区，经常是选择首个数字作为基准，将比基准小的元素放在基准的左边，大的放在基准的右边。再递归，对分区前后的子数组再进行分区排序。
最坏情况下每一次基准元素都是数组中最小或者最大的元素，则快速排序就是冒泡排序。此时时间复杂度同冒泡排序。
最好情况下是O(nlogn)，快排是一种稳定排序。是目前基于比较的内部排序中被认为最好的方法，当数据过大且数据杂乱无章时，则适合采用快速排序。
堆排序
堆是一种特殊的完全二叉树，即除了最底层之外，每一层都是满的。
二叉堆一般分为两种：最大堆和最小堆。
最大堆中的最大元素值出现在根结点（堆顶），堆中每个父节点的元素值都大于等于其孩子结点（如果存在）。
最小堆与最大堆情况相反
算法演示图如下：
