当前位置：文档之家 › 《数据结构排序》PPT课件

《数据结构排序》PPT课件

  • 格式：ppt
  • 大小：269.50 KB
  • 文档页数：51

下载文档原格式

  / 51

合集下载

数据结构第9章 排序

数据结构第9章 排序

R[3] 10
R[4] 60
R[5] 25
R[6] 30
R[7] 18 18 18 18
18 36 20

10 10 36
60 60 60
25 25 25
30 30 30
【算法】直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*对排序表R[1]..R[n]进行直接插入排序，n是记录的 个数*/ for(i=2; i<=n; i++) if (R[i].key<R[i-1].key) {R[0]=R[i]; /*将R[i]插入R[1].. R[i-1]中， R[0]为监测哨*/ for(j=i-1; R[0].key<R[j].key; j--) R[j+1]=R[j]; /*后移记录*/ R[j+1]=R[0]; /*插入到合适位置*/ } }
空间性能：除排序表以外的内存占用情况。 时间性能：比较关键码的次数，数据移动的次数。 它们往往是排序表规模（n）的函数
6. 记录和排序表的数据结构
一般采用顺序结构存储排序表。 记录和排序表的类型定义如下： #define MAXNUM … /* MAXNUM 为足够大的数 typedef struct { keytype key; …… } datatype; datatype R[MAXNUM]; /*关键码字段*/ /*其它信息*/ /*记录类型*/ /*定义排序表的存储
第一趟排序结果，使得间隔为5的字表有序： P=3
29 7 41 30 11 39 50 76 41 13 10 0 80 78 86
子序列分别为:{29,30,50,13,78}，{7,11,76,100,86}， {41,39,41,80}。第二趟排序结果： P=1

(2024年)《数据结构》全套课件

(2024年)《数据结构》全套课件

30
树形数据结构的查找算法
二叉排序树的查找
从根节点开始，若查找值小于当前节点 值，则在左子树中查找；若大于当前节 点值，则在右子树中查找。
VS
平衡二叉树的查找
在保持二叉排序树特性的基础上，通过旋 转操作使树保持平衡，提高查找效率。
2024/3/26
31
散列表的查找算法
散列函数的设计
将关键字映射为散列表中位置的函数。
过指针来表示。
链式存储的特点
逻辑上相邻的元素在物理位置上 不一定相邻；每个元素都包含数
据域和指针域。
链式存储的优缺点
优点是插入和删除操作不需要移 动元素，只需修改指针；缺点是
存储密度小、空间利用率低。
2024/3/26
11
线性表的基本操作与实现
插入元素
在线性表的指定位 置插入一个元素。
查找元素
在线性表中查找指 定元素并返回其位 置。
自然语言处理的应用
在自然语言处理中，需要处理大量的文本数据，数据结构中的字符 串、链表、树等可以很好地支持文本的处理和分析。
41
数据结构在计算机网络中的应用
2024/3/26
路由算法的实现
计算机网络中的路由算法需要大量的数据结构支持，如最短路径 树、距离向量等。
网络流量的控制
在计算机网络中，需要对网络流量进行控制和管理，数据结构中的 队列、缓冲区等可以很好地支持流量的控制。
37
06
数据结构的应用与拓展
2024/3/26
38
数据结构在算法设计中的应用
01
作为算法设计的基 础
数据结构为算法提供了基本操作 和存储方式，是算法实现的重要 基础。
02
提高算法效率

第10章 排序 PPT课件

第10章 排序 PPT课件

清华大学出版社
概述
数据结构（C++版）
排序算法的存储结构
从操作角度看，排序是线性结构的一种操作，待排序 记录可以用顺序存储结构或链接存储结构存储。
假定1：采用顺序存储结构，关键码为整型，且记录 只有关键码一个数据项。
int r[n+1]; //待排序记录存储在r[1]~r[n]，r[0]留做他用
假定2：将待排序的记录序列排序为升序序列。
i = 6 18 10 15 21 25 25* 18
10 15 18 21 25 25*
r[0]的作用? 暂存单元 43;+版）
关键问题(1)如何构造初始的有序序列？
解决方法：
将第1个记录看成是初始有序表，然后从第2个记录起 依次插入到这个有序表中，直到将第n个记录插入。 算法描述：
学号 0001 0002 0003 …
姓名 王军 李明 汤晓影
…
高数 85 64 85 …
英语 68 72 78 …
思想品德 88 92 86 …
清华大学出版社
概述
数据结构（C++版）
排序的基本概念
单键排序：根据一个关键码进行的排序； 多键排序：根据多个关键码进行的排序。
学号 0001 0002 0003 …
算法描述：
r[0]=r[i]; j=i-1; while (r[0]<r[j]) {
r[j+1]=r[j]; j--; }
r[0]有两个作用：
1. 进入循环之前暂存了r[i] 的值，使得不致于因记录 的后移而丢失r[i]的内容；
2. 在查找插入位置的循环 中充当哨兵。
清华大学出版社
插入排序
姓名 王军 李明 汤晓影

《数据结构排序》课件

《数据结构排序》课件

根据实际需求选择时间复杂度和空间 复杂度最优的排序算法，例如快速排 序在平均情况下具有较好的性能，但 最坏情况下其时间复杂度为O(n^2)。
排序算法的适用场景问题
适用场景考虑因素
选择排序算法时需要考虑实际应 用场景的特点，如数据量大小、 数据类型、是否需要稳定排序等 因素。
不同场景适用不同
算法
例如，对于小规模数据，插入排 序可能更合适；对于大规模数据 ，快速排序或归并排序可能更优 。
排序的算法复杂度
时间复杂度
衡量排序算法执行时间随数据量增长而增长的速率。时间复杂度越低，算法效 率越高。常见的时间复杂度有O(n^2)、O(nlogn)、O(n)等。
空间复杂度
衡量排序算法所需额外空间的大小。空间复杂度越低，算法所需额外空间越少 。常见的空间复杂度有O(1)、O(logn)、O(n)等。
在数据库查询中，经常需要对结果进行排序，以便用户能够快速找到所需信息。排序算 法的效率直接影响到查询的响应时间。
索引与排序
数据库索引能够提高查询效率，但同时也需要考虑到排序的需求。合理地设计索引结构 ，可以加速排序操作。
搜索引擎中的排序
相关性排序
搜索引擎的核心功能是根据用户输入的 关键词，返回最相关的网页。排序算法 需要综合考虑网页内容、关键词密度、 链接关系等因素。
VS
广告与排序
搜索引擎中的广告通常会根据关键词的竞 价和相关性进行排序，以达到最佳的广告 效果。
程序中的排序应用
数组排序
在程序中处理数组时，经常需要对其进行排 序。不同的排序算法适用于不同类型的数据 和场景，如快速排序、归并排序等。
数据可视化中的排序
在数据可视化中，需要对数据进行排序以生 成图表。例如，柱状图、饼图等都需要对数 据进行排序处理。

数据结构 排序

数据结构 排序
选择排序种类： 简单选择排序 树形选择排序 堆排序
2019/9/7
30
10.4.1 简单选择排序
待排记录序列的状态为：
有序序列R[1..i-1] 无序序列 R[i..n]
有序序列中所有记录的关键字均小于无序序列中记 录的关键字，第i趟简单选择排序是从无序序列 R[i..n]的n-i+1记录中选出关键字最小的记录加入 有序序列
2019/9/7
5
排序的类型定义
#define MAXSIZE 20 // 待排序记录的个数
typedef int KeyType;
typedef struct
{ KeyType key;
InfoType otherinfo; ∥记录其它数据域
} RecType;
typedef struct {
RecType r[MAXSIZE+1];
分别进行快速排序：[17] 28 [33] 结束 结束
[51 62] 87 [96] 51 [62] 结束
结束
快速排序后的序列： 17 28 33 51 51 62 87 96
2019/9/7
26
自测题 4 快速排序示例
对下列一组关键字 （46,58,15,45,90,18,10,62） 试写出快速排序的每一趟的排序结果

final↑ ↑first
i=8
[51 51 62 87 96 17 28 33]

final↑ ↑first
2019/9/7
14
希尔(shell )排序
基本思想：从“减小n”和“基本有序”两 方面改进。
将待排序的记录划分成几组，从而减少参 与直接插入排序的数据量，当经过几次分 组排序后，记录的排列已经基本有序，这 个时候再对所有的记录实施直接插入排序。

数据结构排序PPT课件

数据结构排序PPT课件
—— 若待排序记录一部分在内存，一部分在外存， 则称为外部排序。
注：外部排序时，要将数据分批调入内存来 排序，中间结果还要及时放入外存，显然外 部排序要复杂得多。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
5.待排序记录在内存中怎样存储和处理？
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
Void BInsertSort (SqList &L) // 折半插入排序
{ for ( i=2；i<=L.length；++i )
{ L.r[0] = L.r[ i ]； // 将L.r [i] 暂存到L.r[0]
处理方式： ① 顺序排序 —— 数据间的逻辑顺序关系通过其物理
存储位置的相邻来体现，排序时直接移动记录； 适合数据较少的情况！
② 链表排序 ——数据间的逻辑顺序关系通过结点中 的指针体现，排序时只修改指针，不移动数据；
③ 地址排序 —— 数据存储在一段连续地址的空间， 构造一个辅助表保持各数据的存放地址（指针），排 序时先修改辅助表中的地址，最后再移动记录。
在整堂课的教学中，刘教师总是让学 生带着 问题来 学习， 而问题 的设置 具有一 定的梯 度，由 浅入深 ，所提 出的问 题也很 明确
4. 什么叫内部排序？什么叫外部排序？ —— 若待排序记录都在内存中，称为内部排序；
内部排序基本操作有两种： ◆ 比较两个关键字的大小；(比不可少的操作) ◆ 存储位置的移动。
i=8
0
1
2
3
4

数据结构ppt课件完整版

数据结构ppt课件完整版
数据结构是计算机中存储、组织 数据的方式，它定义了数据元素 之间的逻辑关系以及如何在计算 机中表示这些关系。
数据结构分类
根据数据元素之间关系的不同， 数据结构可分为线性结构、树形 结构、图形结构等。
4
数据结构重要性
01
02
03
提高算法效率
合理的数据结构可以大大 提高算法的执行效率，减 少时间和空间复杂度。
33
案例三：最小生成树在通信网络优化中应用
Kruskal算法
基于并查集实现，按照边的权值从小到大依次添加边，直到生成 最小生成树。
Prim算法
从某一顶点开始，每次选择与当前生成树最近的顶点加入，直到 所有顶点都加入生成树。
通信网络优化
最小生成树算法可用于通信网络优化，通过选择最优的通信线路 和节点，降低网络建设和维护成本。
2024/1/28
简化程序设计
数据结构的设计和实现可 以简化程序设计过程，提 高代码的可读性和可维护 性。
解决实际问题
数据结构是解决实际问题 的基础，如排序、查找、 图论等问题都需要依赖于 特定的数据结构。
5
相关术语解析
数据元素
数据元素是数据的基本 单位，通常作为一个整
体进行考虑和处理。
2024/1/28
02
队列的基本操作包括入队（enqueue）、出队（ dequeue）、查看队首和队尾元素等。
03
队列的特点
2024/1/28
04
数据从队尾入队，从队首出队。
05
队列中元素的插入和删除操作分别在两端进行，因此也称 为双端操作。
06
队列中没有明显的头尾标记，通常通过计数器或循环数组 等方式实现。
15
栈和队列应用举例

数据结构第7章排序

数据结构第7章排序

7.2.1 冒泡排序
• 排序过程 – 将第一个和第二个元素的关键字进行比较，若为逆序 ，则将两个元素互换；接着比较第二个和第三个元素 的关键字，依次类推，直至最后两个元素的完成比较 ，这称为第一趟冒泡排序。第一趟排序分划出一组元 素个数为n-1的待排序列和一个关键字最大的元素。 – 第i趟对前n - i + 1个的元素进行类似的排序操作，得到 一组元素个数为n - i的待排序列和一个（在前n-i+1个元 素中）关键字最大的元素。 – 这样不断分划直至一趟分划时无元素互换为止。
34 28 81 79 63 28 34 81 79 63 28 34 79 81 63
第一趟
28 34 79 63 81
第二趟
28 34 63 79 81
初始
7.2.1 冒泡排序
• 冒泡排序算法
template<class ElemType> void BubbleSort(ElemType data[], int n) { int lastSwapIndex = n - 1; //用于记录最后一次交换的元素下标 int i, j; for (i = lastSwapIndex; i > 0;i = lastSwapIndex){ lastSwapIndex = 0; for (j = 0; j < i; j++) if (data[j] > data[j + 1]){ Swap(data[j],data[j + 1]); lastSwapIndex = j; } } }
数 据 结 构
第7章 排序
概述
• 什么是排序？ – 排序是计算机内经常进行的一种操作，其目的是将一 组“无序”的元素序列调整为“有序”的元素序列。 – 假设含n个记录的序列为{ R1, R2, …， Rn }，其相应的 关键字序列为 { K1, K2, …，Kn }。这些关键字相互之 间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1≤Kp2≤…≤Kpn （或≥） 按此关系将上面记录序列重新排列为： { Rp1, Rp2, …，Rpn } 的操作称作排序。

数据结构第七章 排序

数据结构第七章 排序

name 张涛 赵亮
冯博远 王强 李燕
7.2
基本原理
插入排序
每次将一个待排序的对象，按其关键字大小， 插入到前面已经排序好的一组对象的适当位臵上， 直到对象全部插入为止。
直接插入排序(Insert Sort)
希尔排序(Shell Sort)
7.2.1
直接插入排序
R[1]---R[i-1]
08 08
16 16
第三次
08
16
21
25* 25
49
希尔排序中d（间隔量）的取法 Shell最初的方案是 d= n/2, d=d/2， 直到d=1； Knuth的方案是d= d/3+1；
其它方案有：都取奇数为好；d互质为好 等等。
希尔排序的稳定性
如序列： 21 25 排序后为：08 16
R[0]有两个作用:
其一: 进入查找循环之前，保存 R[i] 的副本，使之不至 于因记录的后移而丢失R[i]中的内容； 其二: 在 while 循环时，“监视”下标变量 j 是否越界， 一旦越界（j<0）,R[0]自动控制while循环的结束, 从而 避免了在while 循环内的每一次都要检测 j 是否越界( 即 省略了循环条件j>=0）。 因此，把 R[0] 称为“监视哨”。
第七章 排 序
本章内容
排序的概念和有关知识
常用的几种排序方法的基本思想、排序过 程和算法实现 各种排序算法的时间复杂度分析
学生成绩表
学号 姓名 高数 英语 总分
005 010 002
018 004
Chen Lin Gao Hong Wang Na
ZhangYang Zhao Pen
84 69 90

数据结构 排序

数据结构 排序

(3)时间复杂度
比较次数与待排记录的初始顺序无关，只依赖 记录个数； 插入每个记录需要O(log2i)次比较 最多移动i+1次，最少2次（临时记录） 最佳情况下总时间代价为O(nlog2n) ，最差和 平均情况下仍为O(n2)。
30
9.2.3希尔排序（又称缩小增量排序）
1.基本思想
把待排序的数据元素分成若干个小组， 对同一小组内的数据元素用直接插入法排 序；小组的个数逐次缩小；当完成了所有 数据元素都在一个组内的排序后排序过程
11
存储方式
3. 地址连续的一组存储单元，另设一个 指示各个记录存储位臵的地址向量，在 排序过程中不移动记录本身，而移动地 址向量中的地址，在排序之后再按照地 址向量中的值调整记录的存储位臵－－ 地址排序
12
#define MAXSIZE 20 // 待排顺序表最大长度 待排记录的数据类型定义如下 : typedef int KeyType; // 关键字类型为整数类型 typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项 } RedType; // 记录类型 typedef struct { RedType r[MAXSIZE+1]; // r[0]闲臵 int length; // 顺序表长度 } SqList; // 顺序表类型
low high low high m m m high
L.r[high+1] = L.r[0]; // 插入
27
2. 算法实现 void BiInsertionSort ( SqList &L ) {
for ( i=2; i<=L.length; ++i ) { L.r[0] = L.r[i]; // 将 L.r[i] 暂存到 L.r[0]

《数据结构》排序》课件

《数据结构》排序》课件

遍历数组，两两比较并交换元素位
置，重复执行直到排序完成。
3
时间复杂度分析
最好情况下O(n)，最坏情况和平均
优化方法
4
情况下为O(n^2)。
加入标记位，如果某次遍历中没有 发生交换，则表示已排序完成。
插入排序
基本思想
将数组分为已排序 和未排序两部分， 每次从未排序中取 出一个元素插入到 已排序的合适位置。
感谢阅读。
的元素，放到已排序的末尾。
每次遍历未排序部分，找到最小
（或最大）的元素，放到已排序部
分末尾。
3
堆排序
使用堆数据结构进行排序，每次选
取堆顶元素，调整堆结构，重复执
时间复杂度分析
4
行直到排序完成。
最坏情况下为O(n^2)，平均情况下
为O(n^2)。
5
优化方法
使用堆排序技巧，优化选择的效率。
快速排序
1
实现流程
时间复杂度
不同排序算法的时间复 杂度对比。
空间复杂度
不同排序算法的空间复 杂度对比。
稳定性
不同排序算法在相同元 素排序时的稳定性对比。
结语
通过本课件，您了解了不同排序算法的原理、实现和优化。在实际应用中， 选择合适的排序算法非常重要。希望本课件能为您的学习和实践提供有价值 的指导。
让我们继续深入学习！
直接插入排 序
逐个遍历未排序元 素，依次插入到已 排序序列中正确的 位置。
希尔排序
将数组按一定步长 分组，分组内使用 直接插入排序，不 断缩小步长直到为 1。
时间n^1.3)。
选择排序
1
基本思想
每次从未排序中选择最小（或最大）
直接选择排序

数据结构-排序PPT课件

数据结构-排序PPT课件
平均情况时间复杂度
O(nlogn)，归并排序的平均时间复杂度为O(nlogn)。其中，n为待排序序列的长度。
06
基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
分配和收集
基数排序是一种稳定的排序算法，即相同的元素在排序后仍保持原有的顺序。
文件系统需要对文件和目录进行排序，以便用户可以更方便地浏览和管理文件。
数据挖掘和分析中需要对数据进行排序，以便发现数据中的模式和趋势。
计算机图形学中需要对图形数据进行排序，以便进行高效的渲染和操作。
数据库系统
文件系统
数据挖掘和分析
计算机图形学
02
插入排序
将待排序的元素按其排序码的大小，逐个插入到已经排好序的有序序列中，直到所有元素插入完毕。
简单选择排序
基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。 时间复杂度：堆排序的时间复杂度为O(nlogn)，其中n为待排序元素的个数。 稳定性：堆排序是不稳定的排序算法。 优点：堆排序在最坏的情况下也能保证时间复杂度为O(nlogn)，并且其空间复杂度为O(1)，是一种效率较高的排序算法。
基数排序的实现过程
空间复杂度
基数排序的空间复杂度为O(n+k)，其中n为待排序数组的长度，k为计数数组的长度。
时间复杂度
基数排序的时间复杂度为O(d(n+k))，其中d为最大位数，n为待排序数组的长度，k为计数数组的长度。
适用场景
当待排序数组的元素位数较少且范围较小时，基数排序具有较高的效率。然而，当元素位数较多或范围较大时，基数排序可能不是最优选择。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
}
第2趟 13 27 49 38 65 97 76 49* 第3趟 13 27h 38 49 49* 65 97 876
冒泡排序
算法2(参见P16，改进方法：一旦某趟没有进行过交换操作则排序结束， 设置change标志标识之)：
void BubbleSort(SqList &L) {
for(i=1, change=true; i<L.length && change==true; ++i) { //i：趟次，一趟冒泡后最小元素在结果表中的位序
第十章 排序
h
1
内容提要
本课主题： 排序的概念、插入排序，冒泡排序、
快速排序，选择排序，堆排序，归并排序，其 它排序方法
教学目的： 掌握排序的基本概念，掌握插入排
序、冒泡排序、快速排序，选择排序，堆排序， 归并排序算法，了解其它排序方法
教学重点： 插入排序、冒泡排序、快速排序，
选择排序，堆排序，归并排序
姓名 年龄 体重 紫薇 16 48 小燕子 16 50 五阿哥 17 60 尔康 18 70 乾隆 40 70 按年龄排序h (稳定？)
姓名 年龄 体重 小燕子 16 50 紫薇 16 48 五阿哥 17 60 尔康 18 70 乾隆 40 70 按年龄排序(不稳定3)
排序的稳定性
键值相等的记录排序前后相对顺序不变的排序 方法是稳定的！键值相等的记录排序前后相对 顺序可能更改的排序方法是不稳定的！
h
5
排序方法分类
排序方法：
构造二叉排序树本身也是一个排序过程
交换排序(起泡排序、快速排序)
选择排序(简单选择排序，堆排序)
插入排序(直接插入排序、希尔排序)
归并排序
基数排序
排序方法
排序
查找
时间复杂度
Байду номын сангаас
空间复杂度 时间复杂度 空间复杂度
O(nlogn)
构造平衡的 注意：一趟排序(插入 二叉排序树 元素)的时间复杂度
提问：上图所示两个排序其稳定性怎样？ ——前者不确定，后者不稳定 一般稳定性不重要，但是有些特殊场合，如银
行、司法、招生等特别关心先后顺序的场合要 注意稳定性问题
h
4
排序的分类
内部排序：待排序记录存放在计算机的 内存中进行的排序过程；
外部排序：待排序记录数量很大，以致 内存一次不能容纳全部记录，在排序过 程中需对外存进行访问的排序过程。外 部排序的效率主要取决于外存的访问频 度。
比较n次，移动2n次，空间2n
-1 -2 3 -3 4 -1 -2 2
p --->
-1 -2 -3
43
low--->
<--- high
比较n次，移动2n次，空间n
-1 -2 3 -3 4 -1 -2 2
low--->
<--- high
比较n次，最多移动1.5n次，空间1
-1 -2 3 -3 4 -1 -2 2 low---> <--- high
h 比较n次，最多移动n+1次，空间111
快速排序
每一趟排序以某个元素为基准将待排记录分割 成独立的两部分，小于基准的记录放在基准的 前面，大的放在后面。该基准称之为枢轴。
例如以第一个元素为基准，经一趟排序后期望 达到的效果如图：
趟次 49 38 65 97 76 13 27 49*
1 38 13 27 49 65 97 76 49*
for(i=1; i<L.length; ++i) //i：趟次，即一趟冒泡后最小元素在结果表中的位序。 //每一趟交换L.r[i～length]中相邻逆序元素 //结果：最小元素到达第i处 for(j=L.length-1; j>=i; --j) //交换L.r[i～length]中相邻逆序元素。 //注意前后两个循环语句的走向相反 if(L.r[j+1].key < L.r[j].key) //这里下标＝位序 L.r[j+1] <---> L.r[j]; //注意无else语句
下一趟排序，由于比较操作将局限在各部分内 进行，不会与整个表中每个元素逐一比较，比 较次数会逐趟减半，趟次也大大减少。如图：
教学难点： 快速排序，堆排序
h
2
一、排序概述
排序：将一个数据元素的无序序列重新 排列成一个按关键字有序的序列。
下图所示给出了两组按年龄排序的结果。 注意其中有两个人的年龄相同。
姓名 年龄 体重 尔康 18 70 紫薇 16 48 五阿哥 17 60 小燕子 16 50 乾隆 40 70
原始数据
2 13 27 49 38 65 97 3 13 27 38 49 49* 65 4 13 27 38 49 49* 65 注意：第5趟没有交换操作，排序结束。
h
27 49* <---->
27 49* 76 49* 97 76 76 97
7
冒泡排序
void BubbleSort(SqList &L) {
O(logn)
O(logn)
O(logn)
为：O(logn)
h
6
二、交换排序
★1、起泡排序(冒泡排序)
每一趟都从头部(或尾部)开始依次交换相邻逆序记录，直 到在某趟排序过程中没有进行过交换记录的操作为止
趟次 49 38 65 97 76 13 <-- <-- <-- <-- <-- <--
1 13 49 38 65 97 76
change=false; for(j=L.length-1; j>=i; --j) //从后向前交换相邻逆序元素
if(L.r[j+1].key < L.r[j].key) //这里下标＝位序 {L.r[j+1] <---> L.r[j]; change=true;} //注意无else语句
} } //结束条件是该趟没有进行过交换操作
答：13245，3趟。从左到右时：21345，3趟
问题：如何增加交换的跨度以提高性能？
h
10
快速排序
★2、快速排序
提问：编写算法将线 性表中所有负数排在 非负数前，要求时间 复杂度、空间复杂度 越低越好。
-1 -2 3 4 -3 -2 1 2
p ---> -1 -2 -3
34
low--->
high--->
第2趟 13 27 49 38 65 97 76 49* 第3趟 13 27h 38 49 49* 65 97 976
冒泡排序性能分析
性能分析：
比较操作：O(n2)；移动操作：O(n2)。 辅助空间：1。 稳定性：稳定
提问：对整数序列32154进行从小到大的排序， 经过一趟冒泡排序之后的序列怎样？完成排序 至少需要多少趟？