插入排序--c++代码

逃离我推掉我的手 2023-02-14 13:06 36阅读 0赞

**描述**： 在一个已经排好顺序的序列内，要求插入一个新的元素之后新的序列还是一个有序的序列，这个时候就引入了插入排序，**插入排序是一个稳定的排序方法，适用于对少量的数据进行排序**。

**时间复杂度**：O(n^2)

**思路**：每步将一个待排序的元素，按其值的大小依次与前面排好的元素比较，然后插入到前面已经排序的数组中的适当位置上，直到全部插入排好为止。

**代码**：  
由于给定的数组没有已经排好顺序的序列，所以最开始设置第二个元素为待插入的元素，第一个元素为一个有序的序列，两者进行比较之后排好顺序，之后再将第三个元素作为待插入元素，依次类推…直到所有元素顺序排完为止。

*  对于insert\_value你也可以理解为一个 临时变量 temp，目的是插入元素小于前一个元素时，用来交换两个变量的值，这样方便理解

// hmtian @ 2020/6/2 22:09
    #include<iostream>
    #include<vector>
    int main()
    { 
            std::vector<int> arr = { 1,4,5,3,6,76,23,54,67,23,3};
    
            for(int i = 1; i < arr.size(); i++)
            { 
                    //Because we dont know the order firstly, we set the second element as the insert_value.
                    int insert_value = arr[i];
                    //Obtain the element before insert_value for comparison.
                    int init_index = i-1;
                    
                    while( init_index >= 0 && insert_value < arr[init_index])
                    { 
                            arr[init_index + 1] = arr[init_index];
                            init_index--;
                    }
    
                    arr[init_index + 1] = insert_value;
            }
    
            for(const auto& e : arr){ 
                    std::cout << e <<" ";
            }
            std::cout<<std::endl;
    }

**结果**:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]  
参考自： [程序员必须掌握的那些算法][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200602221429109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM3ODgwMA==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/qq_42453117/article/details/99680831