5.3 插入排序算法思想 导学案-2021-2022学年高中信息技术浙教版选修1
高二信息技术导学案 VB模块 班级 姓名
《插入排序算法思想》导学案
[考试要求]
1.插入排序 (c)
[学习目标]
1. 掌握插入排序算法基本思想。
2. 区分插入排序和其他排序方式的优缺点,正确选择合适的排序方式。
3. 合理选择和使用排序方式。
[自主学习]
一、 知识梳理
1.插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建 ,对于未排序数据,在已排序序列中 扫描,找到相应位置并 ,在从后向前扫描过程中,需要反复把已排序元素逐步 挪位,为最新元素提供插入空间。时间复杂度: 。
2.算法描述:
(1)从第一个元素开始,该元素可以认为已经
(2)取出下一个元素,在已经排序的元素序列中 扫描
(3)如果该元素(已排序)大于新元素,将该元素移到下一位置
(4)重复步骤3,直到找到已排序的元素 新元素的位置
(5)将新元素插入到该位置
(6)重复步骤2~5
二、自我检测
1.将下列数据使用插入排序排成由小到大的有序数列
数组 | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | a(7) | 比较 次数 | 交换 次数 |
原始 | 5 | 2 | 7 | 4 | 6 | 3 | 9 | ||
第一趟 | 2 | 5 | 7 | 4 | 6 | 3 | 9 | 1 | 1 |
第二趟 |
|
|
|
|
|
|
|
|
|
第三趟 |
|
|
|
|
|
|
|
|
|
第四趟 |
|
|
|
|
|
|
|
|
|
第五趟 |
|
|
|
|
|
|
|
|
|
第六趟 |
|
|
|
|
|
|
|
|
|
2. 将下列数据使用插入排序排成由大到小的有序数列
数组 | a(1) | a(2) | a(3) | a(4) | a(5) | a(6) | 比较 次数 | 交换 次数 |
原始 | 5 | 9 | 7 | 4 | 6 | 3 | ||
第一趟 |
|
|
|
|
|
|
|
|
第二趟 |
|
|
|
|
|
|
|
|
第三趟 |
|
|
|
|
|
|
|
|
第四趟 |
|
|
|
|
|
|
|
|
第五趟 |
|
|
|
|
|
|
|
|
[课堂练习]
1.将无序的元素依次插入到已知有序数据中的排序方式称为( )
A.冒泡排序 B.插入排序 C.选择排序 D.快速排序
2.现有一组数据:9,3,1,4选择插入排序的方式实现升序,则需要排序的趟数是( )
A.1 B.2 C.3 D.4
3.某校高三(3)班有5位学生参加班长竞选,得票数依次为30,20,7,37,15。使用插入排序的方法对得票数进行从大到小排序,需要进行数据互换的次数是( )
A. 2次 B. 3次 C. 4次 D. 5次