【算法设计与分析】4.2 插入排序

2023-05-16

说明：参考书目为《Computer Algorithms --- Introduction to Design and Analysis》（第三版）Sara Baase, Allen Van Gelder

部分内容参考自大工林晓惠老师的课程【算法设计与分析】讲解。林老师讲算法非常细致，让人很容易理解，推荐一波~

（如部分内容涉及侵权，请联系我删除，谢谢）

之前的文章请见：

【算法设计与分析】如何分析一个算法

之后的文章请见：

【算法设计与分析】(习题4.2-4.5) 冒泡排序

本篇文章目录

第四章排序算法

4.1 章节介绍

1. 定义

2. 章节结构

3. 重点内容

4.2 插入排序

1. 定义

2. 排序过程示例

3. 算法代码

4. 分析O(n), W(n), A(n)

5. 此类算法的性能分析

第四章排序算法

4.1 章节介绍

1. 定义

对n个数据元素按照关键字key递增 / 递减排列

2. 章节结构

注意：在基于比较操作的排序算法中，一般是多次比较后移动数据，即数据移动的次数在量级上不会超过比较次数，所以本系列文章大多数时候只分析比较次数。

3. 重点内容

①算法时间复杂度的分析——证明

②算法改进

③算法正确性证明

4.2 插入排序

（章节号对应参考书目，前三章都是基础内容，可以查阅数据结构相关知识，本系列文章从第四章排序算法开始）

1. 定义

将待排序的数据元素按其关键字的大小依次插入到前面已排序的适当位置上

2. 排序过程示例

3. 算法代码

教材中算法的核心思想是构造一个shiftVac函数：

int shiftVac(Element[] E, int vacant, Key x)
    条件：vacant非负
    return -> x排序后的位置xLoc
    算法核心：1. xLoc之前的数据位置不变；2. xLoc后至原x位置(vacant)-1的数据均向后移动一位

教材给了两种算法思路，第一种是递归，第二种是迭代。

两种方法都是基于前面的数据已经排好序的前提下，试图在排好序的序列中找到合适的位置。只要前面有一个元素不大于自身，就将当前位置作为合适位置，否则将数据向后挪动一位。

// 递归
int shiftVac(Element[] E, int vacant, Key x){
    int xLoc;
    if(vacant ==0)
        xLoc = vacant;
    else if(E[vacant-1].key <= x)
        xLoc = vacant;
    else
        E[vacant] = E[vacant-1];
        xLoc = shiftVac(E, vacant-1, x);
    return xLoc;
}

// 迭代
int shiftVec(Element[] E, int vacant, Key x) {
    int xLoc = 0;    // Assume failure. 始终未找到key<=x，即x应排在第一位
    while(vacant > 0)
    {
        if(E[vacant-1].key <= x)
        {
            xLoc = vacant;    // Succeed.
            break;
        }
        E[vacant] = E[vacant-1];
        vacant --;    // Keep looking.
    }
    return xLoc;
}

insertionSort是调用shiftVec对整个数组进行插入排序的函数：

其中，Element[] E是待排序的数组，也是排好序输出的数组；n是数组大小

void insertionSort(Element[] E, int n) {
    int xindex;
    for(xindex=1; xindex<n; xindex++)
    {
        Element current = E[xindex];
        Key x = current.key;
        int xLoc = shiftVac(E, xindex, x);
        E[xLoc] = current;
    }
    return;
}

4. 分析O(n), W(n), A(n)

空间：O(1)【需要一个额外的辅助空间】

时间：

1）最好情况：O(n) 【待排序的数据已经有序， n-1次数据比较，0次数据移动】

2）最坏情况： $W(n)=\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}\in \Theta (n^{2})$ 【待排序的数据逆序，第二个数据向前比较一次，第三个数据向前比较两次……第n个数据向前比较n-1次】

3） 平均情况：【假定①所有可能的输入都以同等概率出现②每个键值唯一，计算每种输入的比较次数并求和，然后除以输入的数量，即得到平均的时间复杂度】

用下面一张图说明什么是所有可能的输入：

A(n)的推导过程：

5. 此类算法的性能分析

1）此类算法特点：①基于比较、数据移动完成排序 ②一次比较操作后不发生数据移动或仅仅交换一对相邻的数据元素

2）逆序概念：假定排列 $\pi$ ：2, 4, 1, 5, 3。 $\pi$ (1)=2 即序列第一个位置的数据为2，同理 $\pi$ (2)=4。

若排列 $\pi$ 前面的数据大于后面的数据[ i<j， $\pi$ (i)> $\pi$ (j) ]，则是一对逆序。例如排列2, 4, 1, 5, 3 有4 对逆序：(2, 1), (4, 1), (4,3)和(5, 3)

3）性能分析：对排列 $\pi$ 进行排序 <=> 消除 $\pi$ 中所有逆序

如果排序时一次数据比较最多消除一对逆序 -> 有多少对逆序就要进行多少次比较

①计算最坏情况W(n)

对于有n个元素的序列：两两一对，一共有 $\frac{n(n-1)}{2}$ 个有序对（此为有序对最多的情况，即降序）

根据上面的假设，一次数据比较最多消除一个逆序，所以最坏情况 $W(n)=\frac{n(n-1)}{2} \in \Theta (n^2)$

②计算平均情况A(n)

设有一个排列 $\pi$ ： $\pi$ (1)， $\pi$ (2)，...， $\pi$ (n)。颠倒该排列 $\pi$ 所有数据位置得到transpose排列： $\pi$ (n)，...， $\pi$ (2)， $\pi$ (1)。

则在 $\pi$ 中的逆序对在transpose中正序，在 $\pi$ 中的正序在transpose中逆序 -> $\pi$ + transpose的逆序对之和=n(n-1)/2 -> 平均一个排列 $\pi$ 存在n(n-1)/4个逆序

根据上面的假设，一次数据比较最多消除一个逆序，所以平均情况 $A(n)=\frac{n(n-1)}{4}$

4）定理4.1（由(3)推理得到）

任何一个基于关键字的比较且每一次比较最多消除一个逆序的排序算法，最坏的情况下至少比较n(n-1)/2次，平均情况至少比较n(n-1)/4次。

注：“至少”指的是算法设计得到，用相应的次数比较即可排好序，若是算法设计冗余，可能会用更多的比较次数才能排好序。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)