用於計數的合併排序實現數組的反轉

Question

下面是我對數組的反轉的實現。對於某些輸入，它會產生所需的結果。爲例如：

1：0,1,2,3,4,5,6,7,8,9 - > 0反轉（正確）

2：1000,999,998,997，..... ..3,2,1 - > 499500反轉（正確）

3：-1,3,5,2,4,6- - > 3反轉（正確）

但對於

4： 9,10,8,1,4,7,6,2,5,3 - > 41反轉（錯誤）。正確答案是33。

public class Assignment1 { 
static int[] result = new int[10]; 

public static long divideW (int Arr[]) { 
    long countLeft ; 
    long countRight ; 
    long countMerge ; 

    int mid = (Arr.length)/2; 

    if (Arr.length <= 1) 
     return 0; 
    else 
    { 
     int leftArr[] = new int [mid]; 
     int rightArr[] = new int [Arr.length - mid]; 

     for (int i = 0; i < mid; i++){ 
      leftArr[i] = Arr[i]; 
     } 
     for (int j = 0; j < rightArr.length ; j++){ 
      rightArr[j] = Arr[mid + j]; 
     } 
     countLeft = divideW (leftArr); 
     countRight = divideW (rightArr); 

     //int[] result = new int[Arr.length]; 
     countMerge = conquer(leftArr, rightArr, result); 
     return (countLeft + countRight + countMerge); 
    } 
} 
public static long conquer (int []l, int[]r, int[] result) { 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    long count = 0; 
    while ((i < l.length) && (j < r.length)) { 
    if (l[i] <= r [j]) { 
     result[k] = l[i++]; 
    } 
    else if (l[i] > r[j]) { 
     result[k] = r[j++]; 
     count += l.length - i; 
    } 
    ++k; 
    } 
    while (i < l.length) { 
     result[k++] = l[i++]; 
    } 
    while (j < r.length) { 
     result[k++] = r[j++]; 
    } 
    return count; 
} 


public static void main(String[] args) { 
    Assignment1 rs = new Assignment1(); 
    int anArr[] = {9,10,8,1,4,7,6,2,5,3}; 

    System.out.println (rs.divideW(anArr)); 

    for (int i = 0 ; i < result.length; ++i) { 
     System.out.println (result[i]); 
    } 
    } 
} 

Answer 1

在你的答案的問題（我認爲這是正確的）以下：

countMerge = conquer(leftArr, rightArr, result); 

你只是在無序陣列征服部分（leftArr，rightArr）這就是反演數量不同的原因。我更改如下這段代碼和它的工作原理：

Arrays.sort(leftArr); 
Arrays.sort(rightArr); 
countMerge = conquer(leftArr, rightArr, result); 

Answer 2

您的解決方案是不正確的，因爲它不排序的數組傳遞到征服 功能

下面是我用C＃實現的代碼。

using System; 

namespace SortingAlgos 
{ 
    public class InversionCountUsingMergeSort 
    { 
     public static long InversionCount { get; set; } 
     public static void Main(string[] args) 
     { 
      //Load an array 
      int[] arrayInts = { 9, 10, 8, 1, 4, 7, 6, 2, 5, 3 };// { 10, 4, 7, 8, 6, 2, 3, 5 };//{1,3,5,2,4,6}--->3;//{ 9, 10, 8, 1, 4, 7, 6, 2, 5, 3 }-->41;//{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }--->0;//{ 10, 4, 7, 8, 6, 2, 3, 5 }; //LoadInts(); 

      Console.WriteLine("========= UnSorted Array Items =========="); 

      //Print an unsorted array 
      PrintInts(arrayInts); 

      Console.WriteLine("========== Inversion Count ========="); 
      //Sort the array 
      arrayInts = MergeSort(arrayInts); 

      //Print Sorted array 
      PrintInts(arrayInts); 
      Console.WriteLine(InversionCount); 
      Console.ReadKey(); 
     } 

     private static int[] MergeSort(int[] arrayInts) 
     { 
      if (arrayInts.Length <= 1) 
      { 
       return arrayInts; 
      } 
      else 
      { 
       int[] result = new int[arrayInts.Length]; 

       int midPoint = arrayInts.Length/2; 
       int[] leftArray = new int[midPoint]; 
       int[] rightArray; 
       if (arrayInts.Length % 2 == 0) 
       { 
        rightArray = new int[midPoint]; 
       } 
       else 
       { 
        rightArray = new int[midPoint + 1]; 
       } 

       for (int indexLeft = 0; indexLeft < midPoint; indexLeft++) 
       { 
        leftArray[indexLeft] = arrayInts[indexLeft]; 
       } 
       int indexRight = 0; 
       for (int indexOnArryInts = midPoint; indexOnArryInts < arrayInts.Length; indexOnArryInts++) 
       { 
        if (indexRight < rightArray.Length) 
        { 
         rightArray[indexRight] = arrayInts[indexOnArryInts]; 
         indexRight++; 
        } 
       } 

       leftArray = MergeSort(leftArray); 
       rightArray = MergeSort(rightArray); 
       return MergeArrays(leftArray, rightArray); 

      } 
     } 

     private static int[] MergeArrays(int[] leftArray, int[] rightArray) 
     { 
      int arraySize = leftArray.Length + rightArray.Length; 
      int[] arrayFinal = new int[arraySize]; 
      int leftIndex = 0, rightIndex = 0; 
      for (int index = 0; index < arraySize; index++) 
      { 
       if (leftIndex < leftArray.Length && rightIndex < rightArray.Length) 
       { 
        if (leftArray[leftIndex] <= rightArray[rightIndex]) 
        { 
         arrayFinal[index] = leftArray[leftIndex]; 
         leftIndex++;      
        } 
        else if (leftArray[leftIndex] > rightArray[rightIndex]) 
        { 
         arrayFinal[index] = rightArray[rightIndex]; 
         rightIndex++; 
         InversionCount += leftArray.Length - leftIndex; 
        } 
       } 
       else if (leftIndex < leftArray.Length) 
       { 
        arrayFinal[index] = leftArray[leftIndex]; 
        leftIndex++; 
       } 
       else if (rightIndex < rightArray.Length) 
       { 
        arrayFinal[index] = rightArray[rightIndex]; 
        rightIndex++; 
       } 
      } 
      return arrayFinal; 
     } 

     private static void PrintInts(int[] arrayInts) 
     { 
      for (int index = 0; index < arrayInts.Length; index++) 
      { 
       Console.WriteLine(string.Format("{0}", arrayInts[index])); 
      } 
     } 
    } 
}