稳定性是指：排序时值相同的元素在排序后能否保证其相对次序不变（可理解为网购时先将价格由低到高排列，在以质量好坏进行排序，实现物美价廉）
| 时间复杂度 | 空间复杂度 | 稳定性 | |
| 选择排序 | O() | × | |
| 冒泡排序 | O() | √ | |
| 插入排序 | O() | √ | |
| 归并排序 | √ | ||
| 快排（3.0） | × | ||
| 堆排序 | × |
分析：
1.前三个排序都是基于比较的排序，基于比较的排序的时间复杂度不能做到<
2.时间复杂度的三个算法不能兼顾空间复杂度小和稳定性。在实际设计时，一般选择快排，因为其时间复杂度常数项较小，速度较快，考虑稳定性选择归并排序，有空间限制，选择堆排序。
坑：
1.归并排序的额外空间复杂度可为o（1），但会因此丧失稳定性，“内部缓存法”，较难
2.原地归并排序可以使得空间复杂度为o（1），但会使得时间复杂度为O()
3.快排可以做到稳定性，但会使得空间复杂度为
题目：奇数放数组左边，偶书放数组右边，且要求原有的相对次序不变。（这是一个0-1问题，快排无法达到，因为其进化过程做不到稳定性）
工程上对排序的改进：大样本，调度时一般选择快排，小样本时，选择插入排序。综合排序，利用各自的优势（时间快，空间低，以及稳定性的考虑）
Java中的Array.sort()在基础类型时选择快排，非基础类型时选择归并保持稳定性
哈希表HashSet
HashMap
HashMap由增/更新（add）、删（remove）、查（containkey）、拿（get）key的value
哈希表的时间复杂度是常数级别的，能实现增删改查功能
有序表有序表的性能比哈希表差，是
和哈希表一样，分为TreeSet和TreeMap，内部按照Key来组织排序
注意：当放如有序表的东西是基本数据类型的时候，可以实现比较。当放入有序表的东西不是基本数据类型时，要提供比较器。
操作：
1.put（k key， V value） :将（key，value）加入表中，也可实现将key更新成value
2.V get（k key）：根据key查询value返回
3.remove（k key）：删去key的记录
4.boolean containskey（k key)：查
5.k firstkey：所有键值的排序结果中，最小（左）的那个
6.k lastkey：所有键值的排序中，最大（右）的那个
7.k floorkey（k key）：如果表中存过key，则返回key，否则返回所有键值的排序结果中，key的前一个（小于等于）
8.k ceilingkey（k key）：大于等于（后一个）
链表重要技巧：额外数据结构记录（哈希表）、快慢指针
题目
