当前课程知识点：数据结构 > 第8章 排序 > 8.3 交换排序 > 讲解（上）
本节，我们来学习第二类排序
交换排序
交换排序
基于元素交换的思想，也就是两个元素
呈非正序的时候
比如，左边大于右边
这时候，我们交换两个元素的位置
交换排序
具体我们介绍两种，第一种
是冒泡排序，学过C语言的同学，可能对冒泡排序比较熟悉
冒泡排序
对相邻位置的元素，进行两两比较
如果非正序
那么交换，较小者(也就是气泡)
我们把它放到左侧
让较大者放到右侧，第一趟
我们一共要经历n-1次两两比较
最大者(也就是石头)
它会出现在最后一个位置
也就是位置n
比如，现在有n个元素
我们两两比较
这是第一趟的时候，两两比较，第1个和第2个比较
如果左边大于右边，交换
然后第2和第3比较，第3和第4比较
n-1和n比较
一共会经历n-1次
两两比较
因为，第一趟找出了最大者，放在n的位置
第二趟
找出了次大者，放在n-1的位置
最后一趟，实际上，只经历1次两两比较
也就是，第1个和第2个进行比较
那么，它会找出次小者
也就是倒数第二小的那个元素，放在2的位置
最后，还剩一个元素
一个元素是有序的
就没有必要再进行下一趟排序了
是否一定要经过n-1趟呢，不一定，最多执行n-1趟
前面第一章，在讲时间复杂度的时候
曾经分析过冒泡排序
它可以优化为，若某一趟未发生任何两两元素的交换
则不需要进行下一趟，排序就可以结束了
现在，我们通过具体的示例
假设，5个元素，我们进行第一趟
那么，这里，4和2比较
交换，变成2和4
这里变成2和4
然后，4和3比较，交换
变成3和4
然后，4和5比较，不变
5和1比较，交换，变成1和5
所以，第一趟排序结束之后，最大的那个元素5，就出现在了它应该出现的位置
也就是最后一个位置
第二趟，我们对前面4个数，进行3次两两比较
2、3不变
3、4不变
4、1交换，变成1、4
第二趟结束之后
次大者出现在第n-1个位置
再进行两趟冒泡排序
最终排序完毕
这是经历了
4趟排序，5个元素
经历4趟排序
这是最坏的情况
我们再来看一个序列，1、2、3、5、4，这个序列
是基本有序的
我们对它进行第一趟冒泡排序
1、2比较，不变
2、3比较，不变
3、5比较，不变
5、4比较，交换成4、5
第一趟排序结束
最大值5，出现在第5个位置
尽管经过第一趟排序之后
5个元素已经排好了
但是，程序(算法)是不知道的
因为，这一趟排序发生了一次两两交换
那就必须进行下一趟
在第二趟排序过程当中
1、2不变
2、3不变
3、4不变
第二趟排完了
没有发生任何的交换
这时候，就不需要进行第三趟排序了
这是冒泡排序
最多经过n-1趟
现在，我们来看冒泡排序的具体实现
我们对L进行冒泡排序
这个变量
是用来交换的临时变量
外层循环n-1
最后一个值是1
一共执行n-1趟
每一次，i--
这里，for循环第二个表达式，还有一个条件，是exchanged不等于0
很明显
这个条件是用来表示，在某一趟冒泡排序过程当中，是否出现了两两元素的交换
只要交换了
我们就要进行下一趟
如果它等于0
那就没有必要进行下一趟，for循环退出
整个排序也结束
进入外层循环之后
我们将exchanged初始化成0
内层循环，j从1开始，j到i
一共执行i次
这是为什么呢
我们可以分析一下
第一趟
我们这里的i值，实际上取的是n-1，第一趟要经过多少次比较呢
我们刚才已经分析过了
是n-1次
那么，第二趟
i取的值是n-2，注意
i是自减的
我们要经历
n-2次比较，最后一趟
也就是第n-1趟
i能取到的最后一个值是1
最后一趟
实际上，只需要经历1次两两比较
那可以总结出，第i趟的时候，比较次数就是i
所以，内层循环
它就要执行i次
这是因为，i的初值是n-1
1到i，执行i次，内存循环，相邻位置的值进行比较
j和j+1这两个下标位置的值，进行比较
如果左边大于右边，是逆序的
我们就要交换，3行赋值语句
所以，冒泡排序是属于交换排序的
既然发生了交换
我们就在内层循环里面
将这个变量，把它修改成1
表示这一趟排序过程当中
至少发生了一次两两交换
将来，我们进入下一次循环的时候
还要进行下一趟排序
这个算法
它的时间复杂度，最好的情况，也就是元素呈正序排列的时候
时间复杂度是O(n)
因为，这时候只需要经过一趟冒泡排序
而一趟冒泡排序
这个if要执行n-1次
因为，第一趟要进行n-1次两两比较
就是O(n)
最坏的情况(逆序的)，一共要执行n-1趟
每一趟的两两比较次数，是跟n(和i)有关的
是一个等差数列
最后求出来，就是n^2
它的空间复杂度
我们用到了一个临时的变量
当然
你也可以直接用r[0]，作为临时的变量
毕竟这个下标我们没有用
所以，它的空间复杂度是O(1)
这个算法，它是稳定的
但是，我们很容易把它改成不稳定的
刚才已经说过了
如果我们在这加个等号
它就是不稳定的
但通常没有必要
所以，我们认为冒泡排序是稳定的排序算法
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
