数据结构查找与排序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一部分 查找,二分查找,Hash,表,二分查找考点,条件：,顺序存储,按关键字有序,时间复杂度分析（,log,2,n,）,最多要比较的次数,（,2,n,+1,）,理由：,n,个结点的判定树的深度与,n,个结点的完全二叉树深度相同。,折半查找的二叉判定树,1,、请问,满足什么条件的,顺序表,可以实施二分查找,在满足该条件的,n,个记录的顺序表中进行二分查找,最大的比较次数是多少？,答：,数据元素初始状态按关键字有序,最大比较次数应为,2,n,+1,2,、设顺序表为,4,6,12,38,40,67,80,用二分法查找,72,需要进行的比较次数为（）,A,、,3 B,、,n-1 C,、,n+1 D,、,n,答案：,A,例如：,3,、试用于折半查找的表的存储方式及元素排列要求是,顺序存储,按关键字有序,。,4,、对有,10,个元素的有序表,采用二分查找,需要比较,4,次方可找到的元素个数为,3,。,5,、设有序顺序表中的元素依次为,017,094,154,170,275,503,509,512,553,612,677,765,897,908.,试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度。,Hash,查找和,Hash,表的创建,常用,Hash,函数和解决冲突方法,Hash,表的创建,与,平均查找长度的计算,时间复杂度的分析（不依赖问题的规模,与解决冲突的方法以及,hash,表的装填因子有关）,例如,1,、对包含,N,个元素的散列表进行检索,平均检索长度是（,）,A,、,O(log,2,N)B,、,O(N),C,、不直接依赖于,N D,、上述三者都不是,答案：,C,2,、已知待散列存储的关键字序列为（,4,15,38,49,33,60,27,71,）,哈希函数为,H,（,key,）,=keyMOD11,哈希表,HT,的长度为,11,采用,二次探测再散列法,（,d=1,2,-1,2,2,2,-2,2,3,2,）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。,位置,0,1,2,3,4,5,6,7,8,9,10,关键字,33,60,27,4,15,38,71,49,冲突次数,0,4,5,0,1,1,6,3,查找时比较次数,1,5,6,1,2,2,7,4,查找成功的平均查找长度,=,（,1+5+6+1+2+2+7+4,）,/8=28/8=3.5,3,、已知关键码集合,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,位置,100,101,102,103,104,105,106,107,108,109,关键字,79,61,49,53,63,75,46,17,98,19,冲突次数,1,0,3,0,1,0,0,0,0,0,查找时比较次数,2,1,4,1,2,1,1,1,1,1,查找成功时的平均搜索长度：（,2+1+4+1+2+1+1+1+1+1,）,/10=1.5,第二部分 排序,各种排序算法的特性,时间性能（最好、最坏、平均情况）,空间复杂度,稳定性,常见排序算法,堆排序,-,堆的定义,创建堆,堆排序（厦大,3,次,南航,2,次,南大,3,次）,快速排序,基数排序,插入排序,希尔排序,冒泡排序,简单选择排序,归并排序,一、基于选择的排序,简单选择排序,堆排序（,Heap Sort,）,算法关键部分：,for(i=1;i,N;i+),min=i;,for (j=i+1;j,=,N;j+),if (,Aj,31,44,31,35,31,35,“,筛选,”：除了堆顶元素之外,其余元素都满足堆的性质,把这样一个数据集合做成一个堆,这个过程叫做“,筛选,”。,筛选：实际上是一个寻找的过程,由于堆顶元素是唯一一个不满足堆性质的元素,则下面需要在下面的各个位置中,寻找它该处于的位置,首先比较该堆顶元素与其两个孩子的大小,取两个孩子中较大的一个,若,比该元素大,则把这个孩子提升一个层次,再继续比较原堆顶元素与这个孩子原来的孩子,直到发现某个层次上,原来元素的两个孩子均不大于（小于或等于）原堆顶元素,或者到了某个叶子结点位置上为止。,问题,1,：,筛选,问题,2,：,堆的创建,依靠,“筛选”,的过程,“,创建堆,”,是指如何将,已经存在的,N,个元素,按堆（最大堆或最小堆）的要求存放在一个一维数组中。,在,线性时间复杂度,下创建堆。具体分两步进行：,第一步,将,N,个元素按输入顺序存入二叉树中,这一步只要求满足,完全二叉树的结构特性,而不管其有序性。,第二步,按照完全二叉树的层次遍历的反序,找到第一个非叶子结点,从该结点开始“筛选”,调整各结点元素,然后按照反序,依次做筛选,直到做完根结点元素,此时即构成一个堆。,时间复杂性,T(n,)=,O,（,nlogn,）,与数据初始状态无关,堆排序的最佳、最差以及平均时间复杂度均为,O(,n,log2,n,),空,间复杂性,S(n,)=,O,（,1,）,稳定性：,不稳定。,因为是跳跃式的比较与交换。,反例如下：,不稳定！,排序前,2,领先于,2,2,落后于,2,排序后,堆排序特性（属于,选择排序,大类）,2,1,2,1,2,2,2,1,1,2,2,3,2,1,1,2,2,3,1,2,1,2,2,3,适用场合：数据量比较大的情况,因为初始构建堆所需比较次数较多。,设关键字序列为：,49,38,66,90,75,10,20,。请把这些关键字调整成堆顶元素取最小值的堆。（画出过程）,49,38,90,75,10,66,20,49,38,90,75,66,10,20,10,38,90,75,66,20,49,例如：,2,序列是堆的是,(C ),。,A,75,65,30,15,25,45,20,10,B,75,65,45,10,30,25,20,15,C,75,45,65,30,15,25,20,10,D,75,45,65,10,25,30,20,15,3,、对关键码序列,45,30,55,21,94,66,90,82,用堆排序方法进行逆序排序,请画出建立的初始堆以及调整,3,个关键码的示意图。,三、基于交换的排序,冒泡排序,（,Bubble Sort,）,快速排序（,Quick Sort,）,1.,冒泡排序（,Bubble Sort,）算法思想,依次比较相邻的两个记录的关键字,若两个记录是反序的,(,即前一个记录的关键字,大于,后前一个记录的关键字,),则进行交换,直到没有反序的记录为止。,冒泡排序时间复杂度,最好情况,(,正序,),：,比较次数：,n-1,；移动次数：0；,最坏情况,(,逆序,),：,冒泡排序算法分析,比较次数,：,(n-i)=,n-1,i=1,n(n-1),2,移动次数,：,3,(n-i)=,n-1,i=1,3n(n-1),2,时间复杂度,：,T(n)=,O(n),空间复杂度：,S(n)=O(1),稳定性：稳定（相邻元素的比较与交换）,2.,快速排序算法思想：,是一种递归算法,每次根据某个值,将待排序列分成两部分,一部分序列的元素关键字比该值小,另一部分序列的元素关键字比该值大（或等于）,然后再分别对这两部分进行如上操作,直至排序完成。,j,前移,2,个位置后,Rj,放在,Ri,的位置,:,29,23,38 22 45,67 31,i,j,初始关键字序列,:,j,29,29,38 22 45 23 67 31,i,0,29,23,22 45,38,67 31,i,j,i,后移,1,个位置后,Ri,放在,Rj,的位置,:,29,23,22,45,38,67 31,i,j,j,前移,2,个位置后,Rj,放在,Ri,的位置,:,29,23,22,29,45,38,67 31,i,j,i,后移,1,个位置后,i,和,j,的位置重合,:,设有,6,个待排序的记录,关键字分别为,29,38,22,45,23,67,一趟快速排序,的过程如图,所示：,快速排序的平均性能为,O(nlog,2,n),在同数量级算法中综合考虑,是最好的一种内部排序方法,快速排序算法在,最坏,情况下（待排序列,正序,或,逆序,）,每次划分只得到比上一次少 一个记录的子序列,另一个子序列却为空,即划分得极不均匀,此时需要执行,n-1,次递归调用,且比较的次数是,n(n-1)/2,所以快速排序收到序列初始状态的影响,在,最坏,情况下算法,时间复杂度为,O(n,2,),快速排序算法分析,快速排序算法关键字的比较和交换也是跳跃式进行的,所以快速排序算法也是一种,不稳定,的排序方法。,由于进行了递归调用,需要一定数量的栈,O(log,2,n),作为辅助空间,例如,1,、快速排序算法在,数据元素按关键字有序的,情况下最不利于发挥其长处。,2,、设关键字序列为：,49,38,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,125,0,桶：,1,2,3,4,5,6,7,8,9,（,3,位数可以看成个,3,关键字，再按“,次位优先法,”排序）,0,轮次,1,1,51,2,34,3,6,4,12,5,21,6,2,7,8,72,9,轮次,2,0,1,5,1,2,3,4,3,6,4,1,2,5,2,1,6,2,7,8,7,2,9,轮次,3,0,1,8,5,12,2,16,1,25,27,7,29,3,43,64,输出,:,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,分，,8,题，每题,10,分,),23,已知数据序列为,(86,，,8,，,234,，,50,，,116,，,64,，,68,，,453,，,24,，,142),，给出基数排序过程的示意图。,0,桶：,1,2,3,4,5,6,7,8,9,轮次,2,0,8,1,1,6,1,4,2,6,4,2,4,轮次,3,8,24,50,2,34,1,16,64,86,68,输出,:,8,24,50,64,68,86,116,142,234,453,南航,2013,年,4,（,10,分）已知数据序列为,(76,，,58,，,234,，,5,，,16,，,164,28,，,423,，,24,，,102),，给出基数排序过程的示意图。,5,0,轮次,1,14,2,45,3,23,4,8,6,8,6,4,11,6,6,8,2,4,5,0,4,5,3,2,3,4,8,6,6,8,1,42,4,53,排序方法,平均时间复杂度,最坏情况下时间复杂度,额外空间复杂度,稳定性,简单选择排序,O(N,2,),O(N,2,),O(1),不稳定,直接插入排序,O(N,2,),O(N,2,),O(1),稳定,冒泡排序,O(N,2,),O(N,2,),O(1),稳定,希尔排序,O(N,d,)(1d0,，,O(N,4/3,),）,1,2,3,4,6,9,8,12,18,27,16,24,36,54,81,（,O(N(logN),2,),）,稳定性：不稳定，因为是跳跃式的比较和交换,