Sort

数组排序

148. 排序链表

• 冒泡排序
• 选择排序
• 堆排序
• 插入排序
• 希尔排序
• 归并排序

快速排序

1. ==时交换好处是避免了很多没用的交换。坏处是移动到中间的机会减小了。
2. 当数据规模小时，可以直接调用普通排序，定义一个阈值cutoff。

桶排序

计数排序

适用于数据有范围的情况。数据大效果明显。

基数排序

1. 记得要clear。

快速选择Parition	堆排
时间$n$. 第几大的元素，仅适用静态元素	时间:$n\log{n}$.可适用于动态元素

• 215. 数组中的第K个最大元素

外排序

以上都是内部排序。

外排序（External sorting）是指能够处理极大量数据的排序算法。通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。

常用的外排序有外归并排序，原理和内归并排序一样，不过每一轮结果写入到文件，还有外分配排序，其原理类似于内排序中的桶排序。