资源简介

(共17张PPT)
五、 插入排序及程序实现
第五章　数据结构与算法
知识过关
1. 插入排序的算法思想
有一个已经有序的数据序列,在这个已经排好的数据序列中插入一个数,要求插入后此数据序列仍然有序,这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,该算法适用于少量数据的排序。
插入排序的基本思想是每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当的位置上,直到全部插入完为止。
在待排序的元素中,假设前面n－1(n≥2)个数已经是排好顺序的,现将第n个数插到前面已经排好的序列中,然后找到合适自己的位置,使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入,直到整个序列变为有序的过程,称为插入排序。
插入排序法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一
个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待
插入元素)。在第一部分排序完成后,再将这个最后的元素插入到已排好序的第一部分中。
在有序序列(数组)中插入数据“9”(注意顺序不能颠倒)
2. 插入排序(升序)的核心代码
def insert_sort(a):
　　for i in range(1,len(a)):　　　　　　#小于i的为有序部分,i~len－1为无序部分
　　　　tmp = a[i]　　　　　 #无序部分取值
　　　　pos = i－1
　　　　while pos>=0 and a[pos]>tmp:　 #在有序部分寻找插入位置
　　　　　　a[pos+1] = a[pos]　　　　　 #逐位后移
　　　　　　pos －= 1
　　　　a[pos+1] = tmp　　 #将值插入有序部分
　　return a
d = [6, 0, 9, 5, 8, 3, 4, 7, 1, 2]
print(insert_sort(d))
程序运行结果如下:
初始　:[6, 0, 9, 5, 8, 3, 4, 7, 1, 2]
第1轮:[0, 6, 9, 5, 8, 3, 4, 7, 1, 2]
第2轮:[0, 6, 9, 5, 8, 3, 4, 7, 1, 2]
第3轮:[0, 5, 6, 9, 8, 3, 4, 7, 1, 2]
第4轮:[0, 5, 6, 8, 9, 3, 4, 7, 1, 2]
第5轮:[0, 3, 5, 6, 8, 9, 4, 7, 1, 2]
第6轮:[0, 3, 4, 5, 6, 8, 9, 7, 1, 2]
第7轮:[0, 3, 4, 5, 6, 7, 8, 9, 1, 2]
第8轮:[0, 1, 3, 4, 5, 6, 7, 8, 9, 2]
第9轮:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
典例精选
【例1】 (2025·浙江1月选考)数组元素a[0]~a[n－1]已按升序排列,现要将
a[pos](0≤pos≤n－1)的值加1,并保持数组的有序性不变,实现该功能的程序段如下。
方框中应填入的代码是(　　)
t = a[pos]+1
i = pos
while 　　　　:
　　a[i] = a[i+1]
　　i += 1
a[i] = t
A. i < n－1 B. i < n－1 and t > a[i+1]
C. i < n－1 and a[i] > a[i+1] D. i <= n－1 or t > a[i]
【解析】 本题考查数组的插入排序。根据代码可知,由于代码中a[j+1],因此i的取值范围不能等于n－1,否则下标越界,D错误。还需保持数组升序,要增加附加条件,A错误。根据代码,待排序数已存入t中,因此t应与后面元素a[j+1]比较,C错误。
B
【例2】 现有1个有序序列为7,10,13,16,19。有一个数14,插入上述有序序列中,从而得到一个新的有序序列为7,10,13,14,16,19。
其思路如下:首先找到14的插入位置。从右到左开始查找,由于14小于19,先将19右移一个位置,然后14又小于16,因此再将16右移一个位置。接下来再将14与下一个数进行比较,当14大于等于数组中的数据时,记录该位置,然后把14插入即可。程序界面如图所示,输出原始数据以及插入后的数据。
请输入待插入数:14
原始数据为:[7,10,13,16,19]
插入后数据:[7,10,13,14,16,19]
实现上述功能的Python程序如下,请在画线处填入合适的代码。
a=[7,10,13,16,19]
x = int(input("请输入待插入数:"))
print("原始数据为:",a)
i = len(a)－1
a.append(0)　#先给列表a最后增加一个空值
while ①___________________ :
　　　 ②________________
　　　i = i － 1
a[i+1] = x
print("插入后数据:",a)
【解析】 本题考查插入算法。①根据题意,a[i]> x时,该数往后移动,且还要考虑循环变量i的范围,必须确保i>=0。②插入排序,必须从后往前找到正确的插入位置,在找位置的过程中还需要一边将数据往后移动,找到位置后,把x插入即可。因此答案是a[i + 1]=x。
a[i]> x and i>=0
a[i + 1]=a[i]
【例3】 插入排序,其基本算法的思想如下:每次将一个待排序的数据,按其大小插入到前面已排好序的数据序列中,使数据序列依然有序,直到所有待排序数据全部插入完成。
如一组数据(n=5)15,54,8,45,21,其升序的排序过程如下:
初始态:【15】　54　8　45　21
第1趟:【15　54】　8　45　21
第2趟:【8　15　54】　45　21
第3趟:【8　15　45　54】　21
第4趟:【8　15　21　45　54】
小王根据上述算法,编写了一个Python程序,运行界面如图所示。生成n个范围是1~99之间的随机整数,用插入排序将待排序数据按升序排序后输出。
排序前数据:[64,65,99,34,39,24,38,22,16,58]
排序后数据:[16,22,24,34,38,39,58,64,65,99]
实现上述功能的Python程序代码如下,请在画线处填入合适的代码。
import random
n=10
a=[random.randint(1,99)for i in range(n)]
print("排序前数据:",a)
for i in range(1,n):
　　tmp = a[i]
　　j = i － 1　
　　while ①_______________________:
　　　　　a[j+1]=a[j]
　　　　　j = j － 1
　　②______________
print("排序后数据:",a)
tmp < a[j]and j>=0
a[j+1]=tmp
【解析】 本题考查插入排序算法。①该算法的思想是:从后往前检查,若待插入数tmp小于a[j],则将该数组元素a[j]往前移动,故此处答案是tmp < a[j]and j>=0。然后继续往前(j=j－1)检查,直到遇到比tmp小的数组元素为止。②当退出while循环时,返回的值j是比tmp小的数组元素下标,故应该插入的位置是a[j+1],因此答案是a[j+1]=tmp。
自我检测
1. 有如下Python程序段:
for i in range(1,4):
　　tmp = a[i]
　　j = i－1
　　while tmp < a[j] and j >=0:
　　　　a[j+1] = a[j]
　　　　j = j － 1
　　a[j+1] = tmp
已知列表a=[19,8,96,92,85,88],经过该程序段处理后,列表元素的值依次为(　　)
A. 8,19,92,96,85,88 B. 8,19,85,88,92,96
C. 19,8,92,96,85,88 　 D. 19,8,85,92,96,88
【解析】 本题考查插入排序。先后将元素a[1]、a[2]和a[3]作为待插入数据进行排序,因此插入排序结束后,前四个数据有序(升序),而后面两个数据不变,A正确。
A
2. 有如下Python程序段,已知列表a是随机产生的数,要求实现升序排序。
for i in range(1,5):
　　 ①
　　key = a[j]
　　while a[j－1] > key and j > 0:
　　　　　a[j] = a[j － 1]
　　　　　j = j － 1
　　 ②
则画线处的代码应该是(　　)
A. ①j = i　　　　 ②a[j+1] = key
B. ①j = i－1　　 ②a[j+1] = key
C. ①j = i　　　 ②a[j] = key
D. ①j = i－1　　 ②a[j] = key
【解析】 本题考查插入排序算法。完整进行插入排序后,数据实现升序排序。由于插入的条件是a[j－1]> key and j > 0,因此插入的位置应该是a[j],C正确。
C
3. 有如下Python程序段:
for i in range(3 ,1 ,－1):
　　if a[i] < a[i－1]:
　　　 tmp = a[i]
　　　 for j in range(i － 1 , 1 , －1):
　　　　　　if tmp > a[j]:
　　　　　　　　break
　　　　　 a[j + 1] = a[j]
　　　 a[j + 1] = tmp
已知列表a=[19,8,96,92,85,88],经过该程序段处理后,列表元素的值依次为(　　)
A. 8,19,92,96,85,88 B. 8,19,85,88,92,96
C. 19,8,92,96,85,88 　 D. 19,8,85,92,96,88
【解析】 本题考查插入排序。先后将元素a[3]=92作为待插入数据进行排序,由于是从后往前找位置,因此找到位置后插入数据8的后面。而其他数据不变,C正确。
C

展开更多......

收起↑