9.2　直接插入排序

在内部排序的众多算法中,直接插入排序是一种最为简单的排序方法,也是插入排序算法中较为常用的一种。

插入排序算法的基本思想是:每次将一个待排序的记录,按照其关键字插入到已经排好序的记录序列中的适当位置,直到所有记录全部插入完为止。通俗地讲,插入排序就是不断地扩大有序区内记录数目并减少无序区内记录的数目,每次将无序区内的一个记录插入到有序区内的适当位置形成新的有序区,直至无序区内所有记录被移除为止,最终所得到的有序区内的记录序列即是排好序的记录序列。常用的插入排序算法有直接插入排序、折半插入排序、表插入排序和希尔插入排序等,本章将详细介绍直接插入排序。

直接插入排序的基本思想是:将所有的n条记录按照顺序依次存储在数组R[n＋1]中的R[1]到R[n]中；首先取出记录R[1],由于只有一个记录,故而可以视该区内的记录为有序的；假设在第i（2≤i≤n）次操作前,有序区内已经存在的i－1个记录是有序的；然后每次取出一个记录R[i]（2≤i≤n）,并将取出的记录R[i]保存在R[0]中；再用R[0]的关键字依次与有序区中的记录的关键字逐个比较,比较的次序为从R[i－1]到R[1],并将关键字大于R[0]的关键字的记录逐个向后移动一个位置,直到找到一个合适的位置插入记录R[0]；重复上述步骤,直至所有无序区中的记录全部被插入到有序区中,则排序完成。

直接插入的基本操作步骤如下。

（1）获得无序记录序列{R[1],R[2],…,R[n]},并分成两个区域,有序区为{R[1]},无序区为{R[2],R[3],…,R[n]}。

（2）在无序区中取R[i]（2≤i≤n）,执行R[0]＝R[i]。

（3）在有序区{R[1],R[2],…,R[i－1]}中查找记录R[0]插入的位置,并将插入点之后的记录依次逐个向后移动一个位置。

（4）将记录R[0]插入到有序区。

（5）重复步骤（2）、（3）、（4）直至无序区中所有记录都被插入到有序区。

直接插入排序算法可描述如下。

由上述程序可以看出,在程序开始时,有序区内只有一个记录R[1],然后需要将无序区内的记录R[2]～R[n]依次插入到有序区内。首先,在无序区内取出记录R[i]之前,有序区内存在的i－1个记录已经是按关键字有序排列,取出第i个记录并将其存入R[0]中；然后用R[0].key依次与R[i－1].key,R[i－2].key,…,R[1].key进行比较,如果R[0].key＜R[j].key（1≤j≤i－1）,则将R[j]后移一个位置；如果出现R[0].key≥R[j].key（1≤j≤i－1）,则找到记录R[0]应该插入的位置,在数组中的下标为j＋1,此时将R[0]（待排记录中的R[i]）直接插入即可；重复上述的步骤,直至无序区内的记录全部插入到有序区中为止。

【算法分析】

（1）稳定性　由于该算法在循环查找插入点的过程中,循环终止的情况之一为遇到记录的关键字值相等,因此不会把两个关键字相等的记录进行位置的交换,所以算法为稳定的。

（2）空间复杂度　在整个算法的执行过程中,使用的辅助存储空间仅为一个,即R[0]所占据的存储空间,故而空间复杂度为O（1）。

（3）时间复杂度　整个算法执行for循环n－1次,每次循环中的基本操作是比较和移动,其总次数取决于数据表的初始特性,可能有以下几种情况。

①最好情况。当初始记录序列的关键字已经是递增排列时。虽然算法中while语句的循环体执行次数为0,但是在一趟排序中关键字的比较次数为1,即R[0]的关键字与R[j]的关键字比较,而移动次数为2,即R[i]移动到R[0]中,R[0]移动到R[j＋1]中。所以,整个排序过程中的比较次数和移动次数分别为（n－1）和2（n－1）,因而其时间复杂度为O（n）。

②最坏情况。当初始数据序列的关键字序列是递减排列时,进行第i次排序时,while语句内的循环体执行次数为i。因此,关键字的比较次数为i,而移动次数为i＋1。所以,整个排序过程中的比较次数和移动次数分别为:

③一般情况下,可认为出现各种排列的概率相同,因此取上述两种情况的平均值作为直接插入排序关键字的比较次数和记录移动次数,其值约为n²/4,所以其时间复杂度为O（n²）。

由上述分析可知,当待排序列基本为有序序列时,该算法执行效率较高。

【例9－1】　假设有无序记录9个,它们的关键字分别为29＊,18,20,19,38,30,23,31,29,用直接插入法进行排序。

直接插入排序过程如下所示,其中方括号【】内为待插入记录的关键字,即存入到R[0]中的记录的关键字,圆括号（）内为排好序的记录的关键字。