数组的反转表示;需要进行多少次更改才能将数组转换为其排序形式。当数组已经排序时,需要 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)
输入 - 两个数组,谁已经合并,左,右和中间索引。
输出-按排序顺序合并的数组。
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 End
输入 - 给定数组和临时数组,数组的左右索引。
输出 - 排序后的逆序对数量。
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
以上是使用归并排序算法编写的C/C++程序,用于计算数组中的逆序数的详细内容。更多信息请关注PHP中文网其他相关文章!