这里的堆排序是指原地堆排序，不创建新的空间。原地堆排序的核心步骤：

1.先将数组调整为最大堆；
2.不断的将当前堆顶元素和无序数组的最后一个元素进行交换；
3.交换之后，无序数组的最大值就放在了最终位置，此时进行siftDown；
4.重复步骤2和3，当无序数组的只剩下一个元素时，整个堆排序完成。

总结
1.在堆排序中，排升序要建大堆，排降序要建小堆。堆排序对数据不敏感。
2.时间复杂度：
3.空间复杂度：
4.稳定性：不稳定

代码实现

总结
1.归并排序的函数展开时间复杂度为，这个展开过程可以看成是一个递归树。 递归排序的核心主要在于 “并” 这个过程的实现，在这个过程中需要开辟一个临时的数组空间。归并排序无论是对完全有序的原始数据还是完全无序的原始数据都要一分为二进行下一步的操作，所以对数据不敏感。
2.时间复杂度：
3.空间复杂度：
4.稳定性：稳定
5.应用
①海量数据处理。
②使用归并排序的思想对链表进行排序
③使用归并排序中的merge思想解决数组的逆序对问题

核心思想： 每次从无序数组中选取一个元素称为分区点(pivot),将原集合中所有的元素放在分区点的左侧，将的元素放在分区点的右侧。 继续在左半区间和右半区间重复该过程，直到整个数组有序。

代码实现

上述方法是通过递归的方式实现的，在递归的过程中，如果把它看成是一颗二叉树的访问，那这就是前序遍历(根左右)，属于深度优先遍历，所以，我们可以借助栈来实现。 在递归展开中，不断变化的是数组的开始和结束索引，栈中保存的也应该是数组的开始和结束索引，所以每次栈压入和弹出的都是一对元素，这一对元素就表示当前要分区的左区间和右区间。

非递归实现

问题1： 上述挖坑法的分区方法中，在近乎有序的数组上进行排序时，会退化为的时间复杂度。原因在于分区点元素每次取的都是最左侧元素，若待排序集合近乎有序甚至完全有序，则二叉树会变为单枝树，此时二叉树的高度就会从原来的变为 。 所以，为了避免这个现象，需要尽可能随机的选择分区点，保证当前分区点的左侧和右侧都有元素。

优化挖坑法的分区函数

问题2： 在上述方法中，当区间包含了大量重复元素时，递归树又会退化为单枝树， 又变为了的时间复杂度，为了解决个问题，引入新区间，即就是在扫描时将所有等于v的元素设置为一个新区间， 在递归时只需要递归小于v和大于v的区间。

总结
1.快速排序的核心在于分区函数的实现，在挖坑法中，只考虑大于或小于pivot的元素，原因在于与分区点相等的元素无论在左侧还是右侧都不影响最终的排序结果。
2.时间复杂度：
3.空间复杂度：
4.稳定性：不稳定
5.应用
快排分区方法来寻找第k大元素，时间复杂度O(n)。

将要排序的集合分散在若干个桶(数组)中，子数组的内部排序好，整个数组就有序了。

a.待排序的数据能均分在若干个桶中；
b.桶和桶之间是相对有序的；

比如，以订单系统为例，现在有10GB的订单数据，按照订单金额对订单进行排序，订单金额从0-1000不等。

计数排序是桶排序的特殊情况，将数据划分到不同的桶中之后，桶内元素是相等元素，内部不需要再排序，只需要将原数组的所有元素扫描一遍之后划分到不同桶中即可。比如，现在按照年龄把所有中国人排序，此时将年龄相同的人放在同一个桶中。

基数排序最明显的特征就是可以按“位”排序，若最高位已经大于另一个元素，其他位数不需要再次比较；若最高位相同，继续比较下一位。位与位之间是独立的。
比如，现在按照身份证号对所有人进行排序，不同省份人的身份证号开头的数字是不同的。

外部排序中的三种排序算法时间复杂度近乎,对数据非常敏感。