1. 排序的基本概念
1) 排序过程可以是物理重排,也可以是通过指针,使得逻辑有序.
2) 内部排序和外排序:所有的记录都在内存中,这样的排序为内部排序;如果排序的过程中要不断的进行内存与外存的交换,这样的排序为外部排序.
2. 插入排序:
1) 直接插入排序:稳定的排序算法，时间复杂度：最好情况O(n)；最差情况O（n^2）；平均情况为O（n^2）;
2) 折半插入排序：稳定的排序算法
3) 希尔排序：不稳定的排序算法，时间复杂度为：没有最好情况；最差情况O（nlog2n）；平均情况为O(nlog2n)。
3. 交换排序
1) 气泡排序：稳定的排序算法，时间复杂度为:最好情况O（n）；最差情况O(n^2);平均情况为O（n^2）.
2) 快速排序:不稳定的排序算法，时间复杂度为：最好的情况O(nlog2n)；最差情况O(n^2)，平均情况为O(nlog2n)；
4. 选择排序
1) 简单选择排序：不稳定的排序，时间复杂度为：最好情况O(n^2);最差情况为O（n^2）;平均情况为O（n^2）;与关键字的初始排列无关。
2) 堆排序:不稳定的排序，时间复杂度为：最好情况O（nlog2n）；最差情况为O（nlog2n）；平均情况O（nlog2n）；
5. 二路归并排序
稳定的排序，时间复杂度为：最好情况O（nlog2n）；最差情况为O（nlog2n）；平均情况O（nlog2n）；
6. 基数排序
稳定的排序，时间复杂度为：最好情况O（d（n+rd））；最差情况为O（d（n+rd））；平均情况O（d（n+rd））；