数据结构查找与排序.ppt

《数据结构查找与排序.ppt》由会员分享，可在线阅读，更多相关《数据结构查找与排序.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一部分 查找二分查找,Hash表二分查找考点二分查找考点条件：顺序存储,按关键字有序时间复杂度分析（log2n）最多要比较的次数（2n+1）,理由：n个结点的判定树的深度与n个结点的完全二叉树深度相同。折半查找的二叉判定树1、请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个记录的顺序表中进行二分查找,最大的比较次数是多少？答：数据元素初始状态按关键字有序数据元素初始状态按关键字有序 最大比较次数应为最大比较次数应为 2n +12、设顺序表为4,6,12,38,40,67,80用二分法查找72,需要进行的比较次数为（）A、3 B、n-1 C、n+1 D、n 答案：A 例如：3、试

2、用于折半查找的表的存储方式及元素排列要求是、试用于折半查找的表的存储方式及元素排列要求是顺序存储顺序存储,按关键字有序按关键字有序。4、对有10个元素的有序表,采用二分查找,需要比较4次方可找到的元素个数为 3 。5、设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,765,897,908.试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度。Hash查找和Hash表的创建常用Hash函数和解决冲突方法Hash表的创建与平均查找长度的计算时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及hash表的装填因子有关）例

3、如例如1、对包含N个元素的散列表进行检索,平均检索长度是（）A、O(log2N)B、O(N)C、不直接依赖于N D、上述三者都不是 答案：C2、已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（key）=keyMOD11,哈希表HT的长度为11,采用二次探二次探测测再散列法再散列法（d=12,-12,22,-22,32,）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。位置012345678910关键字336027415387149冲突次数04501163查找时比较次数15612274查找成功的平均查找长度=（1+5+6+1+2+

4、2+7+4）/8=28/8=3.53、已知关键码集合53,17,19,61,98,75,79,63,46,49要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内,若发生冲突则用开地址法的线索探测法解决,要求写出的选用的散列函数,形成的散列表：计算查找成功的平均搜索长度。（设等概率情况）答：选选用的散列函数用的散列函数为：H(K)=100+K%10位置100101102103104105106107108109关键字79614953637546179819冲突次数1030100000查找时比较次数2141211111查找成功时的平均搜索长度：（

5、2+1+4+1+2+1+1+1+1+1）/10=1.5第二部分 排序各种排序算法的特性时间性能（最好、最坏、平均情况）空间复杂度稳定性常见排序算法堆排序堆排序-堆的定义堆的定义,创建堆创建堆,堆排序（厦大堆排序（厦大3次次,南航南航2次次,南大南大3次）次）快速排序快速排序基数排序基数排序插入排序插入排序希尔排序希尔排序冒泡排序冒泡排序简单选择排序简单选择排序归并排序归并排序一、基于选择的排序1.简单选择排序简单选择排序2.堆排序（堆排序（Heap Sort）算法关键部分：算法关键部分：for(i=1;i N;i+)min=i;for (j=i+1;j=N;j+)if (Aj314431353

6、135 “筛选筛选”：除了堆顶元素之外：除了堆顶元素之外,其余元素都满足堆的性质其余元素都满足堆的性质,把这样一个数据集合把这样一个数据集合做成一个堆做成一个堆,这个过程叫做这个过程叫做“筛选筛选”。筛选：实际上是一个寻找的过程筛选：实际上是一个寻找的过程,由于堆顶元素是唯一一个不满足堆性质的元由于堆顶元素是唯一一个不满足堆性质的元素素,则下面需要在下面的各个位置中则下面需要在下面的各个位置中,寻找它该处于的位置寻找它该处于的位置 首先比较该堆顶元素与其两个孩子的大小首先比较该堆顶元素与其两个孩子的大小,取两个孩子中较大的一个取两个孩子中较大的一个,若若比该元比该元素大素大,则把这个孩子提升一

7、个层次则把这个孩子提升一个层次,再继续比较原堆顶元素与这个孩子原来的再继续比较原堆顶元素与这个孩子原来的孩子孩子,直到发现某个层次上直到发现某个层次上,原来元素的两个孩子均不大于（小于或等于）原原来元素的两个孩子均不大于（小于或等于）原堆顶元素堆顶元素,或者到了某个叶子结点位置上为止。或者到了某个叶子结点位置上为止。问题问题1：筛选筛选 问题问题2：堆的创建堆的创建 依靠依靠“筛选筛选”的过程的过程 “创建堆创建堆”是指如何将是指如何将已已经经存在的存在的N个元素个元素按堆（最大堆或按堆（最大堆或最小堆）的要求存放在一个一最小堆）的要求存放在一个一维维数数组组中。中。在在线线性性时间时间复复杂

8、杂度度下下创创建堆。具体分两步建堆。具体分两步进进行：行：第一步第一步,将将N个元素按个元素按输输入入顺顺序存入二叉序存入二叉树树中中,这这一步只要求一步只要求满满足足完全二叉完全二叉树树的的结结构特性构特性,而不管其有序性。而不管其有序性。第二步第二步,按照完全二叉按照完全二叉树树的的层层次遍次遍历历的反序的反序,找到第一个非叶子找到第一个非叶子结结点点,从从该结该结点开始点开始“筛选筛选”,调调整各整各结结点元素点元素,然后按照反序然后按照反序,依次做筛选依次做筛选,直到直到做完根结点元素做完根结点元素,此此时时即构成一个堆。即构成一个堆。时间复杂性时间复杂性 T(n)=O（nlogn）,

9、与数据初始状态无关与数据初始状态无关,堆排序的最佳、堆排序的最佳、最差以及平均时间复杂度均为最差以及平均时间复杂度均为O(nlog2n)空空 间复杂性间复杂性S(n)=O（1）稳定性：稳定性：不稳定。不稳定。因为是跳跃式的比较与交换。因为是跳跃式的比较与交换。反例如下：反例如下：不稳定！不稳定！排序前排序前2 领先于领先于 22 落后于落后于 2排序后排序后 堆排序特性（属于堆排序特性（属于选择排序选择排序大类）大类）2 1 2 1 2 2 211223211223121223 适用场合：数据量比较大的情况适用场合：数据量比较大的情况,因为初始构建堆所需比较次数较多。因为初始构建堆所需比较次数

10、较多。1.设关键字序列为：49,38,66,90,75,10,20。请把这些关键字调整成堆顶元素取最小值的堆。（画出过程）493890751066204938907566102010389075662049例如：例如：2序列是堆的是(C )。A75,65,30,15,25,45,20,10 B75,65,45,10,30,25,20,15 C75,45,65,30,15,25,20,10 D75,45,65,10,25,30,20,153、对关键码序列45,30,55,21,94,66,90,82用堆排序方法进行逆序排序,请画出建立的初始堆以及调整3个关键码的示意图。三、基于交换的排序三、基于

11、交换的排序1.冒泡排序冒泡排序（Bubble Sort）2.快速排序（快速排序（Quick Sort）1.冒泡排序（冒泡排序（Bubble Sort）算法思想）算法思想依次比较相邻的两个记录的关键字依次比较相邻的两个记录的关键字,若两个记录是反序的若两个记录是反序的(即前一个记录的关即前一个记录的关键字键字大于大于后前一个记录的关键字后前一个记录的关键字),则进行交换则进行交换,直到没有反序的记录为止。直到没有反序的记录为止。冒泡排序时间复杂度冒泡排序时间复杂度 最好情况最好情况(正序正序)：比较次数：比较次数：n-1；移动次数：；移动次数：0；最坏情况最坏情况(逆序逆序)：冒泡排序算法分析冒

12、泡排序算法分析比较次数比较次数：(n-i)=n-1i=1n(n-1)2移动次数移动次数：3(n-i)=n-1i=13n(n-1)2时间复杂度时间复杂度：T(n)=O(n)空间复杂度：空间复杂度：S(n)=O(1)稳定性：稳定（相邻元素的比较与交换）稳定性：稳定（相邻元素的比较与交换）2.快速排序算法思想：快速排序算法思想：是一种递归算法是一种递归算法,每次根据某个值每次根据某个值,将待排序列分成两部分将待排序列分成两部分,一部分序列的元素一部分序列的元素关键字比该值小关键字比该值小,另一部分序列的元素关键字比该值大（或等于）另一部分序列的元素关键字比该值大（或等于）,然后再分然后再分别对这两部

13、分进行如上操作别对这两部分进行如上操作,直至排序完成。直至排序完成。j前移前移2个位置后个位置后,Rj放在放在Ri的位置的位置:29 23 38 22 45 67 31ij初始关键字序列初始关键字序列:j29 29 38 22 45 23 67 31i029 23 22 45 38 67 31iji后移后移1个位置后个位置后,Ri放在放在Rj的位置的位置:29 23 22 45 38 67 31ijj前移前移2个位置后个位置后,Rj放在放在Ri的位置的位置:29 23 22 29 45 38 67 31i ji后移后移1个位置后个位置后,i和和j的位置重合的位置重合:设有设有6个待排序的记录个

14、待排序的记录,关键字分别为关键字分别为29,38,22,45,23,67,一趟快速排序一趟快速排序的过程如的过程如图图所示：所示：快速排序的平均性能为快速排序的平均性能为O(nlog2n),在同数量级算法中综合考虑在同数量级算法中综合考虑,是最是最好的一种内部排序方法好的一种内部排序方法快速排序算法在快速排序算法在最坏最坏情况下（待排序列情况下（待排序列正序正序或或逆序逆序）,每次划分只得每次划分只得到比上一次少到比上一次少 一个记录的子序列一个记录的子序列,另一个子序列却为空另一个子序列却为空,即划分得极不即划分得极不均匀均匀,此时需要执行此时需要执行n-1次递归调用次递归调用,且比较的次数

15、是且比较的次数是n(n-1)/2,所以快所以快速排序收到序列初始状态的影响速排序收到序列初始状态的影响,在在最坏最坏情况下算法情况下算法时间复杂度为时间复杂度为O(n2)快速排序算法分析快速排序算法分析快速排序算法关键字的比较和交换也是跳跃式进行的快速排序算法关键字的比较和交换也是跳跃式进行的,所以快速排序所以快速排序算法也是一种算法也是一种不稳定不稳定的排序方法。的排序方法。由于进行了递归调用由于进行了递归调用,需要一定数量的栈需要一定数量的栈O(log2n)作为辅助空间作为辅助空间例如例如1、快速排序算法在 数据元素按关键字有序的 情况下最不利于发挥其长处。2、设关键字序列为：49,38,

16、66,80,70,15,22,欲对该序列进行从小到大排序。采用待排序列的第一个关键字作为枢轴,写出快速排序法的一趟和二趟排序之后的状态答：第一趟之后：22,38,15,49,70,80,66 第二趟之后：15,22,38,49,66,70,80例例 给定定 N=10 个整数，范个整数，范围介于介于 0 到到 999(M=1000)之之间。是否。是否可以在可以在线性的性的时间内把它内把它们排序排序?单关键字的单关键字的基数排序基数排序输入输入:64,8,216,512,27,729,0,1,343,1250桶：桶：123456789（3位数可以看成个位数可以看成个3关键字，关键字，再按再按“次位

17、优先法次位优先法”排序）排序）0轮次轮次 1151234364125216278729轮次轮次 20151234364125216278729轮次轮次 30185122161252772934364输出输出:0,1,8,27,64,125,216,343,512,729时间复杂性：时间复杂性：T=O(D(N+R)其中其中D是轮次是轮次,N 是元素个数是元素个数,R 是桶的数量是桶的数量.空间复杂性：空间复杂性：S=O(N+R),N 是元素个数是元素个数,R 是桶的数量是桶的数量.稳定性：稳定性：稳定稳定用用链式链式储存更便于储存更便于分配与收集分配与收集南航南航2010年年二、解答题(共80分

18、，8题，每题10分)23已知数据序列为(86，8，234，50，116，64，68，453，24，142)，给出基数排序过程的示意图。0桶：桶：123456789轮次轮次 2081161426424轮次轮次 382450234116648668输出输出:8,24,50,64,68,86,116,142,234,453南航南航2013年年4（10分）已知数据序列为(76，58，234，5，16，164,28，423，24，102)，给出基数排序过程的示意图。50轮次轮次 1142453234868641166824504532348668142453排序方法平均时间复杂度最坏情况下时间复杂度额外空间复杂度稳定性简单选择排序O(NO(N2 2)O(NO(N2 2)O(1)O(1)不稳定不稳定直接插入排序O(NO(N2 2)O(NO(N2 2)O(1)O(1)稳定稳定冒泡排序O(NO(N2 2)O(NO(N2 2)O(1)O(1)稳定稳定希尔排序O(NO(Nd d)(1d1.5)(1d0，O(N4/3)）1,2,3,4,6,9,8,12,18,27,16,24,36,54,81（O(N(logN)2)）稳定性：不稳定，因为是跳跃式的比较和交换稳定性：不稳定，因为是跳跃式的比较和交换