数据结构查找与排序

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

2、、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表的创建与平均查找长度的计算 时间复杂度的分析（不依赖问

3、题的规模,与解决冲突的方法以及hash表的装填因子有关）例如例如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查找时比较次数

4、15612274查找成功的平均查找长度=（1+5+6+1+2+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冲突次数10

5、30100000查找时比较次数2141211111查找成功时的平均搜索长度：（2 + 1 + 4 + 1+ 2 + 1 + 1 + 1 + 1 + 1）/10=1.5第二部分 排序 各种排序算法的特性 时间性能（最好、最坏、平均情况） 空间复杂度 稳定性 常见排序算法 堆排序堆排序-堆的定义堆的定义,创建堆创建堆,堆排序（厦大堆排序（厦大3次次,南航南航2次次,南大南大3次）次） 快速排序快速排序 基数排序基数排序 插入排序插入排序 希尔排序希尔排序 冒泡排序冒泡排序 简单选择排序简单选择排序 归并排序归并排序一、基于选择的排序1.简单选择排序简单选择排序2.堆排序（堆排序（heap sort

6、）算法关键部分：算法关键部分： for (i=1; i n; i+) min = i ; for (j=i+1; j=n; j+) if (aj314431353135 “筛选筛选”：除了堆顶元素之外：除了堆顶元素之外,其余元素都满足堆的性质其余元素都满足堆的性质,把这样一个数据集合把这样一个数据集合做成一个堆做成一个堆,这个过程叫做这个过程叫做“筛选筛选” 。 筛选：实际上是一个寻找的过程筛选：实际上是一个寻找的过程,由于堆顶元素是唯一一个不满足堆性质的元由于堆顶元素是唯一一个不满足堆性质的元素素,则下面需要在下面的各个位置中则下面需要在下面的各个位置中,寻找它该处于的位置寻找它该处于的位置

7、 首先比较该堆顶元素与其两个孩子的大小首先比较该堆顶元素与其两个孩子的大小,取两个孩子中较大的一个取两个孩子中较大的一个,若若比该元比该元素大素大,则把这个孩子提升一个层次则把这个孩子提升一个层次,再继续比较原堆顶元素与这个孩子原来的再继续比较原堆顶元素与这个孩子原来的孩子孩子,直到发现某个层次上直到发现某个层次上,原来元素的两个孩子均不大于（小于或等于）原原来元素的两个孩子均不大于（小于或等于）原堆顶元素堆顶元素,或者到了某个叶子结点位置上为止。或者到了某个叶子结点位置上为止。 问题问题1：筛选筛选 问题问题2：堆的创建堆的创建 依靠依靠“筛选筛选”的过程的过程 “创建堆创建堆”是指如何将是

8、指如何将已经存在的已经存在的n个元素个元素按堆（最大堆或最小堆）按堆（最大堆或最小堆）的要求存放在一个一维数组中。的要求存放在一个一维数组中。 在在线性时间复杂度线性时间复杂度下创建堆。具体分两步进行：下创建堆。具体分两步进行：第一步第一步,将将n个元素按输入顺序存入二叉树中个元素按输入顺序存入二叉树中,这一步只要求满这一步只要求满足足完全二叉树的结构特性完全二叉树的结构特性,而不管其有序性。而不管其有序性。第二步第二步,按照完全二叉树的层次遍历的反序按照完全二叉树的层次遍历的反序,找到第一个非叶子结点找到第一个非叶子结点,从该结点开始从该结点开始“筛选筛选”,调整各结点元素调整各结点元素,然

9、后按照反序然后按照反序,依次做筛选依次做筛选,直到直到做完根结点元素做完根结点元素,此时即构成一个堆。此时即构成一个堆。 时间复杂性时间复杂性 t(n) = o（nlogn）,与数据初始状态无关与数据初始状态无关,堆排序的最佳、堆排序的最佳、最差以及平均时间复杂度均为最差以及平均时间复杂度均为o(nlog2n) 空空 间复杂性间复杂性s(n) = o（1） 稳定性：稳定性：不稳定。不稳定。因为是跳跃式的比较与交换。因为是跳跃式的比较与交换。反例如下：反例如下：不稳定！不稳定！排序前排序前2 领先于领先于 22 落后于落后于 2排序后排序后 堆排序特性（属于堆排序特性（属于选择排序选择排序大类）

10、大类） 2 1 2 1 2 2 211223211223121223 适用场合：数据量比较大的情况适用场合：数据量比较大的情况,因为初始构建堆所需比较次数较多。因为初始构建堆所需比较次数较多。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, 3

11、0, 15, 25, 20, 10 d75, 45, 65, 10, 25, 30, 20, 153、对关键码序列45,30,55,21,94,66,90,82用堆排序方法进行逆序排序,请画出建立的初始堆以及调整3个关键码的示意图。三、基于交换的排序三、基于交换的排序1.冒泡排序冒泡排序（bubble sort）2.快速排序（快速排序（quick sort） 1.冒泡排序（冒泡排序（bubble sort）算法思想）算法思想依次比较相邻的两个记录的关键字依次比较相邻的两个记录的关键字,若两个记录是反序的若两个记录是反序的(即前一个记录的关即前一个记录的关键字键字大于大于后前一个记录的关键字后前

12、一个记录的关键字),则进行交换则进行交换,直到没有反序的记录为止。直到没有反序的记录为止。冒泡排序时间复杂度冒泡排序时间复杂度 最好情况最好情况(正序正序)：比较次数：比较次数：n-1；移动次数：；移动次数：0； 最坏情况最坏情况(逆序逆序)：冒泡排序算法分析冒泡排序算法分析比较次数比较次数：(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放在放

14、在rj的位置的位置:29 23 22 45 38 67 31ijj前移前移2个位置后个位置后,rj放在放在ri的位置的位置:29 23 22 29 45 38 67 31i ji后移后移1个位置后个位置后,i和和j的位置重合的位置重合:设有设有6个待排序的记录个待排序的记录,关键字分别为关键字分别为29, 38, 22, 45, 23, 67,一趟快速排序一趟快速排序的过程如的过程如图图所示：所示：快速排序的平均性能为快速排序的平均性能为o(nlog2n),在同数量级算法中综合考虑在同数量级算法中综合考虑,是最是最好的一种内部排序方法好的一种内部排序方法快速排序算法在快速排序算法在最坏最坏情况

15、下（待排序列情况下（待排序列正序正序或或逆序逆序）,每次划分只得每次划分只得到比上一次少到比上一次少 一个记录的子序列一个记录的子序列,另一个子序列却为空另一个子序列却为空,即划分得极不即划分得极不均匀均匀,此时需要执行此时需要执行n-1次递归调用次递归调用,且比较的次数是且比较的次数是n(n-1)/2, 所以快所以快速排序收到序列初始状态的影响速排序收到序列初始状态的影响,在在最坏最坏情况下算法情况下算法时间复杂度为时间复杂度为o(n2)快速排序算法分析快速排序算法分析快速排序算法关键字的比较和交换也是跳跃式进行的快速排序算法关键字的比较和交换也是跳跃式进行的,所以快速排序所以快速排序算法也

16、是一种算法也是一种不稳定不稳定的排序方法。的排序方法。由于进行了递归调用由于进行了递归调用,需要一定数量的栈需要一定数量的栈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 个整数，范围介于个整数，范围

17、介于 0 到到 999 ( m = 1000 ) 之间。是否之间。是否可以在可以在线性的时间线性的时间内把它们排序内把它们排序 ? 单关键字的单关键字的基数排序基数排序输入输入: 64, 8, 216, 512, 27, 729, 0, 1, 343, 1250桶：桶：123456789（3位数可以看成个位数可以看成个3关键字，关键字，再按再按“次位优先法次位优先法”排序）排序）0轮次轮次 1151234364125216278729轮次轮次 20151234364125216278729轮次轮次 30185122161252772934364输出输出: 0, 1, 8, 27, 64, 12

18、5, 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桶：桶：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轮次轮次 114245323486864116682450453234