简单排序
- 统一接口
- 默认从小到大排序
- 内部排序：内存足够存储所有数据，在内存中对数据进行排序操作
- 稳定性：如果排序前两个相等的数据是挨在一起的，必须对两个都叫小明的人排序，起初小明1在小明2左边，那么排完后还是得在他左边，不能变成右边。
冒泡排序
- 加了一个flag来标记数据是否已有序，如果一趟排序中全程没有进行交换，那么flag为0，说明数据已有序，可以结束了。
- 缺点：耗时
- 优点：简单，适用于单向链表的排序
- 算法实例：第九讲->9.1第2节
插入排序
- 稳定性：元素不比当前元素大的时候不用往后移，所以是稳定的。
- 比冒泡法好，因为冒泡需要交换，交换需要3步，而这里往后移只需比它大的元素往后移，都移完了再把当前元素插入就行了。
- 算法实例：第九讲->9.1第3节
- 用冒泡和插入分别对这串数据排序的话，交换次数都是9次，而这里面逆序对的个数也是9次。因为美交换一次消去一个逆序对，因此有几个逆序对就需交换几次。
- I是原始序列中逆序对的个数。插入排序不仅跟数据个数有关，还跟逆序对个数有关。
快速排序
分而治之
- 算法实例：第十讲->10.1第1小节
选主元
- 如果数据已经排好序，但是主元都是选第一个的话，那就相当于没有排序。
- 随机取的话，随机函数是很费时的。
- 我们可以取第一个元素、中间一个元素和最后一个元素中第二大的。
- 利用算法把这三个元素从小到大排序，然后等一下就返回那个第二大的。不过等一下是要等什么呢？我们先把中间这个第二大的元素换到最后一个元素的前一个元素（等一下就返回倒数第二个元素），因为我们知道第一个元素一定比等下作为枢纽的元素小，最后一个元素一定比它大，如果规定相等就放在后面的话，那么第二大元素本身就是枢纽，我们知道肯定是要放在后面的，所以我们提前把它放在后面，那等一下只比较第二个到倒数第三个元素与枢纽的大小关系就好了，而中间那个元素就换成了原来倒数第二的元素。否则中间那个元素本身就是枢纽，是已经知道大小关系的，却还要再比一次，就有点浪费时间了。
小规模数据的处理
- 分而治之将数据分得很小的时候调用简单排序，不要一直递归下去。
算法实现
- 要在外面套一个壳，否则不符合接口规范。
- 算法实例：第十讲->10.1所有小节
表排序
- 一种间接排序
- 不需要动元素本身，只是动元素的指针。也就是用它们的下标代替元素本身来排序，下标排在哪个位置，元素就在哪个位置。
物理排序
- 就是排完下标后怎么排元素
- 我们有结论：N个数字的排列由若干个独立的环组成；比如，表的第一个元素是3，第三个元素是1，…，这样下去一定会回到3的，也就是形成了一个环。
- 那这样我们可能会陷入环的死循环里，所以我们要判断什么时候环结束了。可以把访问过的table的元素设置为和A下标一样，这样在访问前判断一下元素和下标是否一样就知道环是否结束了。
复杂度分析
- 算法实例：第十讲->10.2第1、3小节
桶排序
- 给每个程序都设置个桶
- 但是如果桶很多但是人很少怎么办呢？
- 算法实例：第十讲->10.3第1小节
基数排序
- 分桶跟进制有关系，这里是10进制就分10个桶
- 如果桶的个数非常小的话，那么复杂度接近线性复杂度。
- 算法实例：第十讲->10.3第2小节
在多关键字排序上的应用
- 算法实例：第十讲->10.3第3小节
