C / C ++程序使用合并排序对数组中的反转进行计数？
数组的倒数表示；将数组转换为排序形式需要多少次更改。当数组已经排序时，它需要进行0次反转，而在其他情况下，如果数组被反转，则反转次数将是最大的。
为了解决这个问题，我们将遵循合并排序的方法来减少时间复杂度，并使其采用分而治之算法。
输入值
A sequence of numbers. (1, 5, 6, 4, 20).
输出结果
将数字排列为升序所需的反转数。
Here the number of inversions are 2. First inversion: (1, 5, 4, 6, 20) Second inversion: (1, 4, 5, 6, 20)
算法
合并（数组，tempArray，左，中，右）
输入 -两个已合并的数组，左，右和中间索引。
输出 -排序后的合并数组。
Begin
i := left, j := mid, k := right
count := 0
while i <= mid -1 and j <= right, do
if array[i] <= array[j], then
tempArray[k] := array[i]
increase i and k by 1
else
tempArray[k] := array[j]
increase j and k by 1
count := count + (mid - i)
done
while left part of the array has some extra element, do
tempArray[k] := array[i]
increase i and k by 1
done
while right part of the array has some extra element, do
tempArray[k] := array[j]
increase j and k by 1
done
return count
EndmergeSort(array,tempArray,left,right)
输入 -给定数组和临时数组，数组的左右索引。
输出 -排序后的反转数。
Begin
count := 0
if right > left, then
mid := (right + left)/2
count := mergeSort(array, tempArray, left, mid)
count := count + mergeSort(array, tempArray, mid+1, right)
count := count + merge(array, tempArray, left, mid+1, right)
return count
End示例
#include <iostream>
using namespace std;
int merge(int arr[], int temp[], int left, int mid, int right) {
int i, j, k;
int count = 0;
i = left; //i to locate first array location
j = mid; //i to locate second array location
k = left; //i to locate merged array location
while ((i <= mid - 1) && (j <= right)) {
if (arr[i] <= arr[j]){ //when left item is less than right item
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
count += (mid - i); //find how many convertion is performed
}
}
while (i <= mid - 1) //if first list has remaining item, add them in the list
temp[k++] = arr[i++];
while (j <= right) //if second list has remaining item, add them in the list
temp[k++] = arr[j++];
for (i=left; i <= right; i++)
arr[i] = temp[i]; //store temp Array to main array
return count;
}
int mergeSort(int arr[], int temp[], int left, int right){
int mid, count = 0;
if (right > left) {
mid = (right + left)/2; //find mid index of the array
count = mergeSort(arr, temp, left, mid); //merge sort left sub array
count += mergeSort(arr, temp, mid+1, right); //merge sort right sub array
count += merge(arr, temp, left, mid+1, right); //merge two sub arrays
}
return count;
}
int arrInversion(int arr[], int n) {
int temp[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main() {
int arr[] = {1, 5, 6, 4, 20};
int n = 5;
cout << "Number of inversions are "<< arrInversion(arr, n);
}输出结果
Number of inversions are 2