算法设计与分析-习题5.2

目录1.应用快速排序将序列EXAMPLE按照字母顺序排序并画出相应的递归调用树。2.对于本节描述的划分过程a.请证明如果两个扫描指针停下来以后指向的是同一个元素也就是说ij那么该元素的值一定等于p。b.请证明当扫描指针停下来时j指向的元素位置只可能比i指向的元素位置左移一格而不可能左移更多。3.举例说明快速排序不是一个稳定的排序算法。4.请举一个n个元素数组的例子使得我们有必要对它使用本节提到的“限位器”(防止下标越界)。限位器的值应该是多少再解释一下为什么一个限位器就能满足所有的输入呢5.对于本节给出的快速排序的版本a.一个所有元素都相等的数组是该算法的最差输入还是最优输入还是两者都不是b.一个严格递减的数组是该算法的最差输入还是最优输入还是两者都不是6.a.对于三平均中轴选择法来说一个递增数组是该算法的最差输入还是最优输入还是两者都不是b.对于递减数组回答相同的问题。7.a.对于一个包含100万随机数的数组排序快速排序比插入排序快多少倍b.是非题对于n1的n元素数组是否存在插入排序比快速排序更快的情形8.设计一个算法对n个实数组成的数组进行重新排列使得其中所有的负元素都位于正元素之前。这个算法需要兼顾空间效率和时间效率。9.a.荷兰国旗问题(Dutch national flag problem)要求对字符R、W和B构成的任意数组排序(红、白和蓝是荷兰国旗的颜色)使得所有R排在最前面W随后B在最后([Dij76])。为该问题设计一个效率为线性的在位算法。b.解释如何将快速排序算法用于求解荷兰国旗问题。10.任选一种语言实现快速排序算法。用该程序处理一批输入样本来检验该算法的理论效率的正确性。11.螺钉和螺母问题 假设我们有n个直径各不相同的螺钉以及n个相应的螺母。我们一次只能比较一对螺钉和螺母来判断螺母是大于螺钉、小于螺钉还是正好适合螺钉。然而我们不能拿两个螺母做比较也不能拿两个螺钉做比较。我们的问题是要找到每一对匹配的螺钉和螺母。为该问题设计一个算法它的平均效率必须属于集合0(nlogn)。([Raw91])1.应用快速排序将序列EXAMPLE按照字母顺序排序并画出相应的递归调用树。递归调用树如下2.对于本节描述的划分过程a.请证明如果两个扫描指针停下来以后指向的是同一个元素也就是说ij那么该元素的值一定等于p。指针i停下的条件A[i] ≥ p指针j停下的条件A[j] ≤ p题目给出i j因此同一个位置A[i]≥p且A[i]≤p根据不等式性质A[i]p证毕。b.请证明当扫描指针停下来时j指向的元素位置只可能比i指向的元素位置左移一格而不可能左移更多。反证假设停下时j ≤ i - 2即 j 比 i 靠左 ≥2 格。因为 i 停下A[i] ≥ p因为 j 停下A[j] ≤ p因为j i-1所以j1 位置在 i 左边还没被 i 扫描到。此时情况与算法过程矛盾即i从左到右遍历到j2不可能j1未被遍历严格来说i 必须一直向右走直到遇到 ≥p 的元素而 j1 这个位置在 i 的左边、j 的右边既然 i 没有走到 j1 就停下了说明A[j1] ≤ pj 已经停下说明A[j] ≤ p此时A[j1]比A[j]更先满足条件。因此j 最多停在 i-1不可能停在 i-2 或更左3.举例说明快速排序不是一个稳定的排序算法。对一个[v1,v2],其中v1v2的数组进行排序ij时调换v1和v2显然失去了稳定4.请举一个n个元素数组的例子使得我们有必要对它使用本节提到的“限位器”(防止下标越界)。限位器的值应该是多少再解释一下为什么一个限位器就能满足所有的输入呢例子对于严格升序的[1, 2, 3, 4, 5]i 从左向右找 ≥ 1 的元素所有元素都满足i 会一直走到数组末尾之外→下标越界、程序崩溃此时就需要一个限位器1保证让i能够满足到1的情况从而防止越界也就是限位器的值等于轴点至于限位器的数量快速排序 Hoare 划分中只有左指针 i 可能越界向右跑出数组。右指针 j 从右向左永远不会越界因为 j 最终会遇到轴点并停下。我们只需要在数组最右端放一个限位器就能唯一阻止 i 越界。限位器值 轴点 p对任何输入都能让 i 停下。5.对于本节给出的快速排序的版本a.一个所有元素都相等的数组是该算法的最差输入还是最优输入还是两者都不是由所有相等元素组成的数组构成了最佳情况因为所有的分割都会发生在相应子数组的中间b.一个严格递减的数组是该算法的最差输入还是最优输入还是两者都不是严格递减的数组构成了最坏情况因为所有的分割都会产生一个空子数组。注意我们需要在算法的两次连续迭代中证明这是成立的因为第一次迭代不会产生大小为 n-1 的递减数组。6.a.对于三平均中轴选择法来说一个递增数组是该算法的最差输入还是最优输入还是两者都不是三平均中轴 选A[left]、A[mid]、A[right]这三个数的中位数作为轴点 pivot。递增数组用三平均中轴时轴点会选到接近中间的元素。划分结果接近均衡效率为 Θ(n log n)。既不会像普通快排那样退化成 O (n²)也不是理论最优划分。→属于正常高效情况不是最坏也不是最优。b.对于递减数组回答相同的问题。同样对于递减数组也会选择到接近中间的元素此时划分结果也接近均衡效率为 Θ(n log n)。因此也不是最坏也不是最优7.a.对于一个包含100万随机数的数组排序快速排序比插入排序快多少倍以平均情况作为比较快排效率为Θ(nlogn)插入排序为Θ(n^2)对于比较中带入10000000b.是非题对于n1的n元素数组是否存在插入排序比快速排序更快的情形当数组已经接近有序、或规模很小时插入排序只需O(n)次操作快速排序仍有递归、划分等固定开销8.设计一个算法对n个实数组成的数组进行重新排列使得其中所有的负元素都位于正元素之前。这个算法需要兼顾空间效率和时间效率。对该数组进行一次划分算法SeparateNegPos(A[0..n-1]) // 输入实数数组A // 输出负数在前正数在后原地重排 i ← 0 j ← n-1 while i j do // 左指针找 非负数正数/0 while i j 且 A[i] 0 do i ← i1 // 右指针找 负数 while i j 且 A[j] ≥ 0 do j ← j-1 // 交换 交换 A[i] 和 A[j]效率为Θ(n),空间为Θ(1)9.a.荷兰国旗问题(Dutch national flag problem)要求对字符R、W和B构成的任意数组排序(红、白和蓝是荷兰国旗的颜色)使得所有R排在最前面W随后B在最后([Dij76])。为该问题设计一个效率为线性的在位算法。算法DutchFlag(A[0..n-1]) // 输入只含 R, W, B 的数组 // 输出R在前W在中B在后原地排序 i ← 0 // 下一个 R 要放的位置 j ← 0 // 当前扫描指针 k ← n-1 // 下一个 B 要放的位置 while j ≤ k: if A[j] R: 交换 A[i] 和 A[j] i ← i 1 j ← j 1 elif A[j] W: j ← j 1 else: // A[j] B 交换 A[j] 和 A[k] k ← k - 1b.解释如何将快速排序算法用于求解荷兰国旗问题。使用三向切分快速排序使用三向切分快速排序。选择W作为轴点 pivot。一次划分将数组分成三段小于 pivotR左边等于 pivotW中间大于 pivotB右边因为只有 3 种值一次划分即可完成排序。10.任选一种语言实现快速排序算法。用该程序处理一批输入样本来检验该算法的理论效率的正确性。#include stdio.h #include stdlib.h #include time.h // 快速排序划分函数 (Hoare) int partition(int arr[], int low, int high) { int pivot arr[low]; // 选第一个做轴点 int i low, j high; while (1) { while (arr[i] pivot) i; while (arr[j] pivot) j--; if (i j) return j; // 交换 int temp arr[i]; arr[i] arr[j]; arr[j] temp; i; j--; } } // 快速排序主函数 void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi); quickSort(arr, pi 1, high); } } // 生成随机数组 void generateArray(int arr[], int n) { for (int i 0; i n; i) { arr[i] rand() % 100000; } } int main() { srand(time(0)); int n; printf(请输入数组大小); scanf(%d, n); int *arr (int*)malloc(n * sizeof(int)); generateArray(arr, n); clock_t start clock(); quickSort(arr, 0, n - 1); clock_t end clock(); double time (double)(end - start) / CLOCKS_PER_SEC; printf(快速排序耗时%.6f 秒\n, time); free(arr); return 0; }11.螺钉和螺母问题 假设我们有n个直径各不相同的螺钉以及n个相应的螺母。我们一次只能比较一对螺钉和螺母来判断螺母是大于螺钉、小于螺钉还是正好适合螺钉。然而我们不能拿两个螺母做比较也不能拿两个螺钉做比较。我们的问题是要找到每一对匹配的螺钉和螺母。为该问题设计一个算法它的平均效率必须属于集合0(nlogn)。([Raw91])选一个螺钉 pivot。遍历所有螺母找到匹配的螺母并把螺母分成比螺钉小匹配比螺钉大用这个匹配的螺母当轴点把螺钉分成比螺母小匹配比螺母大中间一对已经匹配成功。递归处理左边小的部分和右边大的部分。