数组的反转表示；需要进行多少次更改才能将数组转换为其排序形式。当数组已经排序时，需要 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)
登录后复制
算法
merge(array, tempArray, left, mid, right)
输入 – 两个数组，谁已经合并，左，右和中间索引。
立即学习“C++免费学习笔记（深入）”；
输出-按排序顺序合并的数组。
Begin i := left, j := mid, k := right count := 0 while imergeSort(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 countEnd登录后复制
示例
实时演示
#include 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 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 2登录后复制
以上就是使用归并排序算法编写的C/C++程序，用于计算数组中的逆序数的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2587766.html
