最坏情况:O(N^2)
最好情况:O(N^2)
平均情况:O(N^2)
稳定性:稳定排序
直接插入排序是把新的数据插入以及排序好的数列中,排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。
可以选择不同的方法在已经排好序数据表中寻找插入位置。根据查找方法不同,有多种插入排序方法,下面要介绍的是直接插入排序。
1. 每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。
2. 第一趟比较前两个数,然后把第二个数按大小插入到有序表中;
3. 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;
4. 依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。
以数组数据{ 70,50,30,20,10,70,40,60}为例:
第一趟 | 50 | 70 | 30 | 20 | 10 | 70 | 40 | 60 |
第二趟 | 30 | 50 | 70 | 20 | 10 | 70 | 40 | 60 |
第三趟 | 20 | 30 | 50 | 70 | 10 | 70 | 40 | 60 |
第四趟 | 10 | 20 | 30 | 50 | 70 | 70 | 40 | 60 |
第五趟 | 10 | 20 | 30 | 50 | 70 | 70 | 40 | 60 |
第六趟 | 10 | 20 | 30 | 40 | 50 | 70 | 70 | 60 |
第七趟 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 70 |
第八趟 | 10 | 20 | 30 | 40 | 50 | 60 | 70 | 70 |
将红色的数据依次插入组成一个逐渐有序的数组
#include<iostream> using namespace std; void insert_sort(int a[],int n) { int i,j; for(i=1; i<n; i++) { //循环从第2个元素开始 if(a[i]<a[i-1]) { int temp=a[i]; for(j=i-1; j>=0 && a[j]>temp; j--) { a[j+1]=a[j]; } a[j+1]=temp;//此处就是a[j+1]=temp; } } } int main() { int a[8]= {70,50,30,20,10,70,40,60}; int n=7; insert_sort(a,n); for(int i=0; i<=n; i++) { cout<<a[i]<<' '; } return 0; }
1714 | 数据结构-直接插入排序 |
知识点标签:排序
本文固定URL:https://www.dotcpp.com/course/161
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程