基本思想

当读入一个元素时，在已经排序好的序列中，搜寻它正确的位置，再放入读入的元素。但不该忽略一个重要的问题：在插入这个元素前，应当先将它后面的所有元素后移一位，以保证插入位置的原元素不被覆盖。

具体步骤

插入排序使用的是增量（incremental）方法；在排好子数组A[1…j-1]后，将A[j]插入，形成排好序的子数组A[1…j]；

步骤：

⒈从有序数列和无序数列{a2,a3，…，an}开始进行排序；
⒉处理第i个元素时（i=2,3，…，n），数列{a1,a2，…，ai-1}是已有序的，而数列{ai,ai+1，…，an}是无序的。用ai与ai-1，a i-2，…，a1进行比较，找出合适的位置将ai插入；
⒊重复第二步，共进行n-i次插入处理，数列全部有序。

实现方法

程序代码

#include <iostream> using namespace std; int main () {int n,temp,array[1000];cin>>n;array[0]=n;for(int i=1;i<=n;i++){cin>>array[i];for(int j=1;j<=i;j++){if(array[i]<array[j]){temp=array[i];array[i]=array[j];array[j]=temp;}}}for(int i=1;i<=n;i++){cout<<array[i]<<' ';}return 0; }

算法分析

实际复杂度

算法稳定性

总结

以上是生活随笔为你收集整理的排序算法 —— 插入排序的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。