5.4排序算法--插入与桶 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第五章 数据结构与算法 选修1《数据与数据结构》 5.4 排序算法 --插入与桶 学习目标 排序算法 插入排序算法 桶排序算法 插入排序算法 插入排序算法是对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。 ·插入排序的基本思路 对长度为 n 的数组而言，一共排序 n-1 次，比较次数是 n(n-1)/2。 排序算法 ·插入排序的效率 插入排序算法 ·图解插入排序算法(降序) 排序算法 第一层： 第二层： 插入排序算法 ·图解插入排序算法(降序) 排序算法 第三层： 插入排序算法 ·图解插入排序算法(降序) 排序算法 第四层： 插入排序算法 ·图解插入排序算法(降序) 排序算法 第五层： 插入排序算法 ·图解插入排序算法(降序) 排序算法 一：从第二个元素开始排序，先取出要排序的值，再插入到前面已经排好序的序列表中，最后把取出来的值赋值到对应的位置。 二：循环 i：层数。取值范围： 1 ~ 5 j：比较的次数。取值范围：i之前所有的数据元素 ~ -1 a = [3, 8, 2, 5, 4, 7] print("原列表为：") print(a) for i in range(1, len(a)): k = a[i] for j in range(i - 1, -2, -1): if a[j] < k: a[j + 1] = a[j] else: break a[j+1] = k print("插入排序后的列表（降序）为：") print(a) 输出结果： 原列表为： [3, 8, 2, 5, 4, 7]