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

数据结构与算法,排序：冒泡排序,本节学习要点,了解排序的基本概念 理解冒泡排序的算法思想（重点）使用JAVA语言实现冒泡排序（难点）教学课时：1课时,一 排序概述,什么是排序,将一组杂乱无章的数据按一定的规律顺次排列起来。,存放在数据表中,按关键字排序,排序的目的是什么？,便于查找！,通常是如何排序的？两个基本操作！比较比较两个关键字的大小移动 将记录从一个位置移动到另一个位置,一 排序概述,排序的优劣,排序算法的好坏如何衡量？时间效率 排序速度（即排序所花费的全部比较次数）空间效率 占内存辅助空间的大小稳定性 若两个记录A和B的关键字值相等，但排序后A、B的先后次 序保持不变，则称这种排序算法是稳定的。,原始记录：张三，16、李四，18、王五，17、赵六，17 排序1：张三，16、王五，17、赵六，17、李四，18 排序2：张三，16、赵六，17、王五，17、李四，18,一 排序概述,若待排序记录都在内存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。,内部排序,反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。,外部排序,一 排序概述,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,内部排序的方法,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：,交换排序,插入排序,选择排序,归并排序,基数排序,二 冒泡排序,冒泡排序是一种极其简单的排序算法，它依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。,基本思想,大（重）的下沉,小（轻）的上浮,二 冒泡排序,冒泡排序算法的执行过程如下：比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。,执行过程,二 冒泡排序,关键字序列 T=（76，18，99，35，12）,第一趟 排序过程演示,执行过程,二 冒泡排序,第一趟,第二趟,第三趟,第四趟,初 态,冒泡排序过程演示,二 冒泡排序,关键字序列 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次。两两比较、逐趟比较,每趟结束时，都能找出一个最大值，并将其移动到最后面的位置。,三冒泡排序,最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1 i n)做了n-i 次关键码比较，执行了n-i 次对象交换。,因此：时间效率：O（n2)因为要考虑最坏情况空间效率：O（1）只在交换时用到一个缓冲单元稳 定 性：稳定 相同元素在排序前后的次序未改变,三 程序实现,分析可得：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(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 语言实现上述双向冒泡排序算法,