2020-08-31

插入排序

插入排序基本原理

插入排序的工作方式就像是打扑克牌一样，左手的牌都是有序的，而右手的牌都是无序的。对于右手的任意一张牌，从右向左遍历左手的牌，直到找到了合适的位置后，将其插入即可。

image

插入排序代码

用变量i对有序部分和无序部分进行分割的话，假设运行到某一时刻，排序状态如下。

|———————————————|—————————————————————————————————|
|    ordered    |     
|———————————————|—————————————————————————————————|
i

基础版

template <typename T>
void insertSort(T* arr, const int len)
{
    //arr[0...i)有序，第一个元素不用排，所以i从1开始
    for(int i = 1; i < len; i++)
    {
        //将a[i]插入到a[i-1]、a[i-2]...之中
        for(int j = i; j > 0 && arr[j] < arr[i]; j--)
            swap(arr[j], arr[j-1])
    }
}

如果可以将内循环中的较大元素都向后移动而不是交换两个元素的话，则会减少数组的访问次数，这样就可以提高插入排序的速度。

改进版

template <typename T>
void insertSort(T* arr, const int len)
{
    for (int i = 1; i < len; i++)
    {
        T tmp = arr[i];
        int  j = i;
        for(j = i-1; j >= 0; j--)
        {
            if(arr[j] > tmp)
                arr[j+1] = arr[j];
            else
                break;
        }
        arr[j+1] = tmp;
    }
}

插入排序性能分析

对于随机排列的数组，假设其长度为 $N$ ，平均情况下，需要 $\frac{N^2}{4}$ 次比较和 $\frac{N^2}{4}$ 次交换。最坏的情况下需要 $\frac{N^2}{2}$ 次比较和 $\frac{N^2}{2}$ 次交换；最好的情况下需要 $N-1$ 次比较和 $0$ 次交换。

	一般情况下	最好情况	最差情况
交换次数	$\frac{N^2}{4}$	$0$	$\frac{N^2}{2}$
比较次数	$\frac{N^2}{4}$	$N-1$	$\frac{N^2}{2}$

插入排序适用场景

插入排序的性能取决于输入数组的初始顺序，非常适用于对一个很大的数组并且数组中的元素接近有序的状态，其性能远远高于比随机顺序的数组或者是逆序的数组。其中接近有序的数组一般有以下三种情况

数组中的每个元素距离它的最终位置都不远
一个有序的大数组和一个小数组相连的情况
数组中只有某几个元素的位置不正确

除此之外，插入排序也很适用于小规模的数组的排序，尤其是针对快速排序或者是归并排序的优化的话，还会用到插入排序。

实际上，对于上述的某些情况，使用插入排序的性能几乎是线性级别的，在某些情况下，其性能可能要好于快速排序。

最后编辑于：2020.08.31 21:01:32