C语言用蛮力穷举法求逆序对,其中运用到递归,简单形式
时间: 2024-05-06 18:19:37 浏览: 54
以下是简单的递归形式的C语言代码,用蛮力穷举法求逆序对:
```c
#include <stdio.h>
int count = 0; // 存储逆序对的数量
void merge(int arr[], int left, int mid, int right)
{
int i = left;
int j = mid + 1;
int k = 0;
int temp[right - left + 1];
while (i <= mid && j <= right)
{
if (arr[i] <= arr[j])
temp[k++] = arr[i++];
else
{
temp[k++] = arr[j++];
count += mid - i + 1; // 如果arr[i] > arr[j],则左侧区间[i, mid]的所有元素都是逆序对
}
}
while (i <= mid)
temp[k++] = arr[i++];
while (j <= right)
temp[k++] = arr[j++];
for (i = left, k = 0; i <= right; i++, k++)
arr[i] = temp[k];
}
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
}
int main()
{
int arr[] = {3, 2, 1, 5, 4};
int len = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, len - 1);
printf("逆序对的数量为:%d\n", count);
return 0;
}
```
该代码通过归并排序的思想求逆序对的数量。在merge函数中,将左侧区间[i, mid]的所有元素都和右侧区间[j, right]的元素进行比较,如果arr[i] > arr[j],则左侧区间[i, mid]的所有元素都是逆序对。在mergeSort函数中,利用递归对左侧区间和右侧区间进行排序。最终,逆序对的数量存储在全局变量count中,并在主函数中输出。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![C](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)