java - 如何找到数组中的反转次数？

Question

基本上，我正在尝试用 Java 编写一个算法来确定数组中乱序的对数。因此，如果我们采用 i 和 j，并且 j 在数组中的位置高于 i 但 A[i] > A[j] 则它将这两个数字计为倒置。目前这是我所拥有的:

for(int i = 0; i<n-1; i++){
    if (A[i] > A[i+1]){
        k++;

它所做的只是比较彼此相邻的对，所以现在我试图修改它以找到数组中较低位置的值高于较高位置的数字的任意两个数字。我知道如何做类似的事情，但我希望运行时间为 (n+k)，其中 n 是数组的长度，k 是数组中的反转次数。

编辑:这是我实现插入排序的尝试:

int k = 0;
int [] A = {5, 4, 3, 2, 1};
int n = A.length;
for(int i = 1; i < n; i++){
    int temp = A[i];
    int j;
    for (j = i - 1; j >=0 && temp < A[j]; j--){
        A[j + 1] = A[j];
    A[j + 1] = A[j];
        k++;

k 应该跟踪多少次反转。对于数组 5、4、3、2、1，我返回的数字是 6。对吗？

Answer 1

解决办法是实现插入排序，统计一对相邻元素被交换的次数。这是有效的，因为插入排序对每个反转执行交换，并且只对每个反转执行交换。事实上，它的运行时间是 O(n + k)，正如您所要求的。

---

至于问题的第二部分 - 这是更正后的插入排序算法:

for (int i = 1; i < n; i++) {
    int temp = A[i];
    int j;
    for (j = i - 1; j >= 0 && temp < A[j]; j--) {
        A[j + 1] = A[j];
        k++;  // Number of inversions
    }
    A[j + 1] = temp;
}

---

额外说明:计算数组倒置的有效方法是修改合并排序算法，该算法运行时间为 O(n log n ) 时间。然而，当 k 较小时，O(n + k) 大约为 O (n)，小于 O(n log n)。事实上，合并排序的最佳情况时间仍然是 O(n log n)，而插入排序的最佳情况是 O em>(n)。因此，合并排序不会回答 OP 对 O(n + k) 算法的问题。