使用分治法编写C++程序,实现如果数组已经排序,则反转计数为0,但是如果数组以相反顺序排序,则反转计数为最大值。 如果a [i]> a [j]且i <j,则两个元素a [i]和a [j]构成一个倒置
时间: 2023-12-27 13:03:15 浏览: 37
以下是使用分治法编写的C++程序,实现数组排序反转计数的问题:
```c++
#include <iostream>
using namespace std;
int merge(int arr[], int temp[], int left, int mid, int right)
{
int i = left;
int j = mid;
int k = left;
int count = 0;
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
count += (mid - i);
}
}
while (i <= mid - 1)
{
temp[k++] = arr[i++];
}
while (j <= right)
{
temp[k++] = arr[j++];
}
for (i = left; i <= right; i++)
{
arr[i] = temp[i];
}
return count;
}
int mergeSort(int arr[], int temp[], int left, int right)
{
int mid, count = 0;
if (right > left)
{
mid = (right + left) / 2;
count += mergeSort(arr, temp, left, mid);
count += mergeSort(arr, temp, mid + 1, right);
count += merge(arr, temp, left, mid + 1, right);
}
return count;
}
int getReverseCount(int arr[], int n)
{
int* temp = new int[n];
return mergeSort(arr, temp, 0, n - 1);
}
int main()
{
int arr[] = { 2, 3, 8, 6, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int count = getReverseCount(arr, n);
if (count == 0)
{
cout << "Array already sorted" << endl;
}
else if (count == (n * (n - 1)) / 2)
{
cout << "Array sorted in reverse order" << endl;
}
else
{
cout << "Reverse Count: " << count << endl;
}
return 0;
}
```
该程序使用归并排序算法来计算反转计数。如果反转计数为0,则数组已经排序。如果反转计数等于(n *(n-1))/ 2,则数组以相反的顺序排序。否则,程序会输出反转计数。
请注意,该程序仅适用于整数数组。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)