数据结构
RISE ONLY THIS
.COM
RISE ONLY THIS
.COM
插入排序(Insertion Sort)是一类借助“插入”进行排序的方法，其基本思想是：每次将 一个待排记录按其关键字大小插入到一个已排好的有序子序列中.直到全部记录排好顺序。 插入排序的方法主要包括直接插入排序和希尔排序。
直接插入排序(Straight Insertion Sort)是插入排序中最简单的一种排序方法，需要解 决两个关键问题：一是如何构造初始有序子序列；二是如何査找待插记录插入位置。
① 构造初始的有序子序列。将n个待排序的记录序列{『】，&，…，玲}划分成有序区 和无序区，初始时有序区为待排序记录序列中的第一个记录，无序区包括所有剩余待排序的 记录。
② 查找待插入记录的插入位置。依次将无序区中的记录与有序区中记录关键字比较, 确定插入位置并插入记录，从而使无序区减少一个记录，有序区增加一个记录；重复该过 程，直到无序区中没有记录。
② 时间复杂度。
假设待排序记录个数为n,直接插入排序需要进行n-1趟排序。当初始文件记录为正 序时，即L. r[i]. key^L. key,内循环只进行1次关键字的比较，而不移动记录，因
此，总关键字比较次数为n-1,总记录移动次数为0。当初始文件记录为反序时，即L. r[i]. keyVL. r[i—1]. key,内循环需要将L. r[0]. key与有序子序列L. r[l.. i—1]中的i_]个 记录的关键字进行比较，并将L. r[l. . i一口中的i-1个记录后移，因此，总关键字比较次数 为(n + 2)(n—1)/2,总记录移动次数为(n—1) (n + 4)/2。当初始文件记录为随机时，即待 排序记录可能出现的各种排列的概率相同，关键字比较次数和记录移动次数均取上述最小 值和最大值的平均，约为n2/4o因此算法9-1的时间复杂度为0(/)。
③ 空间复杂度。
直接插入排序只需要一个记录的辅助空间，用来作为待插入记录的暂存单元和查找记 录的插入位置过程中的“哨兵”，因此算法9-1的空间复杂度为0(1)(称为就地排序)。
④ 方法适用性。
算法9-1是一种稳定的排序方法。该方法简单且容易实现，当序列中的记录基本有序 或待排序记录较少时，它是最佳的排序方法。但当待排序的记录个数较多时，大量的比较和 移动操作使直接插入排序算法的效率降低。
所需要的工作量来区分，可以将排序方法分为简单排序法，其时间复 杂度为0(/)；先进排序法，其时间复杂度为O(nlogm)；基数排序法，其时间复杂度为 O(dXn)(d为单逻辑关键字中关键字的个数)。通常，在排序过程中需要进行两种基本操作：
(1) 比较：即比较两个记录关键字大小。该操作对大多数排序方法来说都是必要的。
(2) 移动：将记录从一个位置移动至另一个位置。该操作可以通过改变记录的存储方 式来予以避免。
通常，待排序记录序列有3种存储方式。
(1) 以顺序表存储待排序记录序列。待排序记录存储在一组地址连续的存储单元中， 类似于线性表的顺序存储结构，在序列中相邻的两个记录，其存储位置也相邻。在这种存储 方式中，记录之间的次序关系由其存储位置决定，实现排序必须移动记录。
(2) 以静态链表存储待排序记录序列。待排序记录存储在一个静态链表中，在这种存 储方式中，记录之间的次序关系由指针指示，实现排序不需要移动记录，仅需要修改指针即 可。该存储方式下的排序又称为链表排序。
(3) 以顺序表存储待排序记录序列，并另设一个指示各个记录存储位置的地址向量。 在这种存储方式中，实现排序不需要移动记录本身，而移动地址向量中这些记录的“地址”, 在排序之后再按照地址向量中的值调整记录的存储位置。该存储方式下的排序又称为地址 排序。
排序的性能分析主要从两个方面考虑：一个是时间复杂度，另一个是空间复杂度。
