5.3插入排序 课件-2022-2023学年浙教版（2019）高中信息技术选修1

5.3数据排序 ——插入排序 1 插入排序 有一个已经有序的数据序列，在这个已经排好的数据序列中插入一个数，要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法 ——插入排序法，插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。 算法思想 插入排序 如一组数据(n=5)15，54，8，45，21，其升序的排序过程如下: 初始态 15 第1遍加工 第2遍加工 第3遍加工 第4遍加工 15 54 8 15 54 8 15 45 54 8 15 21 45 54 插入排序 插入排序 插入排序 插入排序 插入排序 1.现有1个有序数数列为: 7，10，13，16，19。有一个数 14，插入上述有序序列，从而得到一个新的有序序列为: 7，10，13，14，16，19。 a=[7,10,13,16,19] x=int(input("请输入待插入数:")) print("原始数据为:",a) i=4 #先给列表 a 最后增加一个空值a.append(0) while _______________: ________ i=i-1 a[i+1]=x print("插入后数据:",a) a[i]>x and i>=0 a[i+1]=a[i] 插入排序 2.小王根据上述算法，编写了一个 Python 程序，运行界面如图所示。生成 n 个范围是 1~99 之间的随机整数，用插入排序将待排序数据按升序排序后输出。 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) a[j]>tmp and j>=0 a[j+1]=tmp 课堂练习 小明编写了一个Python程序,功能如下:运行程序,随机产生n个随机整数,并显示排序前数据,且输出经过上述排序算法后的数据,运行结果如图所示。 实现上述功能的Python代码如下,但加框处代码有错,请改正。 import random n=10 #变量n存储待排序数据个数 a=[random.randint(1,99)for i in range(n)] print("待排序数据:",a) for i in range(1,n): t=a[i] j=i-1 while t<a[j]: a[j]=a[j+1] j=j-1 if j<0: break a[j]=t print("排序后数据:",a) a[j+1]=a[j] a[j+1]=t End Thank you 11 插入排序是指在待排序的元素中，假设前面n－1(其中n>＝2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、数量加1的有序数据，算法适用于少量数据的排序。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外(让数组多一个空间才有插入的位置)，而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。 在有序序列(数组)中插入数据“9”(注意顺序不能颠倒) 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。 二、插入排序的时间复杂度： 插入排序的时间复杂度最优为O(n)，最差为O(n2)。 三、插入排序(升序)的核心代码： $