数据结构-ch10

《数据结构-ch10》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构第十章内部排序【学习目标】1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。2．掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。【重点和难点】希尔排序、快速排序和归并排序等高效方法是本章的学习重点和难点。【知识点】排序、直接插入排序、希尔排序、起泡排序、快速排序、选择排序、归并排序、排序方法的综合比较。第十章内部排序10.1概述10.2插入排序10.3快速排序10.4选择排序10.5归并排序1

2、0.1概述一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。例如：将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为14,23,36,49,52,58,61,75,80,97一般情况下，假设含n个记录的序列为{R,R,…，R}12n其相应的关键字序列为{K,K,…，K}12n这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：K≤K≤…≤Kp1p2pn按此固有关系将上式记录序列重新排列为{R,R,…，R}p1p2pn的操作称作排序。二、排序算法的稳定性如果在待排序

3、的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。排序之前:{·····R(K)·····R(K)·····}ij排序之后:{·····R(K)R(K)···········}ij三、内部排序与外部排序根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。内部排序指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中。外部排序指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将一部分数据元素放置在内存，另一部分数据元素放

4、置在外设上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。本章只讨论常用的内部排序方法。四、排序算法的效率时间复杂度：在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；空间复杂度：执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。10.2插入

5、排序一、直接插入排序(InsertSort)基本思想：当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序，此时，用v[i]的关键码与V[i-1],V[i-2],…的关键码顺序进行比较，找到插入位置即将V[i]插入，原来位置上对象向后顺移。有序序列R[1..i-1]无序序列R[i..n]R[i]有序序列R[1..i]无序序列R[i+1..n]由此实现一趟插入排序的步骤为：1、在R[1..i-1]中查找R[i]的插入位置，即确定j(0≤j＜i)使得R[1..j].key≤R[i].key＜R[j+1..i-1].key2、将R[j+1..i-1

6、]中的记录后移一个位置；3、将R[i]插入到j+1的位置。直接插入排序举例i(0)(1)(2)(3)(4)(5)temp[21]254925*1608251[2125]4925*1608492[212549]25*160825*3[212525*49]1608164[16212525*49]08085[0816212525*49]直接插入排序算法完整的插入排序算法为：voidInsertSort(S_TBL&p){for(i=2；i<=p->length；i++)if(p->elem[i].keyelem[i-1].key)/*小于时，需将elem[i]

7、插入有序表*/{p->elem[0].key=p->elem[i].key；/*为统一算法设置监测*/for(j=i-1；p->elem[0].keyelem[j].key；j--)p->elem[j+1].key=p->elem[j].key；/*记录后移*/p->elem[j+1].key=p->elem[0].key；/*插入到正确位置*/}}直接插入排序效率分析直接插入排序算法简单、容易实现，只需要一个记录大小的辅助空间用于存放待插入的记录（在C语言中，我们利用了数组中的0单元）和两个int型变量。从上述排序过程可见，排序中的两个基本操作是：（关

8、键字间的）比较和（记录的