快速排序 ppt课件.ppt

江西师范大学计算机信息工程学院 数据结构 快速排序 作者 杨劲松 内容提要 快速排序导入 快速排序思想 快速排序讲解 快速排序算法分析 练习题 退出 快速排序导入 请同学们使用冒泡排序的方法将下列数据排序 从小到大 212549162506 目录 初始状态 第一次交换结束 快速排序导入 冒泡排序过程 目录 第二次交换 第二次交换结束 快速排序导入 冒泡排序过程 目录 第三次交换结束 第二次交换结束 第四次交换结束 快速排序导入 冒泡排序过程 目录 第六次交换结束 第五次交换结束 请同学们说说 冒泡排序是如何工作的 快速排序导入 目录 对所有记录从左到右每相邻的元素进行比较 不符合要求则交换 快速排序导入 冒泡排序分析 冒泡排序的基本做法 思考 在数据为以下排列时 冒泡的排序效果好不好 492525211606 快速排序导入 冒泡排序分析 初始状态是反序的 则需要进行n 1趟扫描 目录 快速排序导入 冒泡排序分析 从直观上49移动到最终的位置经过了n 1次比较和交换 492525211606 061621252549 能不能不经过n 1次比较和交换呢 不能 这是由于冒泡排序中需要相邻的元素两两比较 交换 目录 快速排序思想 基本思想 1 寻找一个中心元素 通常为第一个数 2 将小于中心点的元素移动至中心点之前 大于中心点的元素移动至中心点之后 3 对上步分成的两个无序数组段重复1 2 操作直到段长为1 t t 目录 快速排序思想 以21为中心元素 划分可得 以06 49为中心元素 划分可得 目录 快速排序讲解 选取中心元素的问题 选取第一个数为中心元素 如何划分问题 如何重复步骤 将所有数据排序 使用递归 目录 当已知中心元素的前提下 怎样将其他元素划分好 即 大于中心点在之后 小于中心点在之前 需要解决的问题 快速排序讲解 i 0 1 2 3 4 5 i 0 i 1 j 5 j 5 j i 1 j 3 i 1 j 4 i 2 j 3 i 2 j 2 算法终止 目录 快速排序讲解 请同学们思考 该算法有没有可以改进的地方 目录 快速排序讲解 i 0 1 2 3 4 5 i 0 i 1 j 5 j 5 j i 1 j 3 i 1 j 4 i 2 j 3 i 2 j 2 算法终止 通过动画 可以看出每次中心元素都要交换 根据划分的思想最后位置一定是中心元素 可以申请一个变量保存中心元素 以避免交换 目录 快速排序讲解 i left j right inttemp a left do 从右向左找第1个不小于中心元素的位置jwhile a j temp left right用于限定要排序数列的范围 temp即为中心元素 程序填空 当前元素小于中心元素结束循环时 应当在中心元素的左边 移至左边 目录 快速排序讲解 从左向右找第1个不大于中心元素的位置iwhile a i temp 将中心元素t填入最终位置 程序填空 目录 快速排序讲解 函数头 quicksort inta intleft intright 初始化 i left j right inttemp a left 划分 do 一次划分 while i j 中心元素填入 a i temp 递归地对剩余段作快速排序 quicksort a left i 1 quicksort a i 1 right 目录 快速排序完整代码 voidquicksort inta intleft intright inti j if lefttemp 目录 while a i temp 快速排序完整代码 目录 算法分析 思考 当数据有序的情况下 快速排序的效率如何 快速排序的最坏时间复杂度为O n2 061621252549 例 快速排序的最好时间复杂度为O nlog2n 快速排序的平均时间复杂度为O nlog2n 快速排序是不稳定的排序方法 目录 练习题 1 在快速排序方法中 进行每次划分时 是从当前待排序区间的 向 依次查找出处于逆序的元素并交换之 最后将中心元素交换到一个确定位置 从而以该位置把当前区间划分为前后 两端 中间 2 假定一组记录的关键字为 46 79 56 38 40 80 对其进行快速排序的一次划分的结果为 3840 46 567984 3 快速排序在 情况下效率最低 在 情况下最易发挥其长处