第7章 排序算法
1. 请简述排序的作用。
排序的作用是将一个待排序元素集合按关键字递增（或递减）顺序整理为一个有序序列。 2. 请简述稳定排序和不稳定排序的含义。
若采用某种排序算法对任一组元素进行排序，在排序前后，那些具有相同关键字值的元素之间的相对次序都保持不变，则将这种排序算法称为是稳定的，否则称为是不稳定的。 3. 请简述各种排序算法的适用范围。
排序算法的适用范围如下：
（a）直接插入排序、简单选择排序和冒泡排序都是简单排序算法，它们的时间复杂度和空间复杂度分别为O(n2)和O(1)。若待排序元素数量n较小，可以选用直接插入排序和冒泡排序。另外，当待排序元素基本有序时，也应选用直接插入排序和冒泡排序，此时时间复杂度都能达到O(n)。若元素本身数据量较大，元素移动操作代价较高，则应选用平均移动元素次数最少的简单选择排序。希尔排序是对直接插入排序算法的改进，大大降低了时间复杂度，但它是一种不稳定的排序算法。
（b）堆排序、快速排序和归并排序主要适用于待排序元素数量n较大的情况，当待排序元素数量n较小时，它们的性能有可能劣于简单排序算法。因此，在实际应用时，快速排序算法和归并排序算法经常与简单排序算法结合使用（例如，可以先用快速排序算法将集合划分为规模更小的子集合，对于元素数量较小的子集合，则用直接插入排序算法进行排序）。在所有平均时间复杂度为O(nlog2n)的算法中，尽管快速排序在最坏情况下时间复杂度较高，但它通常被认为是平均性能最好的一种算法，并且通过优化可以降低最坏情况出现的概率。归并排序是一种稳定的排序算法，其时间性能一般要优于堆排序，但它所需要的辅助空间较多，当应用环境要求排序前后具有相同值的元素相对次序不能改变时可以考虑使用。堆排序所需的辅助空间最少，当可用空间非常有限时可以考虑使用。
（c）箱排序和基数排序的时间复杂度最低，但它们的空间复杂度最高。箱排序主要适用于待排序元素长度（即d值）较小的情况，在实际中应用不多；基数排序是箱排序的改进，主要适用于整数或字符串的排序，或者与其他排序算法结合进行实数的排序（例如，可以先用基数排序算法按整数部分将元素分成若干个子集合，再对每个子集合应用直接插入排序算法进行排序）。
5. 请简述插入排序、选择排序、交换排序、归并排序和分配排序的原理。
插入排序：按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至所有元素都插入完毕。
选择排序：每次从待排序的元素中选择具有最小（或最大）关键字的元素放到已排序序列的尾部（或头部），直至所有元素都排序完毕。
交换排序：从待排序的元素中选择两个次序相反的元素进行交换，直至任意两个元素的次序都正确。
K路归并排序：每次将K（K≥2）个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含所有待排序元素的有序序列。
分配排序：根据元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。
5. 请简述直接插入排序的具体步骤。
直接插入排序是一种简单排序算法，其具体步骤为：
（a）初始已排序区为空，将第一个待排序的元素插入到已排序区中。
（b）将后继每一个待排序的元素依次取出，并按照关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。
（c）重复上一步骤直至将待排序的元素都插入到已排序序列中。 6. 请简述希尔排序的具体步骤。
希尔排序，又称为“缩小增量排序”，其具体步骤为：
（a）令n为待排序元素数目，设置增量序列{d0, d1, …, dk}，其中n>d0>d1>…>dk=1。 （b）按增量di（i依次取值为0, 1, …, k）将待排序元素分为di组，将所有下标距离为di的倍数的元素放在同一组中，即R[1], R[1+ di], R[1+2*di], …在第一组中，R[2], R[2+ di], R[2+2*di], ??在第二组中，??，依此类推。然后分别在各组内进行直接插入排序。
（c）重复上一步骤直至最后以1为增量对所有待排序元素进行直接插入排序。 7. 请简述简单选择排序的具体步骤。
简单选择排序是一种简单排序算法，其具体步骤为：
（a）初始已排序区为空，待排序区包含所有待排序元素。
（b）从待排序区中选择具有最小关键字的元素，将其与待排序区的第一个元素交换位置，并将该位置加到已排序区中。
（c）重复上一步骤直至所有元素都排序完毕。 8. 请简述堆的定义和堆的构建过程。
堆的定义：
对于包含n个元素的集合R={R[1], R[2], …, R[n]}，若满足：
（1）R[i]≤R[2*i]且R[i]≤R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不大于其孩子结点的值）。
（2）或R[i]≥R[2*i]且R[i] ≥R[2*i+1]（即R所表示的完全二叉树中每一棵子树的根结点的值均不小于其孩子结点的值）。
则称集合R为堆。若满足前一个条件则称R为小根堆，满足后一个条件则称R为大根堆。
堆的构建过程：
堆一般采用自底向上的构建方法，即在将以某一结点为根结点的二叉树构建成堆之前，先将其左子树和右子树构建成堆。以叶子结点为根的子树必然是堆，因此，对于由n个元素构成的完全二叉树，其对应的堆的构建过程从R[?n/2?]作为根结点的子树开始，依次对R[?n/2?-1]、R[?n/2?-2]、…、R[1]作为根结点的树进行堆的构建。
在将一棵R[i]作为根结点的子树整理为堆时，只有根结点不满足堆的条件，因此，需将根结点与后继层中的结点依次比较并不断将根结点下移直至该子树满足堆的条件，这里以大根堆构建为例介绍其具体过程：
（a）若R[i]存在左孩子R[2*i]，则令j=2*i；若R[i]存在右孩子R[2*i+1]且R[2*i+1]>R[2*i]，则令j=2*i+1。将R[j]与R[i]比较，若R[i]较小，则将R[i]和R[j]交换，并令i=j。
（b）重复上述步骤直至R[i]无孩子结点或R[i]比其孩子结点都大，此时该子树即为堆。 9. 请简述堆排序的具体步骤。
堆排序的具体过程： （a）采用自底向上的方法将包含n个元素的待排序集合R={R[1], R[2], …, R[n]}整理为大根堆，其元素数目i=n，初始时已排序集合R'为空集；
（b）将R[1]与R[i]交换，并将i算作已排序集合中的元素位置，更新待排序集合中最后一个元素的位置i=i-1，此时待排序集合R={R[1], R[2], …, R[i]}，已排序集合R'={R[i+1],
R[i+2], …, R[n]}。显然，待排序集合R={R[1], R[2], …, R[i]}中只有根结点R[1]不满足大根堆的条件，通过下移R[1]重新将R整理为大根堆；
（c）重复上一步骤直至待排序集合R={R[1]}，此时直接将R[1]作为已排序集合R'中的元素，堆排序过程结束。
10. 请简述冒泡排序的具体步骤。
冒泡排序是一种简单排序算法，其具体步骤为：
（a）初始已排序区为空，待排序区包含所有待排序元素。
（b）在一轮排序中，对待排序区所有相邻元素从前至后进行两两比较，若相邻两个元素次序相反（即前一个元素的关键字值大于后一个元素的关键字值），则交换它们的位置。每轮排序后，待排序区中的最大元素会移到待排序区的尾部，将待排序区的最后一个元素放到已排序区的头部。
（c）重复上一步骤直至待排序区中只剩下一个元素或者在一轮排序中没有出现相邻元素交换的情况，此时直接将待排序区中的所有元素按原次序放到已排序区的头部，冒泡排序结束。
11. 请简述快速排序中划分的含义和过程。
划分的含义：
划分是以指定元素x为基准将一个集合R分为两个子集R1和R2，其中R1中的元素都小于或等于x，R2中的元素都大于或等于x。
划分的过程： 对于包含(high-low+1)个元素的待排序集合R={R[low], R[low+1], …, R[high]}，以R[k]（low ≤k ≤high）为基准对其进行划分的具体过程为：
（a）令i、j分别指向集合R的第一个元素和最后一个元素（即i=low、j=high），并将R[k]与R[i]交换（即初始基准元素在i所指向的位置，此时基准元素前面没有任何元素，下面对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）。
（b）若j!=i且R[j]≥R[i]，则令j=j-1，重复直至R[j] （c）若i!=j且R[i]≤R[j]，则令i=i+1，重复直至R[i]>R[j]或i==j。上述处理后，若i!=j（即通过R[i]>R[j]这个条件退出循环）则将R[i]与R[j]交换、j=j-1，并回到上一步（该步处理结束后，基准元素在i所指向的位置，此时基准元素前面的元素都小于或等于基准元素，而位置j后面的元素都大于或等于基准元素，下面继续对基准元素后面、位置在i+1到j之间的元素按照从后至前的顺序逐一检查其是否大于或等于基准元素）；否则集合划分操作结束。 12. 请简述快速排序的具体步骤。 快速排序就是对集合不断划分的过程：通过划分可以将一个集合分为两个子集合，若子集合中元素数目大于1则再对子集合分别进行划分，重复该过程直至最终每个子集合中元素数目都小于或等于1时快速排序结束。 13. 请简述二路归并排序的具体步骤。 二路归并排序的具体步骤为： （a）对于包含n个元素的待排序集合，将其分为n个长度为1的子序列。 （b）将每两个相邻的子序列进行归并，得到?n/2?个长度为2的子序列和0或1个长 度为1的子序列。 （c）在此基础上，再对每两个相邻的子序列进行归并，得到?n/4?个长度为4的子序列和0或1个长度小于4的子序列。 （d）重复该过程直至得到一个长度为n的有序序列为止。 14. 请简述箱排序的具体步骤。 箱排序的具体步骤为： （1）假设待排序元素的取值范围为m~m+n-1，则箱子数量为n，设置包含n个元素的队列集合B={B[0], B[1], …, B[n-1]}代表n个箱子。 （2）依次取出每一个待排序元素，若其值为m+i（i=0, 1, …, n-1），则通过入队操作将其放在箱子B[i]中。 （3）从B[0]开始，依次检查集合B中每一个队列所代表的箱子，若箱子不为空，则通过出队操作将箱子中的元素逐个取出并依次加到已排序集合中。 15. 请简述基数排序的具体步骤。 基数排序是对箱排序的改进和推广，它先将待排序元素按规则分解得到多个分量、再根据每一个分量对元素进行多次箱排序。 （a）对于数字排序问题，基数排序方法先将每一个数字写成以r为基数的按权展开式形式：N= an-1*r+…+a0*r+a-1*r+…+a-m*r；再按照从低位到高位（即从r开始到r）的顺序进行n+m次箱排序。 （b）对于字符串排序问题，基数排序方法按照从后至前的顺序对字符串中的每个字符分别进行箱排序。若待排序字符串中最长的字符串长度为n，则需进行n次箱排序；若某一字符串长度为m（0≤m≤n），则该字符串在前(n-m)次箱排序中对应的字符值为'\\0'。 n-1 0 -1 -m -m n-1 第8章 查找算法 1. 请简述查找的作用。 查找的作用是根据给定值从一个数据集合中搜索某个元素。若某个元素的关键字值与给定值相等，则查找成功；否则查找失败。 2. 请简述静态查找和动态查找的含义。 静态查找只根据给定值在数据集合中按关键字查找匹配元素、访问匹配元素的属性，而不对数据集合进行插入元素、删除元素等操作；而动态查找可能会在查找过程中向数据集合中插入一个新元素或从数据集合中删除一个已有元素。 3. 请简述各种查找算法的适用范围。 各种查找算法的适用范围： （a）顺序查找虽然查找效率最低，但其对待查找数据集合的存储结构无特别要求，在对数据集合进行增、删、改等操作时效率较高，因此，根据那些不需要经常作查找操作的关键字进行查找时，一般采用顺序查找算法。若经常作查找操作，则应使用效率较高的其他查找算法。 （b）折半查找和分块查找主要适用于数据集合增、删、改等操作较少的情况；二叉排序树查找则适用于数据集合变化较频繁的情况。 （c）哈希查找虽然在理论上具有最短的平均查找长度，但它占用的存储空间较多，且在实际中只有哈希函数构造得好才能达到常量级的平均查找长度。而要想构造出好的哈希函数，必须以大量数据为基础，因此，哈希查找主要适用于数据分布已知的情况。 4. 请简述顺序查找对待查找数据集合的要求及顺序查找的具体步骤。 顺序查找是一种最简单、直观的查找算法，适用于采用任何存储结构的数据集合，其具体步骤为： （a）按预先规定的顺序依次将数据集合中每个元素的关键字与给定值进行比较，若某个元素的关键字与给定值相同，则查找成功； （b）若遍历所有元素后，仍没有找到关键字与给定值相同的元素，则查找失败。 5. 请简述折半查找对待查找数据集合的要求及折半查找的具体步骤。 折半查找，又称二分查找，它要求数据集合采用顺序表存储结构，且数据集合中的元素是按关键字大小有序排列的。假设数据集合的元素按关键字递增排列，折半查找算法的具体步骤为： （a）对于包含n个元素的递增数据集合R={R[1], R[2], …, R[n]}（R[i]≤R[i+1]），根据给定元素K进行折半查找，初始化待查找数据集合的下标起始位置low=1和结束位置high=n。 （b）计算中间元素下标mid=?(low+high)/2?，若R[mid]==K，则查找成功，折半查找算法结束；若R[mid] （c）若新的待查找数据集合不为空，即low≤high，则返回到上一步在新的数据集合（R[low],R[low+1],…,R[high]）上继续进行折半查找；否则查找失败。 6. 请简述分块查找对待查找数据集合的要求及分块查找的具体步骤。 在分块查找算法中，除了待查找的数据集合外，还需建立一个索引表。待查数据集合与索引表的关系描述如下：（a）将包含n个元素的待查找数据集合均匀分为b块（即b个子集合），前b-1块中元素数目s=?n/b?，最后一块中元素数目小于等于s。（b）分块后块内元素可以无序，但块间必须有序，这里假设块间为递增排列，即第i+1块中的任一元素大于第i块中的任一元素（i