从今天开始我们就要开始学习排序算法啦！

排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。为了查找方便,通常希望计算机中的表是按关键字有序的。

除了我们之前了解的时间复杂度和空间复杂度来判断一个算法的好坏之外，在排序算法这里我们引入一个新的判断标准——稳定性。

算法的稳定性。若待排序表中有两个元素R;和R，其对应的关键字相同即key~i~= key~j~,且在排序前R~i~在R~j~的前面， 若使用某一排序算法排序后，R~i~仍然在R~j~的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。需要注意的是，算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。如果待排序表中的关键字不允许重复，则排序结果是唯一的，那么选择排序算法时的稳定与否就无关紧要。

这里需要注意的是我们上一篇博客在图的应用中的拓扑排序他并不是我们这里严格意义上的排序算法。

要将元素L(i)插入已有序的子序列[1……i-1]，需要执行以下操作(为避免混淆，下面用L[ ]表示一个表，而用L()表示一个元素):

为了实现对L1..n]的排序,可以将L(2) ~L (n)依次插入前面已排好序的子序列，初始L[1]可以视为是一个已排好序的子序列。上述操作执行n- 1次就能得到一个有序的表。插入排序在实现上通常采用就地排序(空间复杂度为0(1))，因而在从后向前的比较过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

假定初始序列为49, 38, 65, 97 ,76, 13, 27,49，初始时49可以视为一个已排好序的子序列，按照上述算法进行直接插入排序的过程如图所示，括号内是已排好序的子序列。

空间效率:仅使用了常数个辅助单元，因而空间复杂度为0(1)。

时间效率:在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态。在最好情况下，表中元素已经有序，此时每插入一个元素，都只需比较一一次而不用移动元素，因而时间复杂度为0(n)。在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反(逆序)， 总的比较次数达到最大，总的移动次数也达到最大，总的时间复杂度为0(2)。平均情况下，考虑待排序表中元素是随机的，此时可以取上述最好与最坏情况的平均值作为平均情况下的时间复杂度，总的比较次数与总的移动次数均约为n^2^ /4。