内容发布更新时间 : 2024/5/16 3:35:42星期一 下面是文章的全部内容请认真阅读。

学而不思则惘，思而不学则殆

LL型调整、RR型调整、LR型调整、RL型调整

LL型调整:单向右旋平衡。 RR型调整:单向左旋平衡。

LR型平衡:先左旋转后向右旋转平衡。 RL型平衡:先右旋转后左旋转平衡。

问题9.10 什么是哈希表？其查找思想是什么？有什么优点？ 哈希表又称散列表，是一种存储线性表的存储结构。

查找思想：设要存储的对象个数为n,设置一个长度为m(m≥n)的连续内存单元， 以线性表中每个对象的关键字ki为自变量，通过一个称为哈希函数的函数h(ki),把k 映射为内存单元的地址h(ki),并把该对象存储在这个内存单元中。 优点：计算过程简单，高的时间效率

第10章 内排序

问题10.1 什么是排序？怎么理解排序的稳定性 排序就是整理表中的元素，使之按关键字递增或递减的顺序排列；如果待排序的表 中，存在多个关键字相同的元素，经过排序后这些具有相同关键字的元素之间的相对次 序保持不变，则称这种排序方法是稳定的，反之，则称这种排序方法是不稳定的。

问题10.2 什么是内排序和外排序？

各种排序方法可以按照不同的原则加以分类。在排序的过程中，若整个表都是放 在内存中处理，排序时不涉及内外存数据的交换，则称为内排序；反之，成为外排序。

问题10.3 插入排序、交换排序、选择排序的概念是什么？ 插入排序:每次将一个待排序的元素，按其关键字大小插入到已经排好序的子表中 的适当位置，直到全部元素插入完成为止。

交换排序：两两比较待排序元素的关键字，发现两个元素的次序相反时即进行交 换，直到没有反排序的元素为主。

选择排序：每一趟从待排序的元素中选出关键字最小的元素，顺序放在一排序好 的子表的最后，直到全部元素排序完毕。

问题10.4解释直接插入排序、折半插入排序、希尔排序的思路和效率分析。 直接插入排序: 假设待排序的元素存放在数组R[0..n-1]中，排序过程中的某一时刻,R 被划分成个子区间R[0..i-1]和R[i..n-1]，其中，前一个子区间是已经排序排序好的有序区， 后一个子区间则是当前未排序的部分，称其为无序区。直接插入排序的一趟操作是将当 前无序区的开头元素R[i]插入到有序区R[0..i-1]中的适当位置上，使R[0..i]变为新的有序 区。

折半插入排序：直接插入排序将无序区中开头元素R[i]插入到有序区R[0..i-1]中，此

时可以采用折半查找方法先在R[0..i-1]中找到插入位置再通过移动元素进行插入。

希尔排序：希尔排序实际上是一种分组插入方法。其基本思路为：先定义一个小于 n的整数d1作为第一个增量，把表的全部元素分成d1个组，所有相互之间距离为d1的 倍数的元素放在一个组中，在各组中进行直接插入排序；然后取第二个增量d2(

学而不思则惘，思而不学则殆

复上述的分组和排序过程，直至所取的增量dt(dt

问题10.5 深入分析冒泡排序、快速排序的思想和差异。

冒泡排序：通过无序区中相邻元素间关键字的比较和位置的交换，使关键字最小 的元素如气泡一般往上漂浮直至水面。整个算法是从最下面的元素开始，对每两个相 邻的关键字进行比较对每两个相邻的关键字进行比较，且使关键字较小的元素换至关 键字较大的元素之上，使得经过一趟冒泡排序后，关键字最小的元素到达最上端，接 着，再在剩下的元素中，找关键字次小的元素，并把它换到第二个位置上。以此类推， 一直到所有元素都有序为止。

快速排序：是在待排序的n个元素中选取一个元素(通常取第一个元素)作为基准，

把该元素放入适当位置后，数据序列被此元素划分成两部分，所有关键字比该元素关 键字小的元素放置在前一部分，所有关键字比它大的元素放置在后一部分，并把该元 素排在这两部分的中间(称该元素归为)，这个过程称作一趟快速排序，之后对所有划 分出来的两部分分别重复上述过程，将表一分为二，对此表按递归方式继续这种划分 直至划分的子表长为1和0。 冒泡排序是一种稳定的排序方法。快速排序是一种不稳 定的排序方法。

问题10.6 深入分析直接选择排序、堆排序、归并排序、基数排序的思路和优缺点。

直接选择排序:第i趟排序开始时,当前有序区和无序区分别为R[0..i-1]和R[i..n-1], 该趟排序是从当前无序区中选出关键字最小的元素儿R[k],将它与无序区的第一个元 素R[i]交换,是R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。

堆排序:堆排序是一种树形选择排序方法，它的特点是，在排序过程中，将

R[1..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中，双亲节点和孩子节点之间的内在关系,在当前无序区中选择关键字最大(或最小)的元素。 归并排序：是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表即二路归并。将R[0..n-1]看成是n个长度为1的有序序列,然后进行两两归并,得到二分之n个长度为二的有序序列,(最后一个有序序列的长度可能为1)，在进行两两归并，得到四分之n个长度为四的有序序列，最后一个有序序列的长度可能小于四，……，直到得到一个长度为n的有序序列。

基数排序：是基数排序有两种:最低位优先LSD和最高为优先MSD。最低为优先的过程是:先按最低位的值对元素进行排序,在此基础上，再按次低位进行排序,以此类推,由低位向高位,每趟都是根据关键字的一位并在前一趟的基础上，对所有元素进行排序，直至最高位。 优缺点:直接选择排序使从大量的元素中选择一部分排序元素变简单。但直接选择排序算法是一个不稳定的排序方法。堆排序可以使元素数较多的表比较方便处理。但堆排序是一种不稳定的排序方法。基数排序不需要进行关键字间的比较而且它是一种稳定的排序方法。 和优缺点。