算法作业_5

Python

注：(li, si) <- Compare(x, y); 代表在比较 x,y 后，将较大值赋予 li, 将较小值赋予 si。在下面伪码中，i 指第 i 次比较。

5_1

用 6 次比较在 5 个元素中找到中位数；

Algorithm FindMid_In6(A[])
  (l1, s1) <- Compare(A[0], A[1]);
  (l2, s2) <- Compare(A[3], A[4]);
  l3 <- Max(l1, l2);
  s4 <- Min(s1, s2);
  s5 <- Min(l3, A[2]);
  mid <- Max(s4, s5);
  return mid;

5_2

用 7 次比较完成 5 个元素的排序

Algorithm Sort_In7(A[])
  (l1, s1) <- Compare(A[0], A[1]);
  (l2, s2) <- Compare(A[3], A[4]);
  (l3, s3) <- Compare(l1, l2);
  (l4, s4) <- Compare(s1, s2);
  (max, s5) <- Compare(l3, A[2]);
  (mid, min) <- Compare(s4, s5);
  B[0] <- min;
  B[2] <- mid;
  B[4] <- max;
  (l7, s7) <- Compare(s3, l4);
  B[1] <- s7;
  B[3] <- l7;
  return B[];