插入排序

直接插入排序

算法描述

将一条记录插入到有序表中，得到新的有序表。
将需要调整位置的元素暂存在r[0]处，然后再进行插入。

算法实现

void InsertSort(SqList &L) {
    for(i = 2; i <= L.length; i++)
        if(L.r[i].key < L.r[i - 1].key) {
            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[j + 1] = L.r[0];
        }
}

算法分析

1. 时间复杂度
   关键字比较次数KCN + 记录移动次数RMN = O(n²)
2. 空间复杂度
   只需要一个辅助空间r[0]，空间复杂度是O(1)

算法特点

1. 稳定排序。
2. 也适用于链式存储。
3. 适用于初始记录基本有序的情况。

折半插入排序

算法描述

将直接插入排序的查找方式改为折半排序，提高平均性能。

算法实现

void BInsertSort(SqList &L) {
    for(i = 2; i <= L.length; i++) {
        L.r[0] = L.r[i];
        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];
    }
}

算法分析

1. 时间复杂度
   折半插入的查找比直接插入快，但无法减少移动次数。
   插入第i个记录时需要经过floor(log2(i) + 1)次比较。
   关键字比较次数KCN + 记录移动次数RMN = O(n²)
2. 空间复杂度
   只需要一个辅助空间r[0]，空间复杂度是O(1)

算法特点

1. 稳定排序。
2. 不适用于链式存储。
3. 适用于初始记录无序、n较大的情况。

希尔排序

算法描述

本质上是一种分组插入。
事先确定一个增量数组，每次取出一个增量d，把所有间隔为d的元素分成一组，全部元素共分成d组，在每个组中分别进行直接插入排序。
直接插入排序是一种增量为1的希尔排序。

算法实现

void ShellInsert(SqList &L, int dk) {
    for(i = dk + 1; i <= L.length; i++)
        if(L.r[i].key < L.r[i - dk].key) {
            L.r[0] = L.r[i];
            for(j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
                L.r[j + dk] = L.r[j]; // 找到插入位置
            L.r[j + dk] = L.r[0];
        }
}

void ShellSort(SqList &L, int dt[], int t) {
    for(k = 0; k < t; k++)
        ShellInsert(L, dt[k]); // 增量为dt[t]
}

算法分析

1. 时间复杂度
   低于直接插入排序，具体难以计算，但n取向无穷时，时间复杂度为n(log2(n))²
2. 空间复杂度
   只需要一个辅助空间r[0]，空间复杂度是O(1)

算法特点

1. 不稳定排序。
2. 不适用于链式存储。
3. 增量值互质，必须递减，最后一个增量值必须为1.
4. 适用于初始记录无序、n较大的情况。