《基本排序技术6h》PPT课件

《《基本排序技术6h》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章查找与排序(下)本节内容通过本单元的学习，了解、掌握有关排序的：基本概念：排序、排序分类、算法稳定性典型的排序算法:插入排序、选择排序、交换排序归并排序、基数排序排序的基本概念定义：将记录按关键字递增(递减)的次序排列起来，形成新的有序序列，称为排序。描述：设n个记录的序列为{R1,R2,…,Rn},其相应关键字序列为{K1,K2,…,Kn},需确定一种排序P1,P2,…,Pn,使其相应的关键字满足递增(升序),或递减(降序)的关系:Kp1Kp2...Kpn或Kp1Kp2….Kpn3.3基本

2、的排序技术虽然排序算法是一个简单的问题，但是从计算机科学发展以来，已经有大量的研究在此问题上。举例而言，冒泡排序在1956年就已经被研究。虽然大部分人认为这是一个已经被解决的问题，有用的新算法仍在不断的被发明。（例子：图书馆排序在2004年被发表）算法稳定性21254925*1608012345490816Exchang=125*2521490816Exchang=12525*21算法稳定性当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。(4,1)(3

3、,1)(3,7)(5,6)(3,1)(3,7)(4,1)(5,6)(保持次序)(3,7)(3,1)(4,1)(5,6)(次序被改变)不稳定排序算法可能会在相等的键值中改变纪录的相对次序。不稳定排序算法可以被特别地实现为稳定。方法是人工扩充键值的比较。然而，要记住这种次序通常牵涉到额外的空间负担。简单起见，这里用顺序存储结构描述待排序的记录。顺序存储结构（C语言描述）：#defineNntypedefstructrecord{intkey；/*关键字项*/intotherterm；/*其它项*/}；typedefst

4、ructrecordRECORD；RECORDfile[N+1]；/*RECORD型的N+1元数组*/排序算法的数据结构典型排序算法冒泡排序快速排序简单插入排序希尔排序简单选择排序堆排序归并排序基数排序二叉排序树一、冒泡排序1.指导思想：两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对元素，直到全部数列满足有序为止。冒泡排序（Bubblesort）是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换，将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排序列中的最

5、大关键字交换到最后（或最前）位置。直到全部元素有序为止。…a1a2a3…an-1an最大值2.冒泡排序算法step1从待排序队列的前端开始(a1)两两比较记录的关键字值，若ai>ai+1(i=1,2,…,n-1)，则交换ai和ai+1的位置，直到队列尾部。一趟冒泡处理，将序列中的最大值交换到an的位置。step2如法炮制，第k趟冒泡，从待排序队列的前端开始(a1)两两比较ai和ai+1（i=1,2,…n-k)，并进行交换处理，选出序列中第k大的关键字值，放在有序队列的最前端。(思考：为什么i=1,…n-k?

6、)Step3最多执行n-1趟的冒泡处理，序列变为有序。从小到大排序冒泡排序算法举例设有数列{65,97,76,13,27,49,58}比较次数第1趟{65，76，13，27，49，58}，{97}6第2趟{65，13，27，49，58}，{76，97}5第3趟{13，27，49，58}，{65，76，97}4第4趟{13，27，49}，{58，65，76，97}3第5趟{13，27}，{49，58，65，76，97}2第6趟{13}，{27，49，58，65，76，97}1总计：21次3.冒泡排序实现bubble(

7、int*item,intcount){inta,b，t;for(a=1;aitem[b])/*若逆序，则交换*/{t=item[b-1];/*它们的位置*/item[b-1]=item[b];item[b]=t;}}4.改进的冒泡排序从上述举例中可以看出，从第4趟冒泡起，序列已有序，结果是空跑了3趟。若两次冒泡处理过程中，没有进行交换，说明序列已有序，则停止交换。这就是改进

8、的冒泡算法的处理思想。用改进的冒泡算法进行处理，比较次数有所减少。对于数列{65,97,76,13,27,49,58}比较次数第1趟{65，76，13，27，49，58}，{97}6第2趟{65，13，27，49，58}，{76，97}5第3趟{13，27，49，58}，{65，76，97}4第4趟{13，27，49}，{58，65，76，97}3总计：18