}
第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进行从小到大的排序， 经过一趟冒泡排序之后的序列怎样？完成排序 至少需要多少趟？