吴及《数据与算法课程讲义》清华大学：3基本非数值算法2-排序

《吴及《数据与算法课程讲义》清华大学：3基本非数值算法2-排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2015-2016秋季学期数据与算法课程讲义基础非数值算法吴及wuji_ee@tsinghua.edu.cn清华大学电子工程系2015年11月内容提要排序概念简单排序方法快速排序归并排序堆排序数据与算法吴及2(20230253)电子工程系排序数据表(????????)，它是待排序数据对象的有限集合数据对象有多个属性域，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键码(???)所谓排序,就是根据关键码递增或递减的顺序,把数据对象依次排列起来,使一组任意排列的对象变成一组按其关

2、键码线性有序的对象。?个对象的序列为?0,?1,⋯,??−1，对应关键码为?0,?1,⋯,??−1确定一种排列?0,?1,⋯,??−1使各关键码满足非递减关系：?≤?≤⋯≤??0?1??−1或者非递增关系：?≥?≥⋯≥??0?1??−1数据与算法吴及3(20230253)电子工程系排序排序算法的稳定性:如果在对象序列中有两个对象??和??，它们的排序码??=??,且在排序之前,对象??排在??前面如果在排序之后,对象??仍在对象??的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的

3、内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。数据与算法吴及4(20230253)电子工程系排序算法的性能评估排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象排序码序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。算法执行时所需的附加存储

4、:评价算法好坏的另一标准。寻找性能更好的排序算法一直是计算机科学领域的重要课题之一数据与算法吴及5(20230253)电子工程系基本操作交换是排序算法中的基本操作，为了讲解和程序实现的方便，先实现交换函数template//基于模板定义inlinevoidexch(T&e1,T&e2){Ttmp;//临时变量tmp=e1;e1=e2;e2=tmp;}数据与算法吴及6(20230253)电子工程系内容提要排序概念简单排序方法快速排序归并排序堆排序数据与算法吴及7(20

5、230253)电子工程系一次冒泡ASORTINGEXAMPLE1ASORTINGEXAMPEL2ASORTINGEXAMEPL3ASORTINGEXAEMPL4ASORTINGEXAEMPL5ASORTINGEAXEMPL6ASORTINGAEXEMPL7ASORTINAGEXEMPL8ASORTIANGEXEMPL9ASORTAINGEXEMPL10ASORATINGEXEMPL11ASOARTINGEXEMPL12ASAORTINGEXEMPL13AASORTINGEXEMPL14AASORTINGE

6、XEMPL数据与算法吴及8(20230253)电子工程系冒泡排序ASORTINGEXAMPLE1ASORTINGEXAMPLE2AASORTINGEXEMPL3AAESORTINGEXLMP4AAEESORTINGLXMP5AAEEGSORTINLMXP6AAEEGISORTLNMPX7AAEEGILSORTMNPX8AAEEGILMSORTNPX9AAEEGILMNSORTPX10AAEEGILMNOSPRTX11AAEEGILMNOPSRTX12AAEEGILMNOPRSTX13AAEEGILMNO

7、PRSTX14AAEEGILMNOPRSTXAAEEGILMNOPRSTX数据与算法吴及9(20230253)电子工程系冒泡排序的实现基本实现templatevoidbubble_sort(T*a,intl,intr){inti,j;for(i=l;ii;j--)if(a[j-1]>a[j])exch(a[j-1],a[j]);}}最坏情况下，比较和交换操作的次数：?−1?−?=??−12?=1数据与算法吴及10(20230253)电子工程系冒泡

8、排序的改进一个待排序对象序列时可能不需要?−1趟起泡就能全部排好序，例中有15个对象(n=15)，执行了12趟起泡就已排好为此，在算法中增加了一个标志，用以标识本趟起泡结果是否发生了逆序和交换。如果没有发生交换则表示全部对象已经排好序，因而可以终止处理，结束算法在做了这样的改进之后，如果对象序列已经有序，那么只需要一趟起泡，算法就顺利结束了。改进的冒泡算法，最好的情况下需要?−1次比较和0次交换平均和最坏情况下，比较