#include <stdio.h>
/*
1、逆数对:在一个数组中,每个数都有一个索引,如果i < j,但是a[i] > a[j],则称 a[i] 和 a[j]是一队逆数对
2、简单的方法去求逆数对,算法复杂度是 O(N^2),利用归并排序的思想去求逆数对,算法复杂度是 O(N*LogN);
3、这种方法是把一个数组先分成一个个有序数组,在合并相邻的两个数组时,去选择两个数组中较小的元素,如果选择是左边的,即 索引靠前的,则不符合逆数对的要求,如果选择的是右边的即索引靠后的,
则说明选择的这个元素和在左边那个和它比较的元素及左边在它之后的元素都能组成逆数对。
*/
int n_count;
void AdjustArr(int arr[],int first, int mid, int last,int tmp[])
{
int i = first, j = mid;
int k = mid + 1, l =last;
int m = 0;
while(i <= j&&k <= l)
{
if(arr[i] <= arr[k])
tmp[m++] = arr[i++];
else
{
tmp[m++] = arr[k++];
n_count += j - i + 1; //a[j]和a[i]、a[i + 1]......a[mid]都能组成逆数对。
}
}
while(i <= j)
tmp[m++] = arr[i++];
while(k <= l)
tmp[m++] = arr[k++];
for(i = 0;i < m;i++)
arr[i+first] = tmp[i];
}
void merge_sort(int arr[],int first,int last,int tmp[])
{
if(first < last)
{
int mid = (first + last)/2;
merge_sort(arr,first,mid,tmp);
merge_sort(arr,mid + 1,last,tmp);
AdjustArr(arr,first,mid,last,tmp);
}
}
void main()
{
int arr[8] = {1, 7, 2, 9, 6, 4, 5, 3};
int tmp[8];
merge_sort(arr,0,7,tmp);
printf("数组arr中逆数对的个数是: %d",n_count);
}
基于C语言中的一些算法和面试题
需积分: 3 132 浏览量
2024-03-29
07:15:28
上传
评论
收藏 14KB ZIP 举报
MarcoPage
- 粉丝: 2165
- 资源: 797
最新资源
- JSP-JTBC-CMS(SQLITE).rar
- MC3362和MC145151调频无线接收器的设计.pdf
- MiniRenamer-v100.0一款简单易用的批量文件重命名工具(已注册PRO版本).rar
- 小狐狸Ai系统 小狐狸ai付费创作系统V2.8.0 ChatGPT智能机器人
- 公孙离-内衣-肚兜.zipgsl
- 快慢指针判断链表是否有环-go 语言实现
- 学生成绩管理系统的设计与实现-收藏备用.pdf
- JSP+SQL网站流量统计管理系统(源代码+论文).rar
- IBM-PC-XT微机过程...道中模拟量数据的采集和处理.pdf
- JSP+SQL网上选课系统(源代码+论文+答辩PPT).rar
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈