2. 排序算法

一. 定义

​ 排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。

排序的分类：

1. 内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序。

2) 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

常见的排序算法分类:

二. 算法的稳定性

​ 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的

​ 例如，序列5 7 5 4 1 9，若经过排序算法排完序后，原序列中2个5的相对前后顺序不被破坏（即第一个5仍在前面，第二个5仍在后面），那么该算法就是个稳定的排序算法，否则就是不稳定的排序算法。

常见的排序算法的稳定性

​ 堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。

三. 内排序和外排序

内排序：所有排序操作都在内存中完成；

外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；