《计算机软件基础》第四章 查找与排序（4.5-4.6.1）直接插入排序

排序 主要内容 今4.5直接插入排序 今4.6交换排序 ◆4.7选择排序 今4.8多关键字排序

排序 计算机软件基础 ❖ 4.5 直接插入排序 ❖ 4.6 交换排序 ❖ 4.7 选择排序 ❖ 4.8 多关键字排序 • 主要内容：

教学目的与要求 通过本部分相关内容的学习,使同学 们熟练掌握几种排序的思想及算法的具体 实现;了解每种算法的各种性能;根据具 体问题的实际情况,能选择合适的排序算 法进行排序

⚫ 教学目的与要求 通过本部分相关内容的学习，使同学 们熟练掌握几种排序的思想及算法的具体 实现；了解每种算法的各种性能；根据具 体问题的实际情况，能选择合适的排序算 法进行排序

本节课内容的说明 内容:直接插入排序、交换排序 要求:掌握两种排序的基本思想及算法实现, 了解两种排序算法各自的主要性能指标。 重点:两种排序的基本思想及算法实现。 难点:稳定性的概念、排序算法的具体实现

⚫ 本节课内容的说明 ◼ 内容：直接插入排序、交换排序 ◼ 要求：掌握两种排序的基本思想及算法实现， 了解两种排序算法各自的主要性能指标。 ◼ 重点：两种排序的基本思想及算法实现。 ◼ 难点：稳定性的概念、排序算法的具体实现

开动脑 45直接插入排序 如果有n个元素,初始状态下有序表中多少个元 素,无序表中多少个元素? 2.如果有n个元素,最多需要多少趟的插入操作? 基本思想 将整个数据表(n个记录)看成是由无序表和 有序表两个部分组成,每趟排序时将无序表中的 个记录插入到有序表的恰当位置。初始状态时,有 序表中仅有第一个记录,排序共需进行n-1趟,最 终使整个数据表有序排列

一. 基本思想 将整个数据表（n个记录）看成是由无序表和 有序表两个部分组成，每趟排序时将无序表中的一 个记录插入到有序表中的恰当位置，最终使整个数 据表有序排列。 个记录插入到有序表的恰当位置。初始状态时，有 序表中仅有第一个记录，排序共需进行n-1趟，最 终使整个数据表有序排列。 4.5 直接插入排序 1．如果有n个元素，初始状态下有序表中多少个元 素，无序表中多少个元素？ 2．如果有n个元素，最多需要多少趟的插入操作？ 开动脑 筋

°知识回顾 ■设有一个有序排列的整型顺序线性表a,任 意给定一个元素x,将其插入到线性表a中 使得其依然有序。 找到插入位置,元素后移,插入元素,表长加1 线性表:2,4,6,710 从后往前找 插入7: 找位置的同时,元素后移

• 知识回顾 ◼ 设有一个有序排列的整型顺序线性表 a，任 意给定一个元素x，将其插入到线性表a中， 使得其依然有序。 找到插入位置，元素后移，插入元素，表长加1 线性表：2，4，6，8，10 插入7： i 从后往前找 找位置的同时，元素后移 线性表：2，4， 6， 插入7： 8， 1010， i 7

令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225]

计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25]    

令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第一趟排序详细过程

计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25]     第一趟排序详细过程

令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第二趟排序详细过程

计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25]     第二趟排序详细过程

令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第三趙[20383846][74911225] 第三趟排序详细过程

计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25] 第三趟 [20 38 38 46] [74 91 12 25]     第三趟排序详细过程

令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第三趙[20383846][74911225] 第四趙[2038384674][911225]

计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25] 第三趟 [20 38 38 46] [74 91 12 25] 第四趟 [20 38 38 46 74] [91 12 25]    