1、第第9章章 查找查找基本概念基本概念查找查找 内部查找内部查找外部查找外部查找关键字关键字次关键字次关键字稳定查找稳定查找不稳定查找不稳定查找静态查找表静态查找表动态查找表动态查找表查找成功查找成功查找失败查找失败一一.静态查找表静态查找表 1.1.顺序表的查找顺序表的查找2.2.算法实现，时间复杂度分析（成功、包括失败情算法实现，时间复杂度分析（成功、包括失败情况）况）3.3.2.2.有序表的查找有序表的查找4.4.折半查找的适用条件，算法实现，时间复杂度分折半查找的适用条件，算法实现，时间复杂度分析析5.5.3.3.索引顺序表的查找索引顺序表的查找6.6.分块有序的概念，时间复杂度分析分块
2、有序的概念，时间复杂度分析二二.动态查找表动态查找表 1.1.二叉排序树二叉排序树2.2.算法思想，时间复杂度分析算法思想，时间复杂度分析3.3.二叉排序树的蜕化为单支树二叉排序树的蜕化为单支树4.4.2.2.平衡二叉树（平衡二叉树（AVLAVL树）树）5.5.平衡因子，平衡二叉树的构造过程平衡因子，平衡二叉树的构造过程6.6.3.B_3.B_树树7.7.m m阶阶B_B_树的概念，结点结构，插入删除的算法思想树的概念，结点结构，插入删除的算法思想三三.哈希查找哈希查找 1.1.哈希函数哈希函数2.2.2.2.处理冲突的方法处理冲突的方法3.3.3.3.哈希查找的算法思想哈希查找的算法思想Ex
3、ercise9-1已知一个长度为已知一个长度为 15 的线性表，其关键字序的线性表，其关键字序列为列为 190，381，12，40，410，394，540，760，35，476，800，146，9，445，600按各元素的顺序构造一棵二叉排序树按各元素的顺序构造一棵二叉排序树若各元素的查找概率相等，给出该二叉排序若各元素的查找概率相等，给出该二叉排序树的平均查找长度树的平均查找长度Exercise9-2已知关键字序列为已知关键字序列为 45，24，70，7，30，53，90，3，12，26，37，50，61，85，100试按关键字顺序构造一棵试按关键字顺序构造一棵 平衡二叉树，要平衡二叉树，要
4、求画出每个具体步骤求画出每个具体步骤Exercise9-4设哈希表的地址范围为 017，哈希函数为：H(k)=k MOD 16k 为关键字，用线性探测再散列法处理冲突，输入关键字序列为：10，24，32，17，31，30，46，47，40，63，49画出哈希表的示意图若查找关键字 63，需要依次与哪些关键字比较第第10章章 内部排序内部排序时间复杂度比较时间复杂度比较Insertion O(n2)Bubble O(n2)Quick O(n log n)Most of the time!Heap O(n log n)GuaranteedMerging O(n log n)GuaranteedRa
5、dix O(d(n+rd)平均时间性能而言，快速排序最佳。平均时间性能而言，快速排序最佳。空间复杂度比较空间复杂度比较Insertion O(1)Bubble O(1)Quick O(log n)Heap O(1)Merging O(n)Radix O(rd)稳定性比较稳定性比较Insertion 简单稳定，希尔不稳定简单稳定，希尔不稳定Bubble 稳定稳定Quick 不稳定不稳定 Heap 不稳定不稳定Merging 稳定稳定Radix 稳定稳定1.插入排序：插入排序：直接插入排序法应掌握算法直接插入排序法应掌握算法(包括算法的实现包括算法的实现)希尔排序的算法思想，要能写出每趟排序的结果
6、。希尔排序的算法思想，要能写出每趟排序的结果。希尔排序中增量序列定义的要求希尔排序中增量序列定义的要求希尔排序是不稳定的希尔排序是不稳定的(希尔：排得希尔：排得希里糊涂尔希里糊涂尔：)2.交换排序交换排序交换排序的基本思想交换排序的基本思想(两两比较反即换两两比较反即换)。包括冒泡排序和快速排序。包括冒泡排序和快速排序。冒泡排序的算法应掌握。冒泡排序是稳定的。冒泡排序的算法应掌握。冒泡排序是稳定的。快速排序法应掌握算法思想快速排序法应掌握算法思想(分治分治)，针对给定的实例，针对给定的实例，写出快速排序的排序过程。，写出快速排序的排序过程。快速排序的平均时间复杂度为快速排序的平均时间复杂度为O
7、(nlgn)。它是不稳定的它是不稳定的(一一快快就就不稳不稳)3.选择排序选择排序基本思想就是基本思想就是“每趟选一排在后每趟选一排在后”。直接选择排序的算法思想和实现，能写出其各趟排直接选择排序的算法思想和实现，能写出其各趟排序的过程。序的过程。直接选择排序是不稳定的直接选择排序是不稳定的(直接直接“选举选举”也是也是“不稳不稳定定”的，所以我们要进行间接选举的，所以我们要进行间接选举)堆排序。堆的定义堆排序。堆的定义(大根堆就是双亲比孩子大，小根大根堆就是双亲比孩子大，小根堆就是双亲比孩子小堆就是双亲比孩子小)。请判断一个序列是不是堆。请判断一个序列是不是堆(大顶堆或小顶堆大顶堆或小顶堆)
8、。建堆和堆排序的图示过程。堆排序是不稳定的建堆和堆排序的图示过程。堆排序是不稳定的(你想你想，一堆鸡蛋能，一堆鸡蛋能稳定稳定吗吗)4.归并排序归并排序算法思想和归并排序过程的表示算法思想和归并排序过程的表示顺序表和链表上一趟归并排序的实现顺序表和链表上一趟归并排序的实现0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7链链式存储指针式存储指针如何变化？如何变化？5.5.基数排序基数排序将将最低位优先法最低位优先法用于用于单关键字单关键字的情况。的情况。基数排序的分配和收集方法基数排序的分配和收集方法(图示图示)。基数排序中，是稳定的。基数排序中，是稳定的
9、。排序算法的选择策略排序算法的选择策略各种内部排序方法的比较和选择比如在几种排序各种内部排序方法的比较和选择比如在几种排序法中选择稳定的排序法、选择速度快的排序法、法中选择稳定的排序法、选择速度快的排序法、选择稳定且速度快的排序法，对于给定的关键字选择稳定且速度快的排序法，对于给定的关键字序列，选择最好的排序法等。序列，选择最好的排序法等。Exercise10-1若待排序的关键字序列为若待排序的关键字序列为25，73，12，80，116，251.请按如下两种增量值分别给出希尔排序的过程示意图请按如下两种增量值分别给出希尔排序的过程示意图3，2，15，2，12.给出快速排序的过程示意图给出快速排序的过程示意图3.给出堆排序的过程示意图给出堆排序的过程示意图4.给出给出2路归并排序的过程示意图路归并排序的过程示意图5.给出基数排序的过程示意图给出基数排序的过程示意图
