2022届高三信息技术选考总复习专题23 插入排序 课件-（29张PPT）

(共29张PPT)
专题23 插入排序
一、连续多个数组元素的移动
1.数组元素向后移动
将数组元素a(p)至a(i－1)间的元素向后移动一个位置的方法：从最后一个要移动的数组元素a(i－1)开始，将a(i－1)赋值给a(i)，再将a(i－2)赋值给a(i－1)，以此类推。注意：如果从最前面的数组元素a(p)开始往后移动，会出现a(p)覆盖a(p＋1)的现象。具体代码如下：
For j＝i－1 To p Step －1 a(j＋1)＝a(j) Next j For j＝i To p＋1 Step －1
a(j)＝a(j－1)
Next j
2.数组元素向前移动
将数组元素a(p＋1)至a(i)间的元素向前移动一个位置，若需保留a(p)的值，可以执行语句t＝a(p)，将a(p)的值暂存在变量t中。向前移动数组元素需从前面的数组元素依次移动。具体代码如下：
For j＝p To i－1 a(j)＝a(j＋ 1) Next j For j＝p＋1 To i
a(j－ 1)＝a(j)
Next j
二、插入排序
(一)排序思想
在将第i个数key插入到数据区间[1，i－1]或[i＋1，n]范围内，使得数据区间[1，i]或[i，n]有序。重复执行n－1遍，使得全部数据有序。
该算法包括两个步骤，一是查找key位置并向后(向前)移动相关元素，二是把key放在空出来的位置上。
查找key位置的方法是：把a(i)赋值给key，如果从前往后有序，变量j从i－1位置开始，向前查找，a(j)与key比较，直到找到位置或找到最前面(j＝1)。如果从后往前有序，变量j从i＋1位置开始，向后查找，a(j)与key比较，直到找到位置或找到最后面(j＝n)。
(二)算法实现
1.理解变量i、j和key的含义
变量i表示每次要插入数的位置，key表示第i个数的值。j表示查找和比较位置。
2.从前往后有序，进行升序排列
从第2个数(i的初值为2)开始，插入到前面有序的数列中。
某数列已经插入3个数，数列为49，60，61，71，54，3，66，以i＝5为例说明插入排序的过程。
查找位置j：区间为[1，4]，从第4个数开始向前查找。
比较对象：先把当前a(i)的值存在变量key中，再用key分别与前面的数a(j)进行比较。
找到位置的条件：比前面的数大，即key≥a(j)。
当key≥a(j)时，key应所处的位置是j＋1。如果没有找到位置，条件是key＜a(j)，把该数向后移动，即把a(j)赋值给a(j＋1)，a(j)＝a(j＋1)。
(三)实现的核心代码
i＝2 Do While i <＝n key＝a(i) For j＝i－1 To 1　Step －1 　　　If a(j)>key Then 　　　　a(j＋1)＝a(j) 　　　Else 　　　　ExitDo 　　 End If Next j a(j＋1)＝key i＝i＋1 Loop i＝2
Do While i <＝n
key＝a(i)
j＝i
Do While j>1 And a(j－1)>key
　　　　a(j)＝a(j－1)
　　j＝j－1
Loop
a(j)＝key
i＝i＋1
Loop
注意内循环j的初值和终值，比较对象和移动对象。
(四)也可以从后往前进行插入排序
变量i的初值是n－1，一直往前插入排序，使得第1个数有序。
考点一　数组元素的位置移动
在循环体中出现语句a(j－1)＝a(j)或a(j)＝a(j＋1)，表示数组元素不断往前移动，语句a(j)＝a(j－1)或a(j＋1)＝a(j)，表示数组元素不断往后移动。
【例1】 有如下 VB 程序段：
n＝6
For i＝2 To 4
k＝a(n－i＋1)
j＝n－i＋2
Do While a(j)a(j－1)＝a(j)
B
j＝j＋1
If j＝n＋1 Then Exit Do
Loop
a(j－1)＝k
Next i
数组元素a(1)到a(6)值分别为“23，6，37，45，11，52”，程序运行后，a数组的值依次为(　　)
A.6，23，37，45，11，52 B.23，6，11，37，45，52
C.6，11，23，37，45，52 D.23，6，37，11，45，52
解析　当i＝2时，n－i＋1＝5，a(6)【变式1】 有如下VB程序段：
n＝8：t＝3
For i＝t＋1 To n
temp＝a(i)
For j＝i To i＋1－t Step －1
a(j)＝a(j－1)
Next j
a(j)＝temp
Next i
A
数组元素a(1)至a(8)中值分别为9，5，12，55，32，41，11，8，运行程序后，数组元素的值分别为(　　)
A.55，32，41，11，8，9，5，12 B.9，5，12，8，11，32，41，55
C.55，41，32，12，11，9，8，5 D.8，11，41，32，55，9，5，12
解析　从内循环For j＝i To i＋1－t Step －1来看，每次要向后移动t个数字，且把第i个数放置在i－t的位置。因此当i＝4时，前面3个数(9，5，12)向后移动，把第4个数放在第1个位置；当i＝4时，前面3个数(9，5，12)向后移动，把第5个数放在第2个位置；依次类推，把1－t个数移到最后，把t＋1至n的数向前移。
考点二　插入排序
【例2】 (2019·4月浙江省选考)小明基于冒泡排序思想设计了一个改进的排序算法。该算法先用冒泡法将数组a中奇数位置的元素、偶数位置的元素分别进行排序，然后再进行后续处理。该算法的VB程序段如下，但加框处代码有错，请改正。
′待排序数据存储在数组a中(a(1)～ a(n))，要求升序排列
For i＝1 To (n－ 1)\2
For j＝1 To n－i*2
　　　　 t＝a(j): a(j)＝a(j＋2): a(j＋2)＝t
End If
Next j
Next i
For i＝1 To n\2
j＝2*i－1
If a(j)>a(j＋1) Then t＝a(j): a(j)＝a(j＋1): a(j＋1)＝t
Next i
t＝a(i): j＝i－1
Do While ta(j＋1)＝a(j): j＝j－ 1
Loop
a(j＋1)＝t
Next i
答案　(1)a(j)>a(j＋2) 　(2)3 To n
解析　插入排序也是经常要考到的问题。先是分别对奇数位和偶数位进行排序，排序后再使偶数位大于前面的元素，最后进行插入排序，只需要对奇数位进行插入排序即可。仅奇数位插入排序，i从1时会导致出现a(0)下标越界，所以i从3开始，即第二空答案为3 To n。
【变式2】 在编号为1－100的观众中随机产生10位不同的幸运观众，并将幸运观众的编号升序排列。请在划线处填入合适的代码。
n＝10: a(1)＝Int(Rnd*100＋1)
i＝2
Do While i <＝n
t＝Int(Rnd*100＋1)
For j＝1 To i－1
If a(j)＝t Then Exit For
Next j
If ____①____ Then
For j＝i－ 1 To 1 Step －1
　　　　If　a(j)>t Then a(j＋1)＝a(j) Else Exit For
Next j
　　____②____
i＝i＋1
End If
Loop
答案　①i＝j　②a(j＋1)＝t
解析　要求产生10位不同的幸运观众，在已经产生的号码中先进行查找，如果没有重复，会找到i的位置。在利用插入排序的思想，把新产生的数放入合适的位置。
1.(2020·1月余杭高中)反转字符串，如输入字符串为“123ABCD”，则输出字符串为“DCBA321”。部分程序如下所示，划线处的正确语句是(　　)
s＝Text1.Text: n＝Len(s): i＝1
′按变量s中字符顺序从左到右依次存入字符串数组a中，代码略
Do While it＝a(i)
For j＝i＋1 To n
　　____①____
Next j
a(j－1)＝t
____②____
Loop
For i＝1 To Len(s)
Text2.Text＝Text2.Text＋a(i)
Next i
A.①a(j＋1)＝a(j)　②n＝n－1 B.①a(j)＝a(j＋1)　②n＝n＋1
C.①a(j－1)＝a(j)　②n＝n－1 D.①a(j－1)＝a(j)　②n＝n＋1
答案　C
解析　本题主要考查插入排序的算法实现。从左往右，每次循环将最左边的数组元素取出，暂存至变量t，下一位至最后一位依次往前移一位，再将暂存在变量t中的元素插入到n的位置，当后移一位后，n的位置也需要往前移一位，实现字符串的逆序输出。
2.有如下VB程序段：
n＝7：bottom＝7
For i＝2 Ton－1
If i Mod 2＝0 And a(i)＝a(i－1)＋a(i＋1) Then
For j＝i To bottom－1
　　　　a(j)＝a(j＋1)
Next j
bottom＝bottom－1
End If
Next i
For i＝1 To bottom
Text1.Text＝Text1.Text＋Str(a(i))
Next i
数组元素a(1)到a(7)的值依次为“26，94，68，42，69，27，132”。若该程序段执行后，文本框Text1中显示的内容可能是(　　)
A.26 42 27 132 B.26 68 42 27 132
C.26 42 69 27 132 D.26 68 42 69 27 132
解析　在For j内循环中，语句a(j)＝a(j＋1)的功能是把后面数据往前前移动。因此当偶数上的数组元素值等于他前后两个数组元素值之和时，把当前位置后面的数往前移动，并减少bottom的数量。当a(i)等于94时，他与前后两个数组元素之和相等，所有数据往前移动，bottom等于6，a(1)到a(7)的值依次为“26，68，42，69，27，132，132”。当i＝4时，69＝42＋27，因此接着后移，bottom等于5，a(1)到a(7)的值依次为“26，68，42，69，27，132，132，132”。
D
3.某排序算法的VB程序段如下所示：
Dim i As Integer，j As Integer，t As Integer
Const n＝6
Dim a(1 To 6) As Integer ′生成n个随机数，存储在数组a中，代码略
Private Sub Command1_Click()
For i＝2 To n
t＝a(i): j＝i－1
Do While ta(j＋1)＝a(j) 　　′①
j＝j－1
　　　　If j＝0 Then Exit Do
Loop
a(j＋1)＝t
Next i　 ′显示排序后的数据，代码略
End Sub
经历某趟排序后，数据序列为2，5，8，1，9，7。则本趟排序前数据可能的顺序，以及本趟排序中语句①执行的次数为(　　)
A.2，8，5，1，9，7　1次 B.2，5，8，1，9，7　 1次
C.8，2，5，1，9，7　2次 D.8，5，2，1，9，7　 3次
解析　程序的功能是采用插入排序对数据进行升序排列。数组中前3个数据有序，因此可能进行了1趟或2趟插入排序。A选项5向后移动1次，该语句执行了1次。B选项没有发生数据的移动。C选项第1趟排序的结果是2，8，5，1，9，7，在第2趟中，只移动了1次。D选项第1趟排序的结果是5，8，2，1，9，7，在第2趟中，5和8分别向后移动1次。
A
4.对文本框输入的字符串进行去重，并保持原顺序不变，例如，在文本框Text1中输入“aldajbnjndalldfjj”，执行程序后文本框Text2中输出“aldjbnf”。实现该算法的VB程序如下：
s1＝Text1.Text: n＝Len(s1)
For i＝1 To n
a(i)＝Mid(s1，i，1)
Next i
For i＝1 To n
j＝i＋1
Do While j <＝n
If a(i)＝a(j) Then
　　　　For k＝______①______
　　　　　　____②____
　　　　Next k
　　　　n＝n－1: j＝j－1
End If
j＝j＋1
Loop
Next i
For i＝1 To n
s＝s＋a(i)
Next i
Text2.Text＝s
上述程序中2处下划线应填入的程序代码是(　　)
A.①j＋1 To n　②a(k＋1)＝a(k) B.①j＋1 To n　②a(k)＝a(k－1)
C.①j To n－1　②a(k－1)＝a(k) D.①j To n－1　②a(k)＝a(k＋1)
解析　本题主要考查字符串的处理以及数组移动。将字符串s1从左往右遍历并逐个取出存储在a数组中，从第一个字符开始，当前字符与之后的每一个字符比较，如果有重复，则将重复字符后的每一个字符往前移动一位，若k＝j to n－1，则a(k)＝a(k＋1)可以实现整体往前移动一位，若k＝j＋1 to n，则a(k－1)＝a(k)，故只有D项正确。
D
5.有如下VB程序段：
Const n＝6
Dim a(0 To n) As String
Dim i As Integer，j As Integer
For i＝2 To 4
a(0)＝a(i): j＝i－1
Do While a(0)a(j＋1)＝a(j)
j＝j－1
Loop
a(j＋1)＝a(0)
Next i
已知字符串数组元素a(1)到a(6)的原始数据为”118”，”36”，”98”，”15”，
”88”，”2”，执行该程序段后，数组元素a(1)到a(6)的值依次为(　　)
A.”15”，”36”，”98”，”118”，”88”，”2”
B.”118”，”15”，”36”，”98”，”88”，”2”
C.”2”，”15”，”36，”118”，”88”，”98”
D.”2”，”15”，”36”，”88”，”98”，”188””
解析　在每趟查找的区间是[0，i－1]，方向为从后往前。每趟的算法是：与前面数据比较，比前面数小，把前面的数往后移动，如果大于等于前面数，终止本趟查找。当i小于3时，没有比前面数小，因此进行移动，当i＝4时，把”15”移动到”118”的后面。
B
6.下列VB程序段实现把文本框Text1和Text2中输入的升序字符串合并成一个升序字符串，并在文本框Text3中显示。
s1＝Text1.Text: s2＝Text2.Text
n＝Len(s1): i＝1: j＝1
Do While i <＝n＋j－1 And j <＝Len(s2)
If Mid(s1，i，1)Else
s1＝Mid(s1，1，i－1)＋Mid(s2，j，1)＋Mid(s1，i，n＋j－i)
End If
Loop
Text3.Text＝s1
方框①②③中的代码依次为(　　)
A.①j＝j＋1　②i＝i＋1　③j<＝Len(s1)
B.①i＝i＋1　②j＝j＋1　③j<＝Len(s1)
C.①j＝j＋1　②i＝i＋1　③j<＝Len(s2)
D.①i＝i＋1　②j＝j＋1　③j＝Len(s2)
解析　本程序是一个插入排序。语句s1＝Mid(s1，1，i－1)＋Mid(s2，j，1)＋Mid(s1，i，n＋j－i)就是将串s2第j个字符插入到串s1 中的一个合适位置。语句If Mid(s1，i，1)D