Sort Algorithm适用范围
面试的时候应该不会单独考察排序，但是很多问题需要在排序之后解决。更多的是运用到经典排序的算法思维，比如Quick Sort, Merge Sort，Heap Sort, Bucket Sort的算法思维，会运用到很多问题中
Arrays.sort(): Primitive vs Object
Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.
Sort Algorithm
- Array 和 List 常常运用相同的算法，在实现起来差别很大，由于数据结构本身的原因，复杂度也会不同
- 有时候要用到heap的时候，能熟练的写出Comparator 重载的函数，按照自己的规则。这里有Lambda 写法，可以简练
- Quick Sort 的 Partition； Merge Sort 的 Merge 是非常重要的基础算法思维应该能够很熟练的写出来，其中的Partition 需要能够掌握到随便写Quick Select
- 有些时候不同的排序算法适用于不同的场景，都应该能够知道什么时候用什么
- sort color -> bucket sort
- sot List -> merge sort
- wiggle sort -> just swap even
Sort Algorithm典型题目
Bucket Sort 的高境界 O(n) T O(n) S
序列已经排过序了。开辟新的数组，最后插入合并的结果 O(n)
Interval 系列问题的典型
- 用Heap 解决：
O(nlogn) T O(n) S - 用两个pointer 解决：
O(nlogn) T O(1) S
- collect both the row and column coordinates in sorted order
O(NM) S O(NM) T - 求中位数的问题，别忘了，只需要排一次序
O(NM) S O(NM)
- Sort之后 reorder
O (nlogn) - 这种方法及其复杂：
O(n)， 运用到Quick Select，很多的知识