第九章 排序

实现算法： （略）
基本操作在链式结构上的实现
操作一：strcopy（s，t） 操作二：strequal（s，t） 操作三：strlength（s） 操作四：strconcat（s，t） 操作五：strsub（s，i，j） 操作六：strdelsub（s，i，j） 操作七：strins（s1，i，s2） 操作八：strrep（s，i，j，t）
实现算法：（略）
操作五：strsub（s，i，j）
分析：求s中从第i个字符开始长度为j的子串。需判 定所给的i (i>=1&&i<=s.len) 、j (j>=0&&j<=s.len-i+1)范 围是否合法。
实现算法：(略)
操作六：strdelsub（s，i，j）
分析：串s中的字符是连续存储的，所以当删除从i 到j的子串后要求将后面的字符全部前移j个单元，在删 除之前需要判断i (i>=1&&i<=s.len) 、j (j>=0&&j<=s.leni+1)是否合法。
链串结点大小的选择将直接影响到串处理的效率。
存储密度=串值所占存储容量 / 实际分配存储容量
链串的类型定义如下：
typedef struct Lnode
{ char
data ;
//存放字符
struct Lnode * next ;
}*Linkstring ;
朴素的模式匹配算法
论文查询，索引，关键词
操作二：strequal（s，t）
分析：判断s和t两个串是否相等，如果串长不相等则两 个串不相等，返回标志0，如果串长相等且串中的各个 字符对应相等则两个串相等，返回标志1；如果有字符 不相等，则表明两字符串不相等，返回标志0。 实现算法：（略）

KCN i n(n 1) / 2 n 2 / 2, RMN (i 2) (n 4)(n 1) / 2 n 2 / 2
i 1 i 1 n 1 n 1
140-14


平均情况下排序的时间复杂度为 o(n2)。 直接插入排序是一种稳定的排序方法。
折半插入排序 (Binary Insertsort)

基本思想是 : 设在顺序表中有一 个元素序列 V[0], V[1], …, V[n-1]。其中, V[0], V[1], …, V[i-1] 是已经排好序的元素。在插入V[i] 时, 利 用折半搜索法寻找V[i] 的插入位置。
折半插入排序的算法
#include "dataList.h"
140-15
插入排序 (Insert Sorting)

基本方法是：每步将一个待排序的元素，按其 排序码大小，插入到前面已经排好序的一组元 素的适当位置上, 直到元素全部插入为止。
直接插入排序 (Insert Sort)

基本思想是 : 当插入第i (i≥1) 个元素时，前面 的V[0], V[1], …, V[i-1]已经排好序。这时，用 V[i]的排序码与V[i-1], V[i-2], …的排序码顺序 进行比较，插入位置即将V[i]插入，原来位置 上的元素向后顺移。
140-11
直接插入排序的算法
#include "dataList.h" template <class T> void InsertSort (dataList<T>& L, int left, int right) { //依次将元素L.Vector[i]按其排序码插入到有序表 //L.Vector[left],…,L.Vector[i-1]中,使得 //L.Vector[left]到L.Vector[i]有序。 Element<T> temp; int i, j; for (i = left+1; i <= right; i++) if (L[i] < L[i-1]) { temp = L[i]; j = i-1;

作业布置
习题9
教学后记
教 案（实验课）
第 34次课 2 学时
章节
第九章排序
重点
难点
重点：
各种排序算法的基本思想
难点：
各种排序算法的基本思想
要求掌握知识点和分析方法
掌握各种排序的基本原理
掌握本章要求的排序算法
教学内容
上机完成案例。
要求：
完成本章排序综合案例。
作业布置
完成本次课程实验报告
教学后记
讲授主要内容
选择排序；归并排序；基数排序；各种排序方法的比较和选择
重点
难点
重点：
1．选择排序
2．归并排序
3．基数排序
4．各种排序方法的比较和选择
难点：
1．选择排序
2．归并排序
3．基数排序
4．各种排序方法的比较和选择
要求掌握知识点和分析方法
熟练掌握直接选择排序
掌握堆排序
理解归并排序
理解基数排序
掌握各种排序方法的比较和选择
教学设计
1.利用算法动态演示，讲解直接选择排序，给出算法及其性能分析
2.利用算法动态演示，讲解堆排序，给出算法及其性能分析。重点分析堆排序的步骤
3.利用算法动态演示，讲解归并排序，给出算法及其性能分析
4.利用算法动态演示，讲解基数排序，给出算法及其性能分析
5.分析各种排序方法的比较和选择，并通过课堂练习加以深刻理解
熟练掌握直接插入排序
熟练掌握二分插入排序
理解希尔排序
熟练掌握冒泡排序、快排
教学设计
1.给出排序的相关基本概念：排序、稳定性、内排序与外排序、就地排序。
2.利用算法动态演示，讲解直接插入排序，给出算法及其性能分析

数据的排序和筛选教学目标：1. 理解排序和筛选数据的概念及重要性。

2. 学会使用常用排序和筛选方法对数据进行处理。

3. 能够应用排序和筛选技术解决实际问题。

教学内容：第一章：数据的排序1.1 排序的概念1.2 排序的依据1.3 排序的方法1.4 排序的应用第二章：数据的筛选2.1 筛选的概念2.2 筛选的方法2.3 筛选的依据2.4 筛选的应用第三章：排序和筛选的结合3.1 排序与筛选的关系3.2 排序和筛选的结合方法3.3 结合排序和筛选解决问题的实例3.4 练习：结合排序和筛选处理数据第四章：排序和筛选在实际应用中的重要性4.1 排序和筛选在数据分析中的作用4.2 排序和筛选在决策支持中的应用4.3 排序和筛选在信息检索中的重要性4.4 实际案例分享：排序和筛选在商业决策中的应用第五章：排序和筛选技术的拓展5.1 高级排序方法介绍5.2 高级筛选方法介绍5.3 排序和筛选算法的优化5.4 拓展练习：运用高级排序和筛选技术解决复杂问题教学方法：1. 讲授：讲解排序和筛选的概念、方法和应用。

2. 案例分析：分析实际案例，让学生了解排序和筛选在实际应用中的重要性。

3. 练习：引导学生运用排序和筛选方法解决实际问题。

4. 小组讨论：分组讨论排序和筛选技术的拓展应用。

教学评估：1. 课堂问答：检查学生对排序和筛选概念的理解。

2. 练习题：评估学生运用排序和筛选方法解决问题的能力。

3. 小组报告：评价学生在小组讨论中的表现及对拓展排序和筛选技术的理解。

教学资源：1. 教材：数据排序和筛选相关教材。

2. 案例：提供实际案例，用于分析排序和筛选的应用。

3. 练习题：设计具有代表性的练习题，帮助学生巩固所学知识。

4. 计算机软件：用于演示排序和筛选操作。

第六章：排序和筛选工具的使用6.1 常见排序和筛选工具概述6.2 排序工具的使用方法6.3 筛选工具的使用方法6.4 实践练习：使用排序和筛选工具处理数据第七章：数据可视化与排序筛选7.1 数据可视化的基本概念7.2 排序与筛选在数据可视化中的作用7.3 数据可视化工具的排序筛选功能7.4 案例分析：数据可视化中的排序和筛选应用第八章：排序和筛选的算法原理8.1 排序算法的原理与实现8.2 筛选算法的原理与实现8.3 排序和筛选算法的性能分析8.4 练习：实现简单的排序和筛选算法第九章：大数据排序和筛选9.1 大数据排序和筛选的挑战9.2 大数据排序和筛选的策略9.3 大数据排序和筛选的算法优化9.4 案例分享：大数据环境下的排序和筛选应用第十章：排序和筛选的应用案例分析10.1 营销数据中的排序和筛选应用10.2 金融数据中的排序和筛选应用10.3 社交媒体数据中的排序和筛选应用教学评估：1. 练习题：设计具有代表性的练习题，帮助学生巩固所学知识。