复习2,查找和排序.ppt

冒泡排序 关键问题⑴：如何记载一趟排序过程中冒泡的多个记录？ 算法描述： if （r[j]r[j+1]）{ r[j]←→r[j+1]； exchange=j； } 解决方法： 设变量exchange记载记录冒泡的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次冒泡的位置，且从此位置以后的所有记录均已经有序。 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟冒泡排序的范围是r[1] ~ r[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 冒泡排序 关键问题⑵：如何确定冒泡排序的范围？ 05 98 12 69 38 53 81 05 98 69 81 12 冒泡 38 冒泡 53 冒泡 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟冒泡排序的范围是r[1] ~ r[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 冒泡排序 关键问题⑵：如何确定冒泡排序的范围？ 算法描述： bound=exchange; for (j=1; jbound; j++) if （r[j]r[j+1]）{ r[j]==r[j+1]； exchange=j； } 05 98 12 69 38 53 81 解决方法： 在每一趟冒泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录冒泡，exchange的值就会大于0。这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录冒泡，从而判别整个冒泡排序的结束。 冒泡排序 关键问题⑶：如何判别冒泡排序的结束？ 解决方法： 在每一趟冒泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录冒泡，exchange的值就会大于0。这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录冒泡，从而判别整个冒泡排序的结束。 冒泡排序 关键问题⑶：如何判别冒泡排序的结束？ 算法描述： while (exchange) { 执行一趟冒泡排序； } void BubbleSort(int r[ ], int n) { exchange=n; while (exchange) { bound=exchange; exchange=0； for (j=1; jbound; j++) if (r[j]r[j+1]) { r[j]←→r[j+1]； exchange=j； } } } 冒泡排序算法 冒泡排序 最坏情况（反序）： 冒泡排序的时间性能分析 最好情况（正序）： 冒泡排序 比较次数：n-1 移动次数：0 5 4 3 2 1 时间复杂度为O(n)； 4 3 2 1 5 3 2 1 4 5 2 1 3 4 5 1 2 3 4 5 比较次数： 移动次数： 2 ) 1 ( 1 - = ? = n n (n-i) n-1 i 2 ) 1 ( 1 - = ? = n 3n 3(n-i) n-1 i 冒泡排序 如何改进冒泡排序? 1 2 3 4 5 需扫描1趟 5 4 3 2 1 需扫描n-1趟 5 1 2 3 4 需扫描2趟 2 3 4 5 1 需扫描n-1趟 造成不对称的原因是什么? 冒泡排序 如何改变不对称性? 2 3 4 5 1 在排序过程中交替改变扫描方向——双向冒泡排序 2 3 4 1 5 1 2 3 4 5 快速排序 改进的着眼点：在冒泡排序中，记录的比较和移动是在相邻单元中进行的，记录每次交换只能上移或下移一个单元，因而总的比较次数和移动次数较多。 交换排序 减少总的比较次数和移动次数 增大记录的比较和移动距离 较大记录从前面直接移动到后面 较小记录从后面直接移动到前面 快速排序的基本思想 首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。 交换排序 ⑴如何选择轴值？ ⑵如何实现分割（称一次划分）？ ⑶如何处理分割得到的两个待排序子序列？ ⑷如何判别快速排序的结束？ 需解决的关键问题? 选择轴值的方法： 1.使用第一个记录的关键码； 2.选取序列中间记录的关键码； 3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中