这篇文章主要介绍常见的几种排序，除了工作中可能用到之外，面试时被问也不会尴尬。

排序过程中有几个概念：

1. 稳定性：如果a原本在b前面，而a = b，稳定的排序之后a仍然在b的前面。不稳定的排序有可能b在a前面
2. 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
3. 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

冒泡排序

是一种交换类的排序。两两比较相邻元素，如果大小排序不正确，就交换位置。这种排序不需要额外的存储空间。只有交换两个数据位置的时候，需要一个temp位置暂存某一个数据的值

快速排序

是一种交换类的排序。核心的递归。

1. 先找到一个基准数，然后把比基准数大的归类到一个大数组A中，比基准数小的归类到另一个小数组B中
2. 把基准数，A数组，B数组按 B -> 基准数 -> A 的顺序拼接起来
3. A，B两个数组继续递归执行快速排序，也就是在其各自数组中找出基准数，以及其对应的大小数组

插入排序

是一种插入类排序，类似打牌的时候排序。

1. 从未排序的数据中找出一个值
2. 在已排序的数据中找到对应的位置
3. 把这个值插入找到的目标位置

在寻找合适的插入位置时，已排序的数据需要腾出一个位置来给新数据插入，所以只需要一个数据空间即可

希尔排序

希尔排序是一种优化版的插入排序，这是史上第一种突破O(n^{2)时间复杂度的排序。核心是根据增量把一个大数组拆成若干个小数组，每个数组自己用插入排序。这个增量需要让小数组的成员位置在大数组中尽可能相隔最远。}

1. 假设有15个数，第一次排序增量为 15 / 2 向下取整为 7
2. 每各7位组队，下标0和下标7的数据为一组，1和8，一直下去直到7和14（下标14即第15个数了）
3. 分组后每个小组用插入排序排好，然后修改增量为 7 / 2 向下取整为 3
4. 每隔3位组队，下标0，3，6，9，12组队，以此类推
5. 这些小组按插入排序排序好，继续修改增量，3 / 2 向下取整为 1
6. 只分成一组，这一个大组用插入排序

选择排序

简单粗暴，从一堆数中找出最小（或者最大）的值，暴力排序。最稳定的排序，也是最无脑的排序，时间复杂度和空间复杂度都是最稳定的。

堆排序

1. 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

归并排序

归并排序的核心是分治思想。把一个大数组逐步切成一个个小数组，有点类似切成一棵树，再组合这棵树

归并排序和选择排序，堆排序类似，这玩意时间复杂度是恒定的，最优，最差，平均时间复杂度都是一样的。但是需要额外的内存空间。所以如果有堆排序可选，肯定选堆排序，一样的时间复杂度，还省了内存

计数排序

1. 计数排序要求输入的数据必须是有确定范围的整数。
2. 计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

基数排序

基数排序从个位数开始，把个位数一样的数据集合在一块，然后排序一次。然后向前统计下一位数，把下一位数一样的数据集合在一块，再排序一次。直到最后排序完。

总结

选择合适的排序：

1. 首先考虑有没有时间复杂度的要求

   • 考虑数据无序性如何。如果数据非常混乱，优先看最坏时间复杂度；如果相对没这么混乱，优先看平均时间复杂度。最好时间复杂度就是不用排，已经有序了。
   • 考虑数据量。根据数据量n的大小去选择对数复杂度，指数复杂度还是线性复杂度

2. 再考虑有没有空间复杂度的要求

3. 最后考虑有没有稳定性要求