插入排序

直接插入排序

算法思想

1. 基本思想是每次将一个待排序的记录按其关键字大小插入前面已排好序的子序列，直到全部记录插入。
2. 
   要将元素L[i]插入已有序的子序列L[1…i-1]，需要执行以下操作（L[]表示一个表，L()表示一个元素。
   ①查找出L(i)在L[1…i-1]中的插入位置k
   ②将L[k…i-1]中的所有元素依次后移一个位置。
   ③将L(i)复制到L(k)。

模板代码

void InserSort(ElemType A[],int n){
    int i,j;
    for(int i = 2;i <= n;i ++){         //依次将A[2]~A[n]插入前面已排序序列
        if(A[i] < A[i - 1]){            //若A[i]关键码小于前驱，将A[i]插入有序表
            A[0] = A[i];                //复制为哨兵，A[0]不存放元素
            for(j = i - 1;A[0] < A[j];j --) //从后往前查找待插入位置
                A[j + 1] = A[j];        //向后挪位
            A[j + 1] = A[j];            //复制到插入位置
        }
    }
}

性能分析

1. 空间效率：仅使用了常数个辅助单元，因而空间复杂度为O(1).
2. 时间效率：在排序过程中，向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态
   ※ 在最好情况下，表中元素已经有序，此时每次插入一个元素，都只需比较一次而不用移动元素，因而时间复杂度为O(n)
   ※ 在最坏情况下，表中元素顺序刚好与排序结果中的元素顺序相反（逆序），总的比较次数达到最大，总的移动次数也达到最大，总的时间复杂度为O(n²)
   ※ 因此，直接插入排序算法的时间复杂度为O(n²)\
3. 稳定性：由于每次插入元素时总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个稳定的排序方法\
4. 适用性：直接插入排序算法适用于顺序存储和链式存储的线性表。为链式存储时，可以从前往后查找指定元素的位置。

折半插入排序

算法思想

1. 在直接插入排序的基础上，将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素。
2. 当排序表为顺序表时，可以对直接插入排序做如下改进：由于是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可统一地向后移动元素

模板代码

void InserSort(ElemType A[],int n){
    int i,j,low,high,mid;
    for(i = 2;i <= n;i ++){                     //依次将A[2]~A[n]插入到前面的已排序序列
        A[0] = A[i];                            //将A[i]暂存到A[0]
        low = 1;                                //设置折半查找的范围
        high = i - 1;                           //设置折半查找的范围
        while(low <= high){                     //折半查找(默认递增有序)
            mid = (low + high) / 2;             //取中间点
            if(A[mid] > A[0]) high = mid - 1;   //查找左半子表
            else low = mid + 1;                 //查找右半子表
        }
        for(j = i - 1;j >= high + 1;-- j)
        A[j + 1] = A[j];                        //统一后移元素，空出插入位置
        A[high + 1] = A[0];                     //插入操作
    }
}

性能分析

1. 比较次数：不难看出，折半插入排序仅减少了比较元素的次数，约为O(nlog₂ⁿ),该比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n,而元素的移动次数并未发生改变，她依赖于待排序表的初始状态
2. 时间复杂度：O(n²),对于数据量不是很大的排序表，折半插入排序往往能表现出很好的性能。
3. 稳定性：折半插入排序是一种稳定的排序方法。

希尔排序

算法思想

先将待排序表分割成若干形如L[i,i+di+2d,…,i+kd]的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序”时，再对全体记录进行一次直接插入排序。

模板代码

void ShellSort(ElemType A[],int n){
    //A[0]只是暂存单元，不是哨兵，当j <= 0 时，插入位置已到
    int dk,i,j;
    for(dk = n / 2;dk >= 1;dk = dk / 2)                             //增量变化（无统一规定）
        for(i = dk + 1;i <= n;++ i)
            if(A[i] < A[i - dk]){                                   //需将A[i]插入有序增量子表
                A[0] = A[i];                                        //暂存在A[0]        
                for(j = i - dk;j > 0 && A[0] < A[j];j -= dk)
                    A[j + dk] = A[j];                               //记录后移，查找插入的位置
                A[j + dk] = A[0];                                   //插入
            }//if
}

性能分析

1. 空间效率：仅使用常数个辅助单元，因而空间复杂度为O(1)。
2. 时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难。当n在某个特定范围时，希尔排序的时间复杂度为O(n^1.3)。在最坏情况下希尔排序的时间复杂度为O(n²)。
3. 稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变他们之间的相对次序，因此希尔排序是一种不稳定的排序方法。
4. 适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

习题总结

1. 直接插入排序在最坏的情况下要做n(n - 1 ) / 2 次关键字的比较。(不考虑于哨兵的比较)
2. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是(A)
   A. 直接插入排序 B. 简单选择排序 C. 快速排序 D. 归并排序
   ※ 由于这里的序列基本有序，使用直接插入排序算法的时间复杂度接近O(n)，而使用其他算法的时间复杂度均大于O(n)。
3. 对n个元素的顺序表采用直接插入排序算法进行排序，在最坏情况下所需的比较次数是( n(n - 1) / 2); 在最好情况下所需的比较次数是( n - 1)。
4. ※ 在排序过程中，每趟能确定一个元素在其最终位置的有冒泡排序、简单选择排序、堆排序、快速排序，其中前三者能形成全局有序的子序列，后者能确定枢轴元素的最终位置。
5. 在直接插入排序中，若待排序列中的最后一个元素应插入表中的第一个位置，则前面的有序子序列中的所有元素都不在最终的位置上
6. 希尔排序是对直接排序算法改进后提出来的，本质上仍属于插入排序的范围。
7. 虽然折半插入排序是对直接插入排序的改进，但它改进的只是比较的次数，而移动次数并未发生变化，时间复杂度仍为O(n²)。
8. 基于插入、交换、选择的三类排序方法中，通常简单方法是稳定的(直接插入、折半插入、冒泡、归并),但有一个例外就是简单选择，复杂方法都是不稳定的(希尔、快排、堆排)。
9. 每趟冒泡和选择排序后，总会有一个元素被放置在最终位置上、2路归并算法经过第二趟后应该是每4个元素是有序的
10. 折半插入排序的比较次数与初始序列初态无关，为O(nlog₂ⁿ)。而直接插入排序的比较次数与序列初态有关，为O(n)~O(n²)。