5.3 插入排序算法思想 导学案-2021-2022学年高中信息技术浙教版选修1

| 3页
| 518人阅读
| 100人下载
普通

高二信息技术导学案    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次

 

page number 0


由于学科网是一个信息分享及获取的平台,不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益,请联系学科网,我们核实后将及时进行处理。