首页 / 算法 / 直接插入排序1

直接插入排序1

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了直接插入排序1，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含912字，纯文字阅读大概需要2分钟。

内容图文

直接插入排序(Straight Insertion Sort)的基本思想是：

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

插入排序图文说明

下面选取直接插入排序的一个中间过程对其进行说明。假设{20,30,40,10,60,50}中的前3个数已经排列过，是有序的了；接下来对10进行排列。示意图如下：

技术分享图片

图中将数列分为有序区和无序区。我们需要做的工作只有两个：(1)取出无序区中的第1个数，并找出它在有序区对应的位置。(2)将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位。看，是不是很简单。

                void insert_sort(int a[], int n)
{
    int i, j, k;

    for (i = 1; i < n; i++)
    {
        //为a[i]在前面的a[0..i-1]有序区间中找一个合适的位置for (j = i - 1; j >= 0; j--)
            if (a[j] < a[i])
                break;

        //如找到了一个合适的位置if (j != i - 1)
        {
            //将比a[i]大的数据向后移int temp = a[i];
            for (k = i - 1; k > j; k--)
                a[k + 1] = a[k];
            //将a[i]放到正确位置上
            a[k + 1] = temp;
        }
    }
}

时间复杂度和稳定性

直接插入排序的时间复杂度是O(N2)：假设被排序的数列中有N个数，遍历一趟时间复杂度是O(N)，需遍历多少次呢？N-1次，因此，其时间复杂度是O(N2)。

直接插入排序是稳定的算法，它满足稳定算法的定义：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

原文：https://www.cnblogs.com/2228212230qq/p/8111532.html

内容总结

以上是互联网集市为您收集整理的直接插入排序1全部内容，希望文章能够帮你解决直接插入排序1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1279322.html

来源：【匿名】