使用合并排序查找数组的所有反转

Question

我正在尝试实现使用合并排序查找数组所有反转的流行算法，但它一直输出错误的答案，它计算的反转太多了 - 我相信部分或全部子数组正在被在重复调用中迭代了太多次？我不能完全确定它 - 我会很感激一些关于为什么会发生这种情况的指示。请在下面的 java 中查看我的实现：

public class inversionsEfficient {

  public int mergeSort(int[] list, int[] temp, int left, int right) {
    int count = 0;
    int mid = 0;

    if(right > left) {
      mid = (right+left)/2;
      count += mergeSort(list, temp, left, mid);
      count += mergeSort(list, temp, mid+1, right);
      count += merge(list, temp, left, mid+1, right);
    }

    return count;
  }

  public int merge(int[] list, int[] temp, int left, int mid, int right) {
    int count = 0;
    int i = left;
    int j = mid;
    int k = left;

    while((i<=mid-1) && (j<=right)) {
      if(list[i] <= list[j]) {
        temp[k] = list[i];
        k += 1;
        i += 1;
      }
      else {
        temp[k] = list[j];
        k += 1;
        j += 1;
        count += mid-1;
      }
    }

    while(i<=mid-1) {
      temp[k] = list[i];
      k += 1;
      i += 1;
    }

    while(j<=right) {
      temp[k] = list[j];
      k += 1;
      j += 1;
    }

    for(i=left;i<=right;i++) {
      list[i] = temp[i];
    }

    return count;
  }

  public static void main(String[] args) {
    int[] myList = {5, 3, 76, 12, 89, 22, 5};
    int[] temp = new int[myList.length];

    inversionsEfficient inversions = new inversionsEfficient();
    System.out.println(inversions.mergeSort(myList, temp, 0, myList.length-1));
  }
}

该算法基于 Cormen 的算法简介中的伪代码： [1]: https://i.stack.imgur.com/ea9No.png

Answer 1

而不是-

count += mid - 1;

尝试-

count += mid - i;

整个解决方案变成如下图：-

public class inversionsEfficient {

    public int mergeSort(int[] list, int[] temp, int left, int right) {
        int count = 0;
        int mid = 0;

        if (right > left) {
            mid = (right + left) / 2;
            count += mergeSort(list, temp, left, mid);
            count += mergeSort(list, temp, mid + 1, right);
            count += merge(list, temp, left, mid + 1, right);
        }

        return count;
    }

    public int merge(int[] list, int[] temp, int left, int mid, int right) {
        int count = 0;
        int i = left;
        int j = mid;
        int k = left;

        while ((i <= mid - 1) && (j <= right)) {
            if (list[i] <= list[j]) {
                temp[k] = list[i];
                k += 1;
                i += 1;
            } else {
                temp[k] = list[j];
                k += 1;
                j += 1;
                count += mid - i; // (mid - i), not (mid - 1)
            }
        }

        while (i <= mid - 1) {
            temp[k] = list[i];
            k += 1;
            i += 1;
        }

        while (j <= right) {
            temp[k] = list[j];
            k += 1;
            j += 1;
        }

        for (i = left; i <= right; i++) {
            list[i] = temp[i];
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 76, 12, 89, 22, 5};
        int[] temp = new int[arr.length];

        inversionsEfficient inversions = new inversionsEfficient();
        System.out.println(inversions.mergeSort(arr, temp, 0, arr.length - 1));
    }

}

题中提到的示例数组，上面代码生成的输出是8，这是正确的，因为数组有8次反转[5, 3, 76, 12, 89, 22, 5] -

 1. (5, 3)
 2. (76, 12)
 3. (76, 22)
 4. (76, 5)
 5. (12, 5)
 6. (89, 22)
 7. (89, 5)
 8. (22, 5)

代码更改说明

本算法计算需要反转的次数为左子数组反转次数+右子数组反转次数+合并过程反转次数之和。

如果list[i] > list[j]，则有(mid – i)个倒置，因为左右子数组是有序的。这意味着左子数组 (list[i+1], list[i+2] … list[mid]) 中的所有剩余元素也将大于 list[j].

有关更详细的说明，请查看 GeeksForGeeks article on Counting Inversions。

使用合并排序查找数组的所有反转

Finding all inversions of an array using Merger-Sort

java

arrays

recurrence

inversion

代码更改说明