排序算法——插入排序

- 日理万妓 2022-06-12 00:19 213阅读 0赞

## 前言 ##

算法的思想：将数据分成两部分，一部分是有序的部分，另外一部分为无序的部分。然后每次从无序区中取出一个元素，按照其大小插入到前面有序的区间中，直到全部无序的元素取完为止。

![SouthEast][]

就如上图所示，蓝色的是有序的，红色的是无序的。算法就是从无序元素中抽取一个插入到有序的区间中去。

## 1. 编码 ##

template<typename T> struct Disp
    {
        void operator()(T value)
        {
            cout << value << "\t";
        }
    };
    
    void InsertSort(std::vector<int>& vec)
    {
        int len(vec.size());
        if(len == 0) return;
        cout << "display origin array:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());  //打印原始的数据
    
        for(int i=1; i<len; ++i)
        {
            int temp(vec[i]);   //记录当前操作的元素
            //j是i的前面的元素（往前遍历），若是发现当前操作元素小于之前的元素那就应该将其放在前面
            //自然的应该往前移动，直到找到大于当前元素的那个位置（~i的元素整体后移）
            int j(i-1);
            for(j; j>=0&&temp<vec[j]; --j)
                vec[j+1] = vec[j];
    
            vec[j+1] = temp;    //移动之后的空缺，由单签操作数填补
        }
    
        cout << "\narray sorted:" << endl;
        for_each(vec.begin(), vec.end(), Disp<int>());
    }

![SouthEast 1][]

[SouthEast]: /images/20220612/1674dbd75985459d9a082a0ba4316506.png
[SouthEast 1]: /images/20220612/c5fe7a026117490faba90a2ca1a59ae4.png

发表评论取消回复

表情：

评论列表（有 0 条评论，213人围观）

还没有评论，来说两句吧...

相关阅读

相关排序算法：插入排序

排序算法：插入排序一、快速排序 -------------------- 一、快速排序插入排序核心思想：将未排序的元素一个一个地插入到有序的集合中，插

怼烎@/ 2024年03月16日 18:54/ 0 赞/ 39 阅读

相关【排序算法】插入排序

文章目录一：基本概念 1.1 介绍 1.2 原理 1.3 插入排序法思想二：代码实现 2.1 源码

青旅半醒/ 2024年02月24日 03:00/ 0 赞/ 42 阅读

相关排序算法 - 插入排序

直接插入排序基本思路 ![1475571-20190815204657643-1362081037.png][] 一趟直接插入排序：在有序区中插入R\[i\]

短命女/ 2023年08月17日 16:43/ 0 赞/ 121 阅读

相关排序算法——插入排序

排序算法——插入排序 > 插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。在其实现过程使用双层循环，

﹏ヽ暗。殇╰゛Y/ 2022年12月10日 05:59/ 0 赞/ 166 阅读

相关排序算法——插入排序

一、算法思想给定一个无序数列，模拟一个指针从第0位开始向后，始终保持当前位置左边的数列是有序的。指针位置上的元素依次与前面的元素比较，当遇到小于自己的数或右边已经没

刺骨的言语ヽ痛彻心扉/ 2022年11月12日 01:47/ 0 赞/ 175 阅读

相关算法——排序——插入排序

插入排序的特点： 1.所需时间取决于输入元素的初始顺序，适用于一个很大且其中元素基本有序的数组 2.O(n^2) Code: def sortInsert(ar

Bertha 。/ 2022年07月27日 10:53/ 0 赞/ 237 阅读

相关排序算法——插入排序

前言算法的思想：将数据分成两部分，一部分是有序的部分，另外一部分为无序的部分。然后每次从无序区中取出一个元素，按照其大小插入到前面有序的区间中，直到全部无序的元素取完为

- 日理万妓/ 2022年06月12日 00:19/ 0 赞/ 214 阅读

相关排序算法——插入排序

直接插入排序最简单的排序方法。它的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录增1的有序表。 > 把n个待排序的元素看成一个有序表和一个无序

野性酷女/ 2022年05月09日 11:36/ 0 赞/ 249 阅读

相关排序算法--插入排序

1.基本思想：将未排序的数据元素按大小顺序插入到已排好序数据序列中，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。例如：对2, 4, 3, 1, 6,

灰太狼/ 2022年04月10日 12:08/ 0 赞/ 236 阅读

相关排序算法---插入排序

基本思路：将待排序的数一个个的顺序的插入到已经排好序的数组中。则生成的新的序列也是已经拍好许的序列。问题：插入到已拍好的序列中？一开始就是没有顺序的

系统管理员/ 2022年03月11日 04:20/ 0 赞/ 259 阅读