排序算法的知识框架

💡这个知识体系要牢记！

基本概念

定义

什么是排序呢？顾名思义，排序，就是重新排列表中的元素，使元素按照一定的原则使其关键字变得有顺序的过程。

在数据结构这门课程中，排序的规则主要是从大到小或者从小到大排序。

算法的稳定性

稳定性又是何如定义的呢？怎么才能算是稳定呢？

在待排序如果待排序中有2个元素 $Ele_i$ 和 $Ele_j$ 。他们对应的关键字相同即 $Key_i = Key_j$，且在排序前 $Ele_i$ 在 $Ele_j$ 的前面，若使用某个排序算法排序后，$Ele_i$ 仍然在 $Ele_j$ 的前面，我们就认为这个算法是稳定的。反之，即算法不稳定。

说简单点，排序算法的稳定性是指经过排序后，能是关键字相同的元素保持原顺序中的相对位置不变。

两种解释，找一个自己能理解的即可。

算法的分类

根据排序过程中，数据元素是否全在内存中，可以分为内部排序和外部排序。

• 内部排序：顾名思义，指的是排序期间，所有元素全部都在内存中的排序算法。
• 外部排序：指的是在排序期间，元素没有全部存在内存中，有部分元素存在外存里面，因此，在排序过程中需要不断的进行I/O操作。

在内部排序中，又可以根据算法的特征进行细分，主要有五大类，分别是：插入排序、交换排序、选择排序、归并排序、基数排序。

算法的衡量标准

排序算法这么多，我怎么衡量算法的性能呢？

为了衡量内部排序算法的性能，一般使用算法的时间复杂度与空间复杂度作为衡量标准。