首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >我无法在合并排序中使用java获取反转次数

我无法在合并排序中使用java获取反转次数
EN

Stack Overflow用户
提问于 2018-10-09 02:20:43
回答 2查看 103关注 0票数 1

我把A[0..n − 1]设计成n个实数的数组。

如果一对(Ai,Aj )是乱序的,即i Aj,则称这些数是逆的。用于计算倒置次数的O(n log n)算法。

我正在尝试获取倒置的数量,但我不知道我的代码有什么问题,我认为排序方法有问题。

代码语言:javascript
复制
    class Q2
    { 
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
         static int merge(int arr[], int l, int m, int r) 
    { 
    // Find sizes of two subarrays to be merged 
    int n1 = m - l + 1; 
    int n2 = r - m; 
    int counter =0;

    /* Create temp arrays */
    int L[] = new int [n1]; 
    int R[] = new int [n2]; 

    /*Copy data to temp arrays*/
    for (int i=0; i<n1; ++i) 
        L[i] = arr[l + i]; 
    for (int j=0; j<n2; ++j) 
        R[j] = arr[m + 1+ j]; 


    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays 
    int i = 0, j = 0; 

    // Initial index of merged subarry array 
    int k = l; 
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j]) 
        { 
            arr[k] = L[i]; 

            i++; 
        } 
        else
        { 
            arr[k] = R[j]; 
            j++; 
            counter = counter + (m - i); 
        } 
        k++; 

    } 

    /* Copy remaining elements of L[] if any */
    while (i < n1) 
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 

    /* Copy remaining elements of R[] if any */
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
    return counter ;
    } 

// Main function that sorts arr[l..r] using 
// merge() 
    static int sort(int arr[], int l, int r) 
   { 
    int counter=0;
    if (l < r) 
    { 
        // Find the middle point 
        int m = (l+r)/2; 

        // count first and second halves
      counter=sort(arr, l, m); 
       counter+=sort(arr , m+1, r); 

        // count two halves
       counter+= merge(arr, l, m, r); 
    } 
    return counter;
    } 



// Driver method 
     public static void main(String args[]) 
    { 
    int arr[] = {2, 4, 1, 3,5}; 





    System.out.println("Number of inversions are " + sort(arr, 0,arr.length-1 ) ); 

      } 
      }
EN

回答 2

Stack Overflow用户

发布于 2018-10-09 04:08:37

你的方法有一个根本性的缺陷。这个

代码语言:javascript
复制
counter = counter + (m - i)

假设m之前的所有元素都小于R中的值,这是不正确的。请记住,m之前的大部分数组可能已经排序。

代码语言:javascript
复制
counter = counter + (m - l - i)

可能更正确,但在这种情况下,您可能仍然会计算双倍。请注意,当它们不在原始数组中的原始位置时,需要对它们进行计数。

票数 0
EN

Stack Overflow用户

发布于 2018-10-09 18:46:37

你得换掉

代码语言:javascript
复制
 counter = counter + (m - i)

使用

代码语言:javascript
复制
 counter = counter + (n1 - i)

插图:假设一个左数组L的数字为1,6,8,9,一个右数组R的数字为4,5,7。下面显示了循环中单个递归步骤的迭代:

通常,您可以通过以不同的顺序执行反转来对数组进行排序。但是,排序所需的最小倒数是明确的,因此与该顺序无关。由于该算法使用这些可选序列之一,因此它提供了明确的最小数量的反转。这特别意味着没有倒置被计算两次或省略。

该算法为您的数组{2,4,1,3,5}提供了总共3次反转的最小数量:(4,1),(4,3)和(2,1)。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/52708036

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档