各大搜索引擎网站登录入口,湖南哪里有做网站的,房地产分销平台有哪些,咸宁网站建设哪家专业一、引言
归并排序是一种高效且稳定的排序方法#xff0c;而逆序对问题是算法领域的一个经典问题#xff0c;本文教大家如何实现归并排序#xff0c;以及如何使用归并排序去结果逆序对问题
二、归并排序
归并排序思想 分解#xff1a;将待排序的数组分成两半#xff0c…一、引言
归并排序是一种高效且稳定的排序方法而逆序对问题是算法领域的一个经典问题本文教大家如何实现归并排序以及如何使用归并排序去结果逆序对问题
二、归并排序
归并排序思想 分解将待排序的数组分成两半递归地对这两半进行归并排序直到每个子数组的大小为1此时已经是有序的。 合并将两个已排序的子数组合并成一个新的有序数组。合并过程通常使用两个指针分别指向两个子数组的当前元素比较这两个元素并将较小的元素放入结果数组中直到所有元素都被合并。 我们借助递归可以很好的实现数据的分解和合并我们可以借助代码区理解归并排序 #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(请输入待排关键字个数(n0): );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]如果 ij ij 且 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) 不是逆序对因为 1212。 逆序对的数量在计算排序算法的复杂度、分析数组的有序性等方面有重要应用。在某些排序算法中逆序对的数量可以用来衡量数组的“无序程度”。
简而言之就是前面的数比后面的数大那么这两个数的下标就构成了逆序对
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(请输入待排关键字个数(n0): );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的值
四、结语
今天微服务的学习要放在晚上了
