归并排序算法分析,合并排序的递归算法
合并排序算法1。划分问题：将序列分成两半，元素尽可能多。2.递归解决方案：分别对元素的两半进行排序。3.合并问题：将两个有序表合并为一个。Merge是一种基于归并操作的有效排序算法。这个算法是分而治之的典型应用。组合有序子序列以获得完全有序的序列；也就是说，首先对每个子序列进行排序，然后对子序列段进行排序。如果两个有序表合并成一个有序表，称为双向合并。void merge _ sort (int * a，int x，int y，int * t)算法{
if(y-x ^ 1)//等价于x ^ 1y，即左半部分的右边界仍然在右半部分的左边界的左边。
{
int m=x(y-x)/2；
//分区
int p=x，q=m，I=x；
merge_sort(A，x，m，T)；
//递归查找左边的解
merge_sort(A，m，y，T)；
//递归查找正确的解决方案
while(下午上午)
{
if(q=y (pm A[p]=A[q]))T[I]=A[p]；
//从左半数组复制到临时空间
else T[I]=A[q]；
//从右半数组复制到临时空间
}
for(I=x；I y；I)A[I]=T[I]；
//从辅助空间复制回数组A
}
}动画演示
实践练习#包括iostream
使用命名空间std
int A0[15]={3，44，38，5，47，15，36，26，27，2，46，4，19，50，48 }；
int T0[15]；
void merge_sort(int *A，int x，int y，int *T) {
if(y-x ^ 1)//等价于x ^ 1y，即左半部分的右边界仍然在右半部分的左边界的左边。
{
int m=x(y-x)/2；
//分区
int p=x，q=m，I=x；
merge_sort(A，x，m，T)；
//递归查找左边的解
merge_sort(A，m，y，T)；
//递归查找正确的解决方案
while(下午上午)
{
if(q=y (pm A[p]=A[q]))T[I]=A[p]；
//从左半数组复制到临时空间
else T[I]=A[q]；
//从右半数组复制到临时空间
}
for(I=x；I y；I)A[I]=T[I]；
//从辅助空间复制回数组A
}
}
int main() {
for(int m=0；M15；m) {
cout A0[m]“”；
}
cout endl
merge_sort(A0，0，15，T0)；
for(int n=0；n15；n) {
cout A0[n]“”；
}
cout endl
返回0；
}3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
2 4 5 15 19 26 27 36 38 44 46 47 48 50.首先，只要有一个序列不是空的，就要继续归并(while (p m q y))。所以比较的时候不能直接比较A[p]和A[q]，因为可能其中一个序列是空的，从而A[p]或者A[q]。
~如果第二个排序为空(这种情况下第一个序列一定不能为空)，复制一个[p]；
~否则(第二个序列不为空)，复制A[p]当且仅当第一个序列也不为空且A[p]=A[q]。
算法分析合并排序是一种稳定的排序方法。与选择性排序一样，合并排序的性能不受输入数据的影响，但它比选择性排序好得多，因为它总是O(nlogn)的时间复杂度。代价是额外的存储空间。
对于逆序对问题，给出一列数字A 1，A 2，A n，求其逆对数，即有多少个有序对(I，j)，使i j不过是A I A J. N可高达10 ^ 6。
分而治之三步法分析：
“划分问题”:用尽可能多的元素把数列分成两半；
“递归求解”:在I和J在左边或右边的情况下，逆序计算对的个数；
“归并问题”:数一数I在左边而J在右边的对数。
关键在于合并：如何求I在左边，J在右边的反向对数？
统计学常用的技术是“分类”:只要对右边的每一个J，数出左边比它大的元素的个数f(i)，那么所有f(j)之和就是答案。
Merge可以“顺便”完成f(j)的计算：由于merge运算是从小到大进行的，所以当右边的A[j]复制到T时，左边那些没有复制到T的数都是左边大于A[j]的数。此时只需将累加器中左边元素的个数m-p相加(左边剩余的元素在区间[p，m]内，所以元素个数为
代码#包含iostream
使用命名空间std
int cnt=0，T0[15]；
int A0[15]={3，44，38，5，47，15，36，26，27，2，46，4，19，50，48 }；
void Reverse(int *A，int x，int y，int *T)
{
如果(y x 1)
{
int m=x(y-x)/2；
int p=x，q=m，I=x；
反向(A，x，m，T)；
反向(A，m，y，T)；
而(下午 上午)
{
if (q=y(p m A[p]=A[q]))
t[I]=A[p]；
其他
{
t[I]=A[q]；
CNT=m-p；
}
}
for(int I=x；I y；我)
a[I]=T[I]；
}
}
int main()
{
反向(A0，0，15，T0)；
cout cnt= cnt endl
返回0;
}
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。