归并排序与逆序对问题(C语言版)
一、引言
归并排序是一种高效且稳定的排序方法，而逆序对问题是算法领域的一个经典问题，本文教大家如何实现归并排序，以及如何使用归并排序去结果逆序对问题
二、归并排序
归并排序思想
分解：将待排序的数组分成两半，递归地对这两半进行归并排序，直到每个子数组的大小为1（此时已经是有序的）。
合并：将两个已排序的子数组合并成一个新的有序数组。合并过程通常使用两个指针，分别指向两个子数组的当前元素，比较这两个元素并将较小的元素放入结果数组中，直到所有元素都被合并。
我们借助递归可以很好的实现数据的分解和合并，我们可以借助代码区理解归并排序
#include <stdio.h>
#define MAXSIZE 100
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++];
}
}
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 100
int 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的值
四、结语
今天微服务的学习要放在晚上了