数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学使用归并排序计算数组中逆序对的 C/C++ 程序？
对给定数组进行排序时发生的逆序对的数量称为逆序对数。逆序对问题是一个经典问题，可以使用归并排序算法解决。在这个问题中，我们将计算数组中每个元素左侧比它大的元素的数量，并将计数添加到输出中。此逻辑在归并排序的合并函数中完成。
为了更好地理解主题，让我们举个例子。让我们考虑两个参与合并过程的子数组 -
Input: arr[] = { 1, 9, 6, 4, 5}
Output: Inversion count is 5解释
数组的逆序对数
给定一个数组，找出它的逆序对数。如果 (i < j) 且 (A[i] > A[j])，则对 (i, j) 称为数组 A 的逆序对。我们需要计算数组 arr 中所有这样的对。
例如，
数组中有 5 个逆序对
(9,6), (9,4), (9,5), (6,4), (6,5)
1. 比较元素的值。
2. 如果较低索引处的数值较高，则递增计数器。
3. 显示结果。
示例
#include <stdio.h>
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 <= high; i++)
arr[i] = aux[i];
return inversionCount;
}
int MergeSort(int arr[], int aux[], int low, int high) {
if (high == low) // if run size == 1
return 0;
int mid = (low + ((high - low) >> 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;
}
更新于: 2019年8月19日
234 次查看
广告