第八章_排序A.pptVIP

数据结构课程的内容 内部排序内容简介: 8.2 插入排序 1) 直接插入排序 ２) 二分插入排序 ４）希尔（shell）排序（又称缩小增量排序） 例：关键字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），请写出希尔排序的具体实现过程。 课堂练习： 原始序列： 256，301， 751，129，937，863，742，694，076，438 原始序列： 256，301，751，129，937，863，742，694，076，438 8.3 交换排序 1) 冒泡排序 起泡排序过程示例 : 冒泡排序的算法分析 2） 快速排序 例1：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序的算法步骤。 例2：关键字序列 T=(21，25，49，25*，16，08），请写出快速排序算法的一趟实现过程。 快速排序算法效率分析： 讨论. “快速排序”是否真的比任何排序算法都快？ 课堂练习：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。 21，25，49， 25*，16， 08 21，25，25*，16， 08 ，[ 49] 21，25， 16， 08 ，[25*，49] 21，16， 08 ，[25， 25*，49] 16，08 ，[21， 25， 25*，49] 08，[ 16， 21， 25， 25*，49] 初态： 第1趟 第2趟 第3趟 第4趟 第5趟 如何起泡排序需多少趟,每趟需循环次数? 第1趟:n-1次 第2趟:n-2次 … (至多)第n-1趟:1次 template class T1,class T2 void seqlistT1,T2::mp_sort() {//冒泡排序，从小到大 int i,j,k; elemT1,T2 x; j=1;k=1; while((jn)(k0)) {k=0;//计数每趟交换次数，若为0，则可以停止 for(i=1;i=n-j;i++) if(data[i+1].keydata[i].key) { k++;x=data[i];data[i]=data[i+1];data[i+1]=x; } j++; } } 起泡排序算法分析与实现： 时间效率：O（n2) —因为要考虑最坏情况 空间效率：O（1） —只在交换时用到一个缓冲单元 稳 定 性： 稳定 —25和25*在排序前后的次序未改变 详细分析： 最好情况：初始排列已经有序，只执行一趟起泡，做 n-1 次关键码比较，不移动对象。O(n) 最坏情形：初始排列逆序，算法要执行n-1趟起泡，第i趟(1? i? n) 做了n- i 次关键码比较，执行了n-i 次对象交换。此时的比较总次数KCN和记录移动次数RMN为： O（n2） O（n2） 解决方法： 　　设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 关键问题⑴：如何记载一趟排序过程中交换的多个记录？ 05 98 12 69 38 53 81 05 98 69 81 12 交换 38 交换 53 交换 起泡排序算法方法二： 关键算法描述： if （data[j].keydata[j+1].key）{ data[j]←→data[j+1]； exchange=j； } 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟起泡排序的范围是data[1] ~ data[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 关键问题⑵：如何确定起泡排序的范围？ 05 98 12 69 38 53 81 05 98 69 81 12 交换 38 交换 53 交换 关键算法描述： bound=exchange; for (j=1; jbound; j++) if （data[j].keydata[j+1].key）{ data[j]==data[j+1]； exchange=j； } 05 98 12 69 38 53 81 解决方法： 在每一趟起泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录交换，exchange的值就会大于0。这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录交换，从而判别整个起泡排序的结束。 关键问题⑶：如何判别起泡排序的结束？ 关键算法描述： while (exchange) {