数据结构查找与排序.ppt

第一部分 查找,二分查找,Hash表,二分查找考点 条件：顺序存储,按关键字有序 时间复杂度分析（log2n） 最多要比较的次数（2n +1 ）,理由：n个结点的判定树的深度与n个结点的完全二叉树深度相同。 折半查找的二叉判定树,1、请问,满足什么条件的顺序表可以实施二分查找,在满足该条件的n个记录的顺序表中进行二分查找,最大的比较次数是多少？,答：数据元素初始状态按关键字有序 最大比较次数应为2n +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(log2N) B、O(N) C、不直接依赖于N D、上述三者都不是,答案：C,2、已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（key）=keyMOD11,哈希表HT的长度为11,采用二次探测再散列法（d=12,-12,22,-22,32,）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找长度。,查找成功的平均查找长度=（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,查找成功时的平均搜索长度：（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 Amin) ) min=j; /min是待排序列中关键字最小的记录所在位置 if (min!=i) 交换Ai与Amin； ,1. 简单选择排序算法思想：,每一趟从当前待排序的记录中选择关键字最大（小）的记录,然后与末尾（首）记录进行交换, 稳定性：不稳定。反例如下：,2 2 1,1 2 2,不稳定！,简单选择排序算法性能 整个算法是二重循环：外循环控制排序的趟数,对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。 进行第i趟排序时,关键字的比较次数为n-i,则：,与数据的初始状态无关, 时间复杂度是：T(n)=O(n2) 空间复杂度是：S(n)=O(1), 堆排序的算法思想：,Step1：（初始建堆）把待排序元素保存在数组的1至n位置上, 把 这个元素集合（不包括位置0）做成一个最大堆 Step2：交换堆顶元素与当前集合的最后一个元素,然后把堆的范围看做1至n-1（即这时候堆的最后一个元素为n-1,而非n）进行“筛选”,再构造成一个最大堆 Step3：重复Step2,直至堆的大小为1,排序完成,堆是一棵完全二叉树,它的每一个结点满足： 若其有孩子,则该结点的值大于（或小于）孩子的值。 若每一个结点大于孩子结点,则称为最大堆（大顶堆）,反之称为最小堆（小顶堆）。, 堆(Heap), 取出根结点（最大值）元素,与最后一个位置的元素交换。,为了保持完全二叉树的结构特性, 移去的是该结点。, 把 31 移至根,31, 找出31的较大的孩子,31,44,31,35, “筛选”：除了堆顶元素之外,其余元素都满足堆的性质,把这样一个数据集合做成一个堆,这个过程叫做“筛选” 。, 筛选：实际上是一个寻找的过程,由于堆顶元素是唯一一个不满足堆性质的元素,则下面需要在下面的各个位置中,寻找它该处于的位置, 首先比较该堆顶元素与其两个孩子的大小,取两个孩子中较大的一个,若比该元素大,则把这个孩子提升一个层次,再继续比较原堆顶元素与这个孩子原来的孩子,直到发现某个层次上,原来元素的两个孩子均不大于（小于或等于）原堆顶元素,或者到了某个叶子结点位置上为止。, 问题1：筛选, 问题2：堆的创建,“创建堆”是指如何将已经存在的N个元素按堆（最大堆或最小堆）的要求存放在一个一维数组中。, 在线性时间复杂度下创建堆。具体分两步进行： 第一步,将N个元素按输入顺序存入二叉树中,这一步只要求满足完全二叉树的结构特性,而不管其有序性。,第二步,按照完全二叉树的层次遍历的反序,找到第一个非叶子结点,从该结点开始“筛选”,调整各结点元素,然后按照反序,依次做筛选,直到做完根结点元素,此时即构成一个堆。, 时间复杂性 T(n) = O（nlogn）,与数据初始状态无关,堆排序的最佳、最差以及平均时间复杂度均为O(nlog2n), 空 间复杂性S(n) = O（1）, 稳定性：不稳定。因为是跳跃式的比较与交换。反例如下：,不稳定！, 堆排序特性（属于选择排序大类）,2 1 2,1 2 2, 适用场合：数据量比较大的情况,因为初始构建堆所需比较次数较多。,设关键字序列为：49, 38, 66, 90, 75, 10, 20。请把这些关键字调整成堆顶元素取最小值的堆。（画出过程）,例如：,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, 15,3、对关键码序列45,30,55,21,94,66,90,82用堆排序方法进行逆序排序,请画出建立的初始堆以及调整3个关键码的示意图。,三、基于交换的排序,冒泡排序（Bubble Sort） 快速排序（Quick Sort）,1.冒泡排序（Bubble Sort）算法思想,依次比较相邻的两个记录的关键字,若两个记录是反序的(即前一个记录的关键字大于后前一个记录的关键字),则进行交换,直到没有反序的记录为止。,冒泡排序时间复杂度 最好情况(正序)：比较次数：n-1；移动次数：0； 最坏情况(逆序)：,冒泡排序算法分析,时间复杂度：T(n)=O(n) 空间复杂度：S(n)=O(1) 稳定性：稳定（相邻元素的比较与交换）,2.快速排序算法思想：,是一种递归算法,每次根据某个值,将待排序列分成两部分,一部分序列的元素关键字比该值小,另一部分序列的元素关键字比该值大（或等于）,然后再分别对这两部分进行如上操作,直至排序完成。,设有6个待排序的记录,关键字分别为29, 38, 22, 45, 23, 67,一趟快速排序的过程如图所示：,快速排序的平均性能为O(nlog2n),在同数量级算法中综合考虑,是最好的一种内部排序方法 快速排序算法在最坏情况下（待排序列正序或逆序）,每次划分只得到比上一次少 一个记录的子序列,另一个子序列却为空,即划分得极不均匀,此时需要执行n-1次递归调用,且比较的次数是n(n-1)/2, 所以快速排序收到序列初始状态的影响,在最坏情况下算法时间复杂度为O(n2),快速排序算法分析,快速排序算法关键字的比较和交换也是跳跃式进行的,所以快速排序算法也是一种不稳定的排序方法。 由于进行了递归调用,需要一定数量的栈O(log2n)作为辅助空间,例如,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,（3位数可以看成个3关键字，再按“次位优先法”排序）,0,1,512,343,64,125,216,27,8,729,0,1,8,512,216,125,27,729,343,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)，给出基数排序过程的示意图。,08,116,142,64,24,8,24,50,234,116,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) ，给出基数排序过程的示意图。,50,453,234,86,68,142,453,基于关键字比较,基于关键字与地址的映射,初始序列基本有序时,效率高,初始序列基本有序时,效率高,尽管最坏情况不好,但 实际的平均时间效率上,快速排序是最佳的排序方法,1、在堆排序、快速排序和归并排序中： 1）若只从存储空间考虑,则应首先选取哪种排序方法,其次选取哪种排序方法,最后选取哪种排序方法？ 答：首选堆排序（O(1) ）,其次选快速排序(O(log2n),最后选归并排序(O(n)。 2）若只从排序结果的稳定性考虑,则应选取哪种排序方法？ 答：归并排序 3）若只从平均情况下排序最快考虑,则应选取哪种排序方法？ 答：快速排序 4）若只从最坏情况下排序最快并且要节省内存考虑,则应选取哪种排序方法？ 答：堆排序 5）设关键字序列为：49, 38, 66, 90, 75, 10, 20。请把这些关键字调整成堆顶元素取最小值的堆。（画出过程）,例如,2、下列内部排序算法中,其比较次数与序列初态无关的算法是（ B ） A、直接插入排序 B、简单选择排序 C、起泡排序 D、堆排序,3、我们打算对n个数进行排序,由于n非常大,希望满足最坏的情况下排序时间为 O（nlogn）的前提下,辅助空间越小越好,则选择的排序方法是（ ） A、快速排序 B、 堆排序 C、 冒泡排序 D、归并排序,6稳定的排序方法是( )。 A直接插入排序 B直接选择排序 C堆排序 D快速排序 7归并排序算法的时间复杂度是( )。 A. O(log2n) B. O(n) C. O(n2) D. O(nlog2n),答案：B,答案：D,答案：B,答案：A,答案：D,4下列排序算法中,平均时问复杂度不是0(nlog2n)的是( )。 A快速排序 B堆排序 C归并排序 D希尔排序 5下列排序算法中,其中( )是稳定的。 A快速排序 B起泡排序 C堆排序 D希尔排序,答案：D,8、对由n个元素组成的一个无序数组,不必完成全部元素的排序,即可找出最大（或最小）的元素,这是 排序方法。,答案：直接选择排序、起泡排序,9、n个记录的直接插入排序中，键值的最小比较次数是（ B ） A、(n+2)(n-1)/2 B、n-1 C、2(n-1) D、n2/2 10、若用冒泡排序方法对序列（10,14,26,29,41,52）从大到小排序，需进行（ C ）次比较。 A、 3 B、5 C、15 D、25,直接插入排序 在一个已有序的序列中，将待排序的元素关键字逐个与该有序序列中的元素的相应关键字作比较，确定该元素在序列中的正确位置，然后在该位置插入这个元素，形成一个新的有序序列。,算法分析,最坏情况（逆序）下：第i趟排序时，关键字比较次数i次，记录移动次数i+1，对含有n个元素的数据集，需要做n趟排序 最好情况（正序）下：第i趟，关键字比较1次，记录移动0次。 直接插入排序的平均时间复杂度为O(n2),