数据结构与算法(冒泡排序).ppt

《数据结构与算法(冒泡排序).ppt》由会员分享，可在线阅读，更多相关《数据结构与算法(冒泡排序).ppt（15页珍藏版）》请在优知文库上搜索。

1、 数据结构与算法排序 ： 冒泡排序数据结构与算法数据结构与算法本节学习要点本节学习要点l 了解排序的基本概念了解排序的基本概念l 理解冒泡排序的算法思想（重点）理解冒泡排序的算法思想（重点）l 使用使用JAVA语言实现冒泡排序（难点）语言实现冒泡排序（难点） 教学课时：教学课时：1课时课时数据结构与算法数据结构与算法一 排序概述什么是排序什么是排序将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来顺次排列起来。存放在数据表中存放在数据表中按关键字排序按关键字排序排序的目的是什么？排序的目的是什么？ 便于查找！便于查找！ 通常是如何排序的？通常是如何排序的？ 两个基本操

2、作两个基本操作！ 比较比较比较两个关键字的大小比较两个关键字的大小 移动移动 将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置数据结构与算法数据结构与算法一 排序概述排序的优劣排序的优劣 排序算法的好坏如何衡量？排序算法的好坏如何衡量？ 时间效率时间效率 排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数） 空间效率空间效率 占内存辅助空间的大小占内存辅助空间的大小 稳定性稳定性 若两个记录若两个记录A A和和B B的关键字值相等，但排序后的关键字值相等，但排序后A A、B B的先后次的先后次 序保持不变，则称这种排序算法是稳定的。序保持不变，则称这种排

3、序算法是稳定的。原始记录：原始记录：张三，张三，16、 李四，李四，18、 王五，王五，17、赵六，赵六，17 排序排序1： 张三，张三，16 、王五，王五，17、 赵六，赵六，17、李四，李四，18 排序排序2： 张三，张三，16、 赵六，赵六，17、 王五，王五，17、李四，李四，18 稳定稳定不稳定不稳定数据结构与算法数据结构与算法一 排序概述若待排序记录都在内存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排内部排序序。内部排序内部排序反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序外部排序。外部排序外部排序数据结构与算法

4、数据结构与算法一 排序概述内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程。内部排序的方法内部排序的方法经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区基于不同的“扩大扩大” 有序序列长度的方法方法，内部排序方法大致可分下列几种类型：交换排序交换排序插入排序插入排序选择排序选择排序归并排序归并排序基数排序基数排序数据结构与算法数据结构与算法二 冒泡排序 冒泡排序是一种极其简单的排序算法，它依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“

5、浮”到数列的顶端。基本思想基本思想大（重）的下沉大（重）的下沉小（轻）的上浮小（轻）的上浮数据结构与算法数据结构与算法二 冒泡排序冒泡排序算法的执行过程如下：1. 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。3. 针对所有的元素重复以上的步骤，除了最后一个。4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。执行过程执行过程数据结构与算法数据结构与算法二 冒泡排序7676181899993535121218187676999935351212181876

6、769999353512121818767635359999121218187676353512129999关键字序列关键字序列 T =（ 76，18，99，35，12 ）第一趟第一趟 排序过程演示执行过程执行过程数据结构与算法数据结构与算法二 冒泡排序执行过程执行过程76761818999935351212181835351212767699991818121235357676999918187676353512129999第一趟第一趟第二趟第二趟第三趟第三趟12121818353576769999第四趟第四趟初初 态态冒泡排序过程演示数据结构与算法数据结构与算法二 冒泡排序分析总结分析总结

7、关键字序列关键字序列 T =（ 76，18，99，35，12 ）序列长度为 5，共进行了 4 趟排序：第 1 趟：进行了 4 次比较第 2 趟：进行了 3 次比较第 3 趟：进行了 2 次比较第 4 趟：进行了 1 次比较结论：结论：n个关键字要进行个关键字要进行n-1趟排序；趟排序； 第第1趟要比较趟要比较n-1次，第次，第i趟要比较趟要比较n-i次。次。 两两比较、逐趟比较两两比较、逐趟比较每趟结束时，都能找出每趟结束时，都能找出一个最大值，并将其移一个最大值，并将其移动到最后面的位置。动到最后面的位置。数据结构与算法数据结构与算法三冒泡排序算法分析算法分析最好情况：最好情况：初始排列已经

8、有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。最坏情形最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n) 做了n- i 次关键码比较，执行了n-i 次对象交换。因此：因此：时间效率：时间效率：O O（n n2 2) ) 因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：O O（1 1） 只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳 定定 性：性： 稳定稳定 相同元素相同元素在在排序前后的次序未改变排序前后的次序未改变数据结构与算法数据结构与算法三 程序实现程序实现程序实现分析可得：N个数字要排序完成，总共进行进行N-1趟排序，每趟排序，每i趟的

9、排序次数为趟的排序次数为(N-i)次次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数数据结构与算法数据结构与算法三 程序实现程序实现程序实现示例程序：示例程序：数据结构与算法数据结构与算法四 课外拓展操作实践操作实践思考：能否设计一个双向冒泡排序算法？使得一趟排序一趟排序之后，记录的无序序列Rs.t将变为变为：Rs最小、Rt最大！ 初态：初态： 21，25，49， 25， 16， 08第第1趟趟 21，25，25， 16， 08， 4908，21，25， 25， 16， 49第第2趟趟 08，21，25， 16， 25， 4908，16，21， 25， 25， 49第第3趟趟 08，16，21， 25， 25， 4908，16，21， 25， 25， 49用JAVA 语言实现上述双向冒泡排序算法