Dotcpp  >  编程教程  >  排序算法  >  直接插入排序算法实例详解

直接插入排序算法实例详解

点击打开在线编译器,边学边练

1. 复杂度与稳定性

最坏情况:O(N^2)

最好情况:O(N^2)

平均情况:O(N^2)

 

稳定性:稳定排序

2. 过程介绍

直接插入排序是把新的数据插入以及排序好的数列中,排序的基本方法是:每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止。

可以选择不同的方法在已经排好序数据表中寻找插入位置。根据查找方法不同,有多种插入排序方法,下面要介绍的是直接插入排序。

1.         每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

2.         第一趟比较前两个数,然后把第二个数按大小插入到有序表中;

3.         第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;

4.         依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

3.图示过程

以数组数据{ 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

将红色的数据依次插入组成一个逐渐有序的数组

4.  相关的代码

#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;
}



知识点标签:排序


本文固定URL:https://www.dotcpp.com/course/161

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

数据结构教程
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 C++STL库教程(附带题库)
第六章 串、数组、矩阵和广义表
第七章 树
第八章 图
第九章 查找算法
第十章 排序算法
第十一章 算法和竞赛
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)