数据结构-第10章-内部排序.ppt

《数据结构-第10章-内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章内部排序讨论各种内部排序方法：插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及时间复杂性的分析。比较各种内部排序方法。1目录10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序10.6基数排序10.7各种内部排序方法的比较讨论2排序（sorting）1.基本概念将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。假设含n个记录的序列为{R1，R2，…，Rn}(※）其相应的关键字序列为{K1，K2，…，Kn}10.1概述3需确定1，2，…，n

2、的一种排列p1，p2，…，pn，使其相应的关键字满足如下的非递减（或非递增）关系Kp1Kp2…Kpn即使序列(※）成为一个按关键字有序的序列{Rp1，Rp2，…，Rpn}这种操作过程称为排序。排序(接上页)基本概念4基本概念排序方法是稳定的设Ki=Kj（lin，1jn，i≠j），且在排序前的序列中Ri领先于Rj（即i＜j），在排序后的序列中Ri仍领先于Rj。排序方法是不稳定的设Ki=Kj（lin，1jn，i≠j），且在排序前的序列中Ri领先于Rj（即i＜j），在排序后的序列中Rj领先于Ri。52.排序

3、方法分类按照文件所处的位置不同：内部排序待排序记录存放在计算机内存中进行的排序过程。外部排序排序过程中有内、外存间信息的传递及交换的排序过程。6排序方法分类按排序时使用的原理插入排序、交换排序、选择排序、归并排序、基数排序。按照所需的工作量简单的排序方法，其时间复杂度为O（n2）；先进的排序方法，其时间复杂度为O（nlogn）；基数排序，其时间复杂度为O（d·n）。73.基本操作比较两个关键字的大小；将记录从一个位置移动至另一个位置。84.存储结构（1）以一维数组作为存储结构（2）以静态链表作为存储结构（链表排序）（3）采

4、用辅助表排序（地址排序）待排序记录存储在数组中，同时另设一个指示各个记录存储位置的地址向量。在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，排序结束后再按照地址向量中的值调整记录的存储位置。95.排序方法分析排序的时间开销:排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。一般都按平均情况进行估算。对于那些受对象关键字序列初始排列及对象个数影响较大的，需要按最好情况和最坏情况进行估算。衡量排序方法的标准排序时所需要的平均比较次数排序时所需要的平均移动

5、排序时所需要的平均辅助存储空间101.直接插入排序(StraightInsertionSort)概念将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。例：已排序的一组记录排列如下：12，33，45，57，76现将关键字40记录插入上述序列中12，33，40，45，57，7610.2插入排序11算法的基本思路直接插入排序设有n个待排记录存放在r[1..n]中，将第i(2≤i≤n)个记录插入到已排好序的有序表r[1..i-1]中的过程为：从r[i-1]起往前搜索，若r[i]

6、则将r[j]向后移动，直至找到第i个记录的位置。12算法10.1直接插入排序voidInsertSort（SqList&L）{for(i=2;i<=L.Length;++i)ifLT(L.r[i].key,L.r[i-1].key{L.r[0]=L.r[i]；L.r[i]=L.r[i-1]；for(j=i-2;LT(L.r[0].key,L.r[j].key);--j）L.r[j+l]=L.r[j];L.r[j+l]=L.r[0];}}13例子直接插入排序初始关键字：(42)41336774233733i=2：(41)(

7、4142)336774233733i=3：(33)(334142)6774233733i=4：(33)(33414267)74233733i=5：(33)(3341426774)233733i=6：(23)(233341426774)3733i=7：(37)(23333741426774)33i=8：(33)(2333333741426774)14时间复杂性分析直接插入排序若设待排序的对象个数为L.length=n，则该算法的主程序执行n-1趟。关键字比较次数和对象移动次数与对象关键字的初始排列有关。最好情况下，排序前对象

8、已经按关键字大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键字比较1次，总的关键字比较次数为n-1，对象移动次数为0。最坏情况下，排序前对象已经按关键字大小从大到小有序（逆序），需比较和移动次数为多少？15直接插入排序时间复杂性分析若待排序对象序列中出现各种可能排列的概率相同，则可取上