• 直接插入排序程序：

void InsertSort(SqList &L)

 { // 对顺序表L作直接插入排序。算法10.1

   int i,j;

   for(i=2;i<=L.length;++i)//哨兵在0，所以从2开始排序

     if (L.r[i].key < L.r[i-1].key) // "<",需将L.r[i]插入有序子表，确保待插入数据小于之前的最后一个，否则就不需要排序，进行下一个

     {

       L.r[0]=L.r[i]; // 待插入的数据复制为哨兵

       for(j=i-1; L.r[0].key < L.r[j].key;--j)// 将每个数据和哨兵从右向左进行比较，直到哨兵大于该比较值

         L.r[j+1]=L.r[j]; // 记录后移

       L.r[j+1]=L.r[0]; // 插入到正确位置

     }

 }

• 总结：时间复杂度O(n²)，空间复杂度O(1)。
• 思想：L.r[0]用于存储待插入的数据，即哨兵。先将第一个数据看成有序的序列，故从第二个开始开始比较，共需要n-1趟。需将L.r[i]插入有序子表，确保待插入数据小于之前的最后一个，即有序子序列的最后一个。否则就不需要排序，因为改数已经大于最后一个，则为子序列的最大值，应该放于最后。进行此趟排序前，先将i拷入哨兵，之后将每个数据和哨兵从右向左进行比较，若小于该值则将其后移，否则将哨兵拷入该位置即可，本趟排序结束。

评论