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

一、引言

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

二、归并排序

归并排序思想

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的值

四、结语

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