排序一：直接插入排序

直接插入排序

概念

　　直接插入排序是一个把新的数据插入到已经排好的数据列中的过程。
　　它是插入排序最简单的一种，插入排序分①.直接插入排序②.希尔排序。现在先来看看直接插入排序，希尔排序请看下一篇哦。
　　直接插入排序类似于一个打牌时整牌的过程，假设拿到的第一张牌为有序数列，拿到第二张与第一张比较，比它大放它前面，比它小放它后面（降序）；再拿到第三张牌，与前两张有序牌从后到前依次比较，若小于则直接放在后面，若大于则前牌后移直到找到合适位置将第三张牌插入。。。以此类推，直到全部排完使之为一个有序数列。

插入排序的过程：

1、首先将第一个数作为一组元素个数为1的有序数列，end指向每一组有序数列的最后一个数，tmp指向这一组数的下一个数；
2、tmp与这个有序数列从后到前依次比较大小；
3、比tmp小的数后移一位，比tmp大或相等则不变（降序），然后将tmp插入合适的空位；
4、tmp++依次与前一有序数列比较，直到最后一个数，使之成为有序数列。

如图，是插入排序的过程

代码：

//插入排序
void InsertSort(int* a, size_t n)
{
    assert(a);
    for (size_t i = 0; i < n; ++i)//外部循环
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)//内部循环
        {
            if (a[end] < a[end+1])
            {
                a[end+1] = a[end];
                --end;
            }
            else
                break;
        }
        a[end + 1] = tmp;//将tmp插入到合适的位置
    }
}

int main()
{
    int arr[] = { 2, 5, 4, 3, 1 };
    int length = sizeof(arr) / sizeof (arr[0]);
    InsertSort(arr, length);
    for (int i=0; i < length; ++i)
    {
        cout << arr[i] <<" ";
    }
    cout << endl;
}

运行结果

算法分析

时间复杂度： O（n^2）

平均时间复杂度（n^2）
最坏情况时间复杂度(n^2)
最好情况时间复杂度（n）

空间复杂度：O（1）

算法稳定性：稳定

因为在直接插入排序过程中，大小相同数据不会改变位置

最后

以上就是火星上台灯为你收集整理的排序一：直接插入排序的全部内容，希望文章能够帮你解决排序一：直接插入排序所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。