插入排序

基本思想

• 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

即边插入边排序，保证子序列中随时都是排好序的

基本步骤：

1. 在 R[1..i-1]中查找 R[i]的插入位置；R[1..j].key <= R[i].key < R[j+1..i-1].key

2. 将 R[j+1..i-1]中的所有记录均后移一个位置；

3. 将 R[i] 插入(复制)到 R[j+1]的位置上。

直接插入排序（基于顺序查找）

排序过程：整个排序过程为 n-1 趟插入，即先将序列中第 1 个记录看成是一个有序子序列，然后从第 2 个记录开始，逐个进行插入，直至整个序列有序。

算法描述

• 从 R[i-1]向前进行顺序查找，监视哨设置在 R[0]

• 关键字大于 R[i].key 的记录向后移动 if( L.r[i].key<L.r[i-1].key){R[0] = R[i]; // 设置“哨兵”R[i] = R[i-1];for (j=i-2; R[0].key<R[j].key; --j)

• R[j+1] = R[j];

• 循环结束表明 R[i]的插入位置为 j+1L.r[j+1]=L.r[0]; //插入到正确位置

算法实现

void InsertSort(SqList &L){  int i, j;  for(i = 2; i <= L.length; ++i){    if(L.r[i].key < L.r[i - 1].key){      // 将L.r[i]插入有序子表      L.r[0] = L.r[i];  // 复制为哨兵      L.r[i] = L.r[i - 1];      for(j = i - 2; L.r[0].key < L.r[j].key; --j)        L.r[j + 1] = L.r[j];  // 记录后移      L.r[i + 1] = L.r[0];  // 插入到正确位置    }  }}

算法分析

时间复杂度 —— O(n^2)

• 最好的情况（关键字正序）

• 比较次数：

• 

• 移动次数：

• 

• 最坏情况下（关键字逆序）

• 第 i 趟比较 i 次，移动 i+1 次

• 比较次数：

• 

• 移动次数：

• 

平均时间复杂度：O(n^2)

空间复杂度 —— O(1)

• 需要一个记录的辅助空间 r(0)

稳定性

• 稳定

特点：简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。

折半插入排序（基于折半查找）

基本思想：因为 R[1..i-1] 是一个按关键字有序的有序序列，则可以利用折半查找实现“在 R[1..i-1]中查找 R[i]的插入位置”，如此实现的插入排序为折半插入排序。

算法实现

void BiInsertionSort(SqList &L){  for(i = 2; i <= L.length; ++i){    L.r[0] = L.r[i];  // 将L.r[i] 暂存到 r[0]    // 在 L.r[1..i-1]中折半查找插入位置    low = 1;    high = i - 1;    while(low <= high){      m = (low + high) / 2;  // 折半      if(L.r[0].key < L.r[m].key)        high = m - 1;  // 插入点在低半区      else low = m + 1;  // 插入点在高半区    }    for(j = i - 1; j >= high + 1; --j)      L.r[j + 1] = L.r[j];    L.r[high + 1] = L.r[0];  }}

算法分析

• 时间复杂度为 O(n^2)

• 最佳情况下总时间代价为 O(nlog2n)

• 最差和平均情况下仍为 O(n^2)

• 空间复杂度为 O(1)

• 是一种稳定的排序方法