排序的基本概念
按数据存储介质：内部排序和外部排序
按比较器个数：串行排序和并行排序
按主要操作：比较排序和基数排序
插入排序：
基本思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。
基本操作：有序插入
直接插入排序---采用顺序查找法查找插入位置
复制插入元素
记录后移，查找插入位置
插入到正确位置
直接插入排序：使用“哨兵”
复制为哨兵
记录后移，查找插入位置
插入到正确位置
时间复杂度：O(n²)
折半插入排序：查找插入位置时采用折半查找法
折半查找比顺序查找快
希尔排序：
基本思想：先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
特点：缩小增量，多遍插入排序
空间复杂度：O(1)
时间复杂度是n和d的函数：O(n^1.25)~O(1.6n^1.25)
是一种不稳定的排序方法
冒泡排序：每趟不断将记录两两比较，并按“前小后大”规则交换
时间复杂度：
最好情况（正序）：比较次数：n-1；移动次数：0
最坏情况（逆序）：比较次数：1/2（n²-n）；移动次数：3/2（n²-n）
快速排序：
基本思想：
任取一个元素为中心；
所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
对各子表重新选择中心元素并依此规则调整；
直到每个子表的元素只剩一个
具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。
快速排序是一种不稳定的排序方法。
简单选择排序
基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。
堆排序：
堆实质是满足如下性质的完全二叉树：二叉树中任一非叶子结点均小于（大于）它的孩子结点
归并排序：
基本思想：将两个或两个以上的有序子序列“归并”为一个有序序列
在内部排序中，通常采用的是2-路归并排序。
基数排序：
基本思想：分配+收集
也叫桶排序或箱排序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。
基数排序：数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百...进行排序