菜鸟笔记
提升您的技术认知

插入排序

阅读 : 1658

一. 算法描述

插入排序:插入即表示将一个新的数据插入到一个有序数组中,并继续保持有序。
例如有一个长度为N的无序数组,进行N-1次的插入即能完成排序;
第一次,数组第1个数认为是有序的数组,将数组第二个元素插入仅有1个有序的数组中;
第二次,数组前两个元素组成有序的数组,将数组第三个元素插入由两个元素构成的有序数组中......
第N-1次,数组前N-1个元素组成有序的数组,将数组的第N个元素插入由N-1个元素构成的有序数组中,则完成了整个插入排序。

关键问题:在前面已经排好序的序列中找到合适的插入位置。

为方便理解我还准备了动图:

插入排序算法

二. 算法分析

平均时间复杂度:O(n2)

空间复杂度:O(1) (用于记录需要插入的数据)

稳定性:稳定

三. 算法实现

从前向后查找的插入排序:

/********************************************************
*函数名称:InsertSort
*参数说明:pDataArray 无序数组;
*          iDataNum为无序数据个数
*说明:    插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
    for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入
    {
        int j = 0;
        while (j < i && pDataArray[j] <= pDataArray[i])    //寻找插入的位置
            j++;

        if (j < i)    //i位置之前,有比pDataArray[i]大的数,则进行挪动和插入
        {
            int k = i;
            int temp = pDataArray[i];
            while (k > j)    //挪动位置
            {
                pDataArray[k] = pDataArray[k-1];
                k--;
            }
            pDataArray[k] = temp;    //插入
        }
    }
}

从后面查找插入的方式,代码复杂程度较低

/********************************************************
*函数名称:InsertSort
*参数说明:pDataArray 无序数组;
*          iDataNum为无序数据个数
*说明:    插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
    for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入
    {
        int j = i - 1;
        int temp = pDataArray[i];    //记录要插入的数据
        while (j >= 0 && pDataArray[j] > temp)    //从后向前,找到比其小的数的位置
        {
            pDataArray[j+1] = pDataArray[j];    //向后挪动
            j--;
        }

        if (j != i - 1)    //存在比其小的数
            pDataArray[j+1] = temp;
    }
}

四. 算法优化

插入排序中,总是先寻找插入位置,然后在实行挪动和插入过程;寻找插入位置采用顺序查找的方式(从前向后或者从后向前),既然需要插入的数组已经是有序的,那么可以采用二分查找方法来寻找插入位置,提高算法效率,但算法的时间复杂度仍为O(n2)。

//查找数值iData在长度为iLen的pDataArray数组中的插入位置
int findInsertIndex(int *pDataArray, int iLen, int iData)
{
    int iBegin = 0;
    int iEnd = iLen - 1;
    int index = -1;    //记录插入位置
    while (iBegin <= iEnd)
    {
        index = (iBegin + iEnd) / 2;
        if (pDataArray[index] > iData)
            iEnd = index - 1;
        else
            iBegin = index + 1; 
    }
    if (pDataArray[index] <= iData)
        index++;
    return index;
}

/********************************************************
*函数名称:BinaryInsertSort
*参数说明:pDataArray 无序数组;
*          iDataNum为无序数据个数
*说明:    二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
    for (int i = 1; i < iDataNum; i++)    //从第2个数据开始插入
    {
        int index = FindInsertIndex(pDataArray, i, pDataArray[i]);    //二分寻找插入的位置

        if (i != index)    //插入位置不为i,才挪动、插入
        {
            int j = i;
            int temp = pDataArray[i];
            while (j > index)    //挪动位置
            {
                pDataArray[j] = pDataArray[j-1];
                j--;
            }
            pDataArray[j] = temp;    //插入
        }
    }
}