对给定数组进行排序时发生的反转计数称为反转计数。逆问题是一个经典问题，可以使用归并排序算法来解决。在此问题 v 中，我们将计算其左侧大于它的所有元素，并将计数添加到输出。这个逻辑是在合并排序的合并函数中完成的。
为了更好地理解这个主题，让我们举一个例子。让我们考虑合并过程中涉及的两个子数组 –
立即学习“C++免费学习笔记（深入）”；
Input: arr[] = { 1, 9, 6, 4, 5}Output: Inversion count is 5
说明
数组的反转次数
给定一个数组，找出它的反转次数。如果 (i A[j]) 则 (i, j) 对称为数组 A 的反转。我们需要对 arr 中所有此类对进行计数
例如，
数组中有5个反转
(9,6), (9,4), (9,5), (6,4), (6,5)
1.相互比较元素的值。
2.如果较低索引处的值较高，则增加计数器。
3.显示结果。
示例
#include int Merge(int arr[], int aux[], int low, int mid, int high) { int k = low, i = low, j = mid + 1; int inversionCount = 0; while (i <= mid && j <= high) { if (arr[i] <= arr[j]) { aux[k++] = arr[i++]; } else { aux[k++] = arr[j++]; inversionCount += (mid - i + 1); // NOTE } } while (i <= mid) aux[k++] = arr[i++]; for (int i = low; i > 1)); int inversionCount = 0; inversionCount += MergeSort(arr, aux, low, mid); inversionCount += MergeSort(arr, aux, mid + 1, high); inversionCount += Merge(arr, aux, low, mid, high); return inversionCount;}int main() { int arr[] = { 1, 9, 6, 4, 5 }; int N = 5; int aux[N]; for (int i = 0; i < N; i++) aux[i] = arr[i]; printf("Inversion count is %d", MergeSort(arr, aux, 0, N - 1)); return 0;}
以上就是使用归并排序算法编写的C/C++程序来计算数组中的逆序对数？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445399.html
微信扫一扫 
支付宝扫一扫 
