开发语言的基础排序
使用场景之C语言的qsort()
C语言的qsort() :
- 当数据小的时候使用归并排序；
- 当数据大的时候使用快速排序。并且选择分区点的方法就是三数取中法。qsort()自己实现了一个堆，手动模拟递归，避免递归太深导致的堆栈溢出。
- 并且当要排序的区间元素个数<=4的时候，qsort()就退化为插入排序，不再使用递归做快排。(对于小规模数据的排序，O(n2) 的排序算法并不一定比 $O(nlogn)$排序算法执行的时间长。对于小数据量的排序，就选择比较简单、不需要递归的插入排序算法。)
- 插入排序使用了哨兵做优化，少了一次判断。
使用场景之Java的Arrays.sort()
Java的Arrays.sort()主要使用了双轴快速排序（by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch)，算法时间复杂度$O(nlogn)$。算法性能强于单哨兵的快排。但是并非单纯使用了一种算法就解决了所有排序问题，而是根据具体数组的情况采用合适的算法实现。
算法原理：
- 待排序元素length < 47， 使用插入排序；
- 待排序元素length < 286，使用双轴快速排序；
- 待排序元素length > 286, 检测数组的连续升序和连续降序性好不好，如果好的话就选择TimSort算法（（一种改进的归并排序算法），不好的话使用双轴快速排序。
可以看出整体思路与c语言的qsort()大致相同。
MySQL的排序
一句话概括：
- 当内存放得下待排序数据（待排序数据小于sort_buffer_size时候），使用快速排序；
- 当内存放不下，就使用归并排序算法外部排序临时文件。
- 如果是Top-K场景并且没有超过K个数据大小没超过sort_buffer_size还会使用优先队列排序算法，利用堆来线性时间取Top-K优化性能, 并且不需要临时文件。
具体还会根据select 的字段长度，避免内存装不下，分为了全字段排序和row id排序。rowid排序可以一次排序更多行，但是要回表取数据。
MySQL做排序是一个成本比较高的操作，涉及到内存是否可以放下待排序数据，回表等问题。因此，更多时候可以利用覆盖索引技巧避免执行排序。
Redis的ZSET排序
借助了跳表的数据结构实现了排序和$O(logn)$查找，跳表维持数据的动态插入和删除时间复杂度也是$O(logn)$。
之所以选择跳表这个数据结构。是因为Redis ZSET核心操作主要有下面这几个：
- 插入/删除/查找一个数据
- 按照区间查找数据。
对于按照区间查找数据这个操作，跳表可以做到$O(logn)$的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。这样做相比于红黑树会非常高效。
另外，Redis之所以使用跳表实现有序结合，还有其他原因，比如跳表容易实现，更加灵活。
高性能定时器
定时器需要判断每个任务是否到达任务执行时间，如果每过1s就扫描一遍任务列表的做法比较低效。
- 任务的约定执行时间距离当前时间可能还有很久，前面很多次扫描都是徒劳的；
- 每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时。
Java的定时任务@Scheduled 使用堆组织任务，不必每秒都轮询一次。用优先级队列来解决。按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（小顶堆的堆顶）存储的是最先执行的任务。
这样，定时起就不需要每隔1s就扫描一次任务列表里，它拿任务队首任务的执行时间点，与当前时间点相减，得到时间间隔T。 这个时间间隔T 就是从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样定时器就可以设定在Ts 之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。这样，定时器既不用间隔 1 秒就轮询一次，也不用遍历整个任务列表，性能也就提高了。
接口延时99分位
使用堆排序还可以解决求接口延时99分位值。
99分位概念：如果有 100 个接口访问请求，每个接口请求的响应时间都不同，比如 55 毫秒、100 毫秒、23 毫秒等，我们把这 100 个接口的响应时间按照从小到大排列，排在第 99 的那个数据就是 99% 响应时间，也叫 99 百分位响应时间。总结一下，如果有 n 个数据，将数据从小到大排列之后，99 百分位数大约就是第 n99% 个数据，同类，80 百分位数大约就是第 n80% 个数据。
求99分位延时：
维护两个堆，一个大顶堆，一个小顶堆。假设当前总数据个数是n, 大顶堆中保存n 99%个数据，小顶堆中保存n1%个数据。 大顶堆堆顶就是要找的99%响应时间。每次插入一个数据的时候，我们要判断这个数据跟大顶堆和小顶堆堆顶数据的大小关系，然后决定插入到哪个堆中。如果这个新插入的数据比大顶堆的堆顶数据小，那就插入大顶堆；如果这个新插入的数据比小顶堆的堆顶数据大，那就插入小顶堆。
但是，为了保持大顶堆中的数据占 99%，小顶堆中的数据占 1%，在每次新插入数据之后，我们都要重新计算，这个时候大顶堆和小顶堆中的数据个数，是否还符合 99:1 这个比例。如果不符合，我们就将一个堆中的数据移动到另一个堆，直到满足这个比例。移动的方法类似前面求中位数的方法。
通过这样的方法，每次插入数据，可能会涉及几个数据的堆化操作，所以时间复杂度是 O(logn)。每次求 99% 响应时间的时候，直接返回大顶堆中的堆顶数据即可，时间复杂度是 O(1)。