归并排序与逆序对问题(C语言版)

news/2024/11/25 12:55:30/

一、引言

归并排序是一种高效且稳定的排序方法,而逆序对问题是算法领域的一个经典问题,本文教大家如何实现归并排序,以及如何使用归并排序去结果逆序对问题

二、归并排序

归并排序思想

  1. 分解:将待排序的数组分成两半,递归地对这两半进行归并排序,直到每个子数组的大小为1(此时已经是有序的)。

  2. 合并:将两个已排序的子数组合并成一个新的有序数组。合并过程通常使用两个指针,分别指向两个子数组的当前元素,比较这两个元素并将较小的元素放入结果数组中,直到所有元素都被合并。

我们借助递归可以很好的实现数据的分解和合并,我们可以借助代码区理解归并排序


#include <stdio.h>#define MAXSIZE 100int merge[MAXSIZE]; void Merge(int a[], int left, int right, int middle) {int i = left; int j = middle + 1;         int k = left; while (i <= middle && j <= right) {if (a[i] <= a[j]) {merge[k++] = a[i++]; }else {merge[k++] = a[j++];}}while (i <= middle) {merge[k++] = a[i++];}while (j <= right) {merge[k++] = a[j++];}for (i = left; i <= right; i++) {a[i] = merge[i];}
}void Mergesort(int a[], int left, int right) {if (left < right) {int middle = (left + right) / 2;Mergesort(a, left, middle); Mergesort(a, middle + 1, right); Merge(a, left, right, middle); }
}void show(int a[], int n) {for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");
}int main() {int a[MAXSIZE];int n;printf("请输入待排关键字个数(n>0): ");scanf_s("%d", &n);printf("请依次输入关键字的数据值:\n");for (int i = 0; i < n; i++) {scanf_s("%d", &a[i]);}Mergesort(a, 0, n - 1); printf("该组数据排序后的结果: ");show(a, n);printf("该组数据逆序对的个数: %d\n", count); printf("========================================================================================================================");return 0;
}

这段代码便是归并排序的核心代码,其中分解通过递归的方式进行,而合并,我们则定义了一个函数 

void Merge(int a[], int left, int right, int middle) {int i = left; int j = middle + 1;         int k = left; while (i <= middle && j <= right) {if (a[i] <= a[j]) {merge[k++] = a[i++]; }else {merge[k++] = a[j++];count += (middle - i + 1); }}while (i <= middle) {merge[k++] = a[i++];}while (j <= right) {merge[k++] = a[j++];}for (i = left; i <= right; i++) {a[i] = merge[i];}
}

该函数我们可以实现两个有序函数的合并,合并之后还是有序函数 

那么我们如何保证我们要合并的两个数组原本是有序的呢?这就需要我们探究一下递归的本质了

我们通过如下递归,最后会将数组分解为一个一个的单独的数字

void Mergesort(int a[], int left, int right) {if (left < right) {int middle = (left + right) / 2;Mergesort(a, left, middle); Mergesort(a, middle + 1, right); Merge(a, left, right, middle); }
}

 这些一个一个的数字就是我们最早的有序数组,之后我们通过有序数组产生的数组,也都是有序的,经过我们的拆分和合并,最后就会产生一个合并好的最终的有序数组

这样归并排序的全过程就结束了

三、逆序对

1.何为逆序对

逆序对是指在一个序列中,两个元素的相对位置与它们的大小关系不一致。具体来说,对于一个序列中的两个元素 a[i]a[i] 和 a[j]a[j],如果 i<j i<j 且 a[i]>a[j] a[i]>a[j],那么就称这个对 (a[i],a[j])(a[i],a[j]) 为一个逆序对。

例如,在序列 [3,1,2][3,1,2] 中:

  • 逆序对有 (3,1)(3,1) 和 (3,2)(3,2),因为 33 在 11 和 22 之前,但 33 的值大于它们。
  • 而 (1,2)(1,2) 不是逆序对,因为 1<21<2。

逆序对的数量在计算排序算法的复杂度、分析数组的有序性等方面有重要应用。在某些排序算法中,逆序对的数量可以用来衡量数组的“无序程度”。

简而言之,就是前面的数比后面的数大,那么这两个数的下标就构成了逆序对

2.如何用归并思想求取逆序对

代码如下


#include <stdio.h>#define MAXSIZE 100int count = 0; 
int merge[MAXSIZE]; void Merge(int a[], int left, int right, int middle) {int i = left; int j = middle + 1;         int k = left; while (i <= middle && j <= right) {if (a[i] <= a[j]) {merge[k++] = a[i++]; }else {merge[k++] = a[j++];count += (middle - i + 1); }}while (i <= middle) {merge[k++] = a[i++];}while (j <= right) {merge[k++] = a[j++];}for (i = left; i <= right; i++) {a[i] = merge[i];}
}void Mergesort(int a[], int left, int right) {if (left < right) {int middle = (left + right) / 2;Mergesort(a, left, middle); Mergesort(a, middle + 1, right); Merge(a, left, right, middle); }
}void show(int a[], int n) {for (int i = 0; i < n; i++) {printf("%d ", a[i]);}printf("\n");
}int main() {int a[MAXSIZE];int n;printf("请输入待排关键字个数(n>0): ");scanf_s("%d", &n);printf("请依次输入关键字的数据值:\n");for (int i = 0; i < n; i++) {scanf_s("%d", &a[i]);}Mergesort(a, 0, n - 1); printf("该组数据排序后的结果: ");show(a, n);printf("该组数据逆序对的个数: %d\n", count); printf("========================================================================================================================");return 0;
}

 其实逆序对的求取,我们只需要在我们归并排序的基础上加入几行代码便可,其中最核心的是下面的一段

   int i = left; int j = middle + 1;         int k = left; while (i <= middle && j <= right) {if (a[i] <= a[j]) {merge[k++] = a[i++]; }else {merge[k++] = a[j++];count += (middle - i + 1); }}

 当我们的右边数组要比左边数组的数小时,便构成了逆序对的条件,但是这样的依次移动会产生几个逆序对呢,我们可以推断一下

我们左边的数列是有序的,当右边的某个数比左边的小时,它比左边那个数组中的右边的数都要小

所以

count += (middle - i + 1); 

最后的逆序对的个数便是count的值

四、结语

今天微服务的学习要放在晚上了


http://www.ppmy.cn/news/1549821.html

相关文章

社交电商专业赋能高校教育与产业协同发展:定制开发AI智能名片及2+1链动商城小程序的创新驱动

摘要&#xff1a;本文围绕社交电商有望成为高校常态专业这一趋势展开深入探讨&#xff0c;剖析国家政策认可下其学科发展前景&#xff0c;着重阐述在专业建设进程中面临的师资短缺及实践教学难题。通过引入定制开发AI智能名片与21链动商城小程序&#xff0c;探究如何借助这些新…

实现可视化大屏的适配,并且解决缩放导致的事件偏移问题

项目上有一个大屏是根据UI的设计稿&#xff0c;已经将宽高固定了&#xff0c;现在要求做适配&#xff0c;这里推荐两款用过的适配插件。 1、v-scale-screen 组件库地址&#xff1a;https://www.npmjs.com/package/v-scale-screen?activeTabreadme v-scale-screen这个插件利…

K8s 下通过prometheus监控 nginx

k8s 下有两个版本的nginx ingress 分别是 ingress nginx 以及 nginx ingress Ingress-nginx 与 Nginx-ingress - LeoZhanggg - 博客园 这里我讨论的是 nginx ingress Nginx Ingress 使用Prometheus 导出数据 nginx ingress 本身支持通过支持这个提供prometheus 格式的…

【轻量级 Java Web 整合开发(第 2 版)-框架编程技术】-期末复习(第二版)

第一章 Java Web 技术概述 作业 1、完成课后(P28)选择题和问答题&#xff08;只需完成&#xff0c;不需要提交&#xff09; 2、Tomcat的目录结构及其用途&#xff1f; bin:启动/关闭应用服务器的bat批处理命令&#xff1b; conf:包含不同的配置文件。包括server.xml&#xff…

ubuntu24.04下Matlab安装踩坑记录

1. 版本选择 link&#xff1a;https://ww2.mathworks.cn/downloads/matlab2024/2022x按官网执行后&#xff0c;均会出现暂时无法解决的bug&#xff1b;想到以前科大的虚拟机平台的版本是2019b&#xff0c;沿用这个版本即可&#xff1b;(其实很多软件根本没必要更新&#xff0c…

(免费送源码)计算机毕业设计原创定制:Java+B/S+SSM+Web前端开发技术+IDEA+MySQL+Navicat 有风小院

摘 要 信息化社会内需要与之针对性的信息获取途径&#xff0c;但是途径的扩展基本上为人们所努力的方向&#xff0c;由于站在的角度存在偏差&#xff0c;人们经常能够获得不同类型信息&#xff0c;这也是技术最为难以攻克的课题。针对有风小院等问题&#xff0c;对有风小院信息…

开源 AI 智能名片 2+1 链动模式商城小程序:场景驱动的商业创新与用户价值挖掘

摘要&#xff1a;本文围绕开源 AI 智能名片 21 链动模式商城小程序源码&#xff0c;深入分析了场景中的时间、空间、设备、社交和状态五大核心元素。阐述了各元素的表现形式、应用策略及价值&#xff0c;包括时间元素对业务周期和用户行为的影响及相应营销策略&#xff1b;空间…

transform学习

知识点讲解&#xff1a; scale 是 CSS 的 transform 属性的一部分&#xff0c;用于对元素进行比例缩放。 transform: scale(sx); transform: scale(sx, sy); /* sx&#xff1a;表示元素在 水平轴&#xff08;X轴&#xff09;的缩放比例。 sy&#xff08;可选&#xff09;&a…