数据结构中几种排序算法（内部排序）的说明与比较（一）

是一种最简单的排序方法，基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。直接插入排序时，所需进行关键字间的比较次数和移动记录的次数约为n²/4，因此，直接插入排序的时间复杂度为O(n²)。

当待排序记录的数量n很小时，直接插入排序是一种很好的排序方法，当待排序序列中的记录数量n很大时，则不宜采用直接插入排序。因而，可得下列各种插入排序的方法。

在一个有序表中，查找操作由折半查找来实现，由此进行的插入排序称为折半查找。减少了关键字间的比较次数，但记录的移动次数不变。因此，折半插入排序的时间复杂度仍为O(n²)。

是在折半插入排序的基础上再改进之，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。具体做法是：另设一个和L.r同类型的数组d，首先将L.r[1]赋值给d[1]，并将d[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中的第二个记录起依次插入到d[1]之前或之后的有序序列中。先将待插记录的关键字和d[1]的关键字进行比较，若L.r[i].key 在实现算法时，可将d看成是一个循环向量，并设两个指针 first和final分别指示排序过程中得到的有序序列中的第个记录和最后一个记录在d中的位置。在2-路插入排序中，移动记录的次数约为n²/8。因此，2-路插入排序只能减少移动记录的次数，而不能绝对避免移动记录。并且，当L.r[1]是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去它的优越性。因此，若希望在排序过程中不移动记录，只有改变存储结构，进行表插入排序。

为了插入方便，设数组中下标为0的分量为表头结点，并令表头结点记录的关键字取最大整
数MAXINT。则表插入排序的过程描述如下：先将静态数组下标为1的分量(结点)和表头结点构成一个循环链表，然后依次将下标为2至n的分量(结点)按记录关键字非递减有序插入到循环链表中。

又称缩小增量排序，基本思想：先将整个待排序序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
注：有关于内部排序的算法还有很多，将在下一篇文章中加以说明。