排序的基本概念(P200)课件.ppt

《排序的基本概念(P200)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章排序排序的基本概念（P200）排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。排序的基本概念排序的分类1.内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中2.外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。排序的基本概念排序算法的性能指标1.时

2、间开销：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.空间开销：辅助存储空间3.算法的稳定性排序算法的存储结构从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。intr[n+1];//待排序记录存储在r[1]~r[n]，r[0]留做他用假定2：将待排序的记录序列排序为升序序列。10.2冒泡排序交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置

3、。冒泡排序的改进。（P202）冒泡排序的时间性能分析最好情况（正序）：比较次数：n-1移动次数：0时间复杂度为O(n)。最坏情况（反序）：54321时间复杂度为O(n2)。43215321452134512345比较次数：移动次数：2)1(1-=å=nn(n-i)n-1i2)1(1-=å=n3n3(n-i)n-1i平均情况：时间复杂度为O(n2)。冒泡排序的时间性能分析冒泡排序的性能分析在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。冒泡排序是一种稳定的排序方法。选择排序的主要操作是选择，其主要思想是:每

4、趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。10.3选择排序简单选择排序的主要思想是：第i趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。需解决的关键问题?⑴如何在待排序序列中选出关键码最小的记录？⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置？简单选择排序简单选择排序示例0821i=2最小者08交换21,08最小者16交换25,16最小者21交换49,212128i=12516490808i=32108284921284916251625i=4最小者25交换25,28i=5最小者28不交换49

5、2108281625254921081628252849210816282528无序区只有一个记录简单选择排序示例212825164908kkk08问题1：如何在无序区中选出关键码最小的记录？解决方法：设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。问题1：如何在无序区中选出关键码最小的记录？解决方法：设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。算法描述：k=i;for(j=i+1;j<=n;j++)if(r[j]

6、，则r[i]是无序区第一个记录，所以，将index所记载的关键码最小的记录与r[i]交换。算法描述：if(k!=i)r[i]←→r[k];voidSelectSort(Recordr[],intn){for(i=0;i

7、1152341253412354123451234比较次数：)()1(21211nOnninni=-=-å-=）（简单选择排序的时间复杂度为O(n2)。10.4插入排序插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……直接插入排序基本思想：在插入第i（i＞1）个记录时，前面的i