# 2. 排序算法 #### 一. 定义 排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程。 \*\*排序的分类：\*\* 1. 内部排序:指将需要处理的所有数据都加载到内部存储器中进行排序。 2) 外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。 \*\*常见的排序算法分类:\*\* !\[图片1\](https://hgh-typora-image.oss-cn-guangzhou.aliyuncs.com/img/%E5%9B%BE%E7%89%871.png) #### 二. 算法的稳定性 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r\[j\]之前，而在排序后的序列中，r\[i\]仍在r\[j\]之前，则称这种排序算法是稳定的；否则称为不稳定的 例如，序列5 7 5 4 1 9，若经过排序算法排完序后，原序列中2个5的相对前后顺序不被破坏（即第一个5仍在前面，第二个5仍在后面），那么该算法就是个稳定的排序算法，否则就是不稳定的排序算法。 \*\*常见的排序算法的稳定性\*\* 堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法，而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 #### 三. 内排序和外排序 \*\*内排序：\*\*所有排序操作都在内存中完成； \*\*外排序：\*\*由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；