-4

这是我为 C++ 中的反转计数编写的代码。如果你写一些其他的递归方法。请尝试向我解释。我将反转计数存储在 countI 中。我得到 2 作为我在主函数中声明的数组 A[] 的输出。

 #include<iostream>
 #include<math.h>


    using namespace std;
    int countI = 0;
    void merge(int A[], int p, int q, int r)
    {
        int n1 = q - p + 1;
        int n2 = r - q;
        int *L;
        L = new int[n1];
        int *R;
        R = new int[n2];
        for (int i = 1; i <= n1; i++)
        {
            L[i] = A[p + i - 1];
            //  cout << A[p + i - 1]<<endl;
            //cout << L[i];
        }
        for (int j = 1; j <= n2; j++)
            R[j] = A[q + j];
        int i = 1, j = 1;

        //  cout << "li " << L[n1]<<"\t"<<R[n2];

        for (int k = p; k <= r; k++)
        {

            if ((L[i] <= R[j] && i <= n1) || j>n2)
            {
                A[k] = L[i];
                //cout << A[k];
                i++;

            }
            else
            {
                A[k] = R[j];
                j++;
                if (i<n1)
                countI += n1 - i+1; //here I am counting the inversion.
                //cout <<endl<<"R"<< R[j];
            }
        }
    }
    void mergeSort(int A[], int p, int r)
    {
        if (p < r)
        {
            //      cout << A[8];
            int sum = p + r;
            //int q = (sum) / 2 + (sum % 2);
            int q = (sum) / 2;
            mergeSort(A, p, q);
            mergeSort(A, q + 1, r);
            merge(A, p, q, r);

        }
    }



    int main()
    {
        //I am considering array from index 1
        int A[] = { 0, 1, 3, 5,2,4,6 };
    //  int arr[100001];
        int i = 1;
        int n = 0;
        //while (scanf("%d", &n) != EOF) { arr[i++] = n; }

        mergeSort(A, 1, 6);
        for (int i = 1; i <= 6; i++)
        {
            cout << A[i] << " ";
        }
        cout << "\n " << countI;
        system("pause");
        return 0;
    }
4

1 回答 1

1

您应该注意 C++ 使用基于 0 索引的数组。L 和 R 的第一个元素是 0，而不是 1。在 main 中调用 mergeSort 时也是如此。尝试 mergeSort(A, 0, 5)

虽然您与从 1 开始索引的错误一致。您将数组的末尾运行了 1。这可能导致您的程序崩溃；但是，如果不是这样，您经常会得到奇怪的答案（很难调试），因为您不正确地访问和写入内存。

这是一些伪代码（用于基于 0 索引的数组），它们将在执行合并排序时计算反转。

merge(A, p, m , q){
  B = [] // array size of q - p + 1
  i = p, j = m+1, k = 0, inv = 0
  while (i <= m && j <= q){
    if (A[i] < A[j])
      B[k++] = A[i++]
    else{
      B[k++] = A[j++]
      inv += m - i + 1
    }
  }
  while (i <= m)     // copy rest of left side to temp array
    B[k++] = A[i++]  // otherwise it may be overwritten
  i = 0;
  while (i < k){     // copy temp array elements back to A
    A[p+i] = B[i]
    ++i
  }
  return inv
}

merge_sort(A, p, q){
  if (p == q)
    return 0;
  m = floor((p + q)/2)
  inv1 = merge_sort(A, p, m)
  inv2 = merge_sort(A, m+1, q)
  return inv1 + inv2 + merge(A, p, m, q)
}

// you can call it like this:
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  // 10 Elements
inversions = merge_sort(A, 0, 9)    // sort and count inversions from index 0 to index 9
于 2015-07-09T15:39:44.837 回答