Pascal

Question

我从学校得到了一个家庭作业来创建一个项目来计算整数数组的反转。我首先尝试暴力破解它，但正如我所料，我没有超过时间限制。因此，在谷歌搜索并试图完全理解 mergeSort 以及如何实现倒置计数之后，我编写了这段代码，不幸的是它输出了错误的计数，同时正确地对数组进行了排序：

procedure mergeSort(var arr, pomarr : array of longint; start, stop : 
longint; var inv : longint);
var
  mid,i,j,k : longint;
begin
  mid := (start + stop) div 2;
  if (start < mid) then mergeSort(arr,pomarr,start,mid,inv);
  if (mid+1 < stop) then mergeSort(arr,pomarr,mid+1,stop,inv);

  i := start;
  k := start;

  while (i<= mid) and (j <= stop) do begin
    if (arr[i] < arr[j]) then begin
      pomarr[k] := arr[i];
      i += 1;
    end
    else begin
      pomarr[k] := arr[j];
      inv += mid - i;
      j += 1;
    end;
    k += 1;
  end;
  while (i <= mid) do begin
    pomarr[k] := arr[i];
    i += 1;
    k += 1;
  end;
  while (j <= stop) do begin
    pomarr[k] := arr[j];
    j += 1;
    k += 1;
  end;

  for k := start to stop do begin
    arr[k] := pomarr[k];
  end;
end;

在此先感谢您的帮助。我知道这只是声明中的一些愚蠢错误，但我似乎无法找到它。

Answer 1

所以我设法解决了我的问题。我问我的老师是什么导致了这个问题，他告诉我，在程序的头部声明一种类型的变量和在程序的主体中声明它实际上是有区别的。之后我通过创建一个数组类型修复了我的程序：

type
  numlist = array[1..250000] of longint;

并通过此类型在函数和其他任何地方声明我使用的数组。它确实有效。

据我所知，如果你声明一个数组而不使用类型，迭代实际上从 0 开始，而不是像往常一样从 1 开始。老实说，我不知道这两个事实有什么关系，但它解决了我的问题，现在它按预期运行了。

如果有人知道是什么导致了这次迭代转变，请告诉我。我其实比以前更糊涂了

Pascal - 增强的合并排序用于反转计数错误输出

Pascal - Enhanced Merge Sort for inversion count wrong output

arrays

mergesort

inversion