首页 > 试题广场 >

设数组A[1],A[2],…,A[N],已存入了数据,调用不

[填空题]
设数组A[1],A[2],…,A[N],已存入了数据,调用不同的排序程序,则数据比较的次数将会不同,试计算分别调用下列不同的排序过程的比较运算的次数。其中SWAP(I,J)表示A[I]与A[J]进行交换。
(1)
PROCEDURE   SORT1(N : INTEGER);
VAR
  I, J : INTEGER;
BEGIN
  FOR  I:=1  TO  N - 1  DO
    FOR  J:=1  TO  N  DO
      IF A[J] < A[I] THEN  SWAP (I, J)
END;
调用该过程的语句为SORT1(N),比较运算的次数为:_____1_____
(2)
PROCEDURE   SORT2(I, N : INTEGER);
VAR
  J : INTEGER;
BEGIN
  IF  I = N  THEN  WRITE(A[N])
  ELSE FOR  J:=I + 1   TO  N  DO
  BEGIN
    IF  A[J] < A[I]  THEN  SWAP (I, J)
      WRITE(A[I]);
    SORT2(I + 1, N)
  END
END
调用该过程的语句为SORT2(1,N),比较运算的次数为:______2____

(3)
PROCEDURE   SORT3(I, J : INTEGER);
VAR
  M : INTEGER;
BEGIN
  IF  I <> J   THEN
  BEGIN
    M := (I + J) DIV 2;
    SORT3(I, M);
    SORT3(M + 1, J);
    MERGE; { 假设合并的元素分别为P、G个,需要比较P+G次 }
  END;
END;
调用该过程的语句为SORT3(1,N),比较运算的次数为:______3____

这道题你会答吗?花几分钟告诉大家答案吧!