#include <stdio.h>
int main()
{
int sz[10]={1,2,3,4,5,6,7,8,9,10};
int *pvar=sz;
*pvar=10;
for (int i;i<10;i++)
{
sz[i]=sz[*pvar];
*pvar--;
printf("sz[%d]",*pvar);
}
return 0;
}
这里哪里错了
首先阐述一下逆序对的概念。假设有一个数组为Array[0..n] 其中有元素a[i]，a[j].如果 当i<j时，a[i]>a[j],那么我们就称（a[i],a[j]）为一个逆序对。
那么统计一个数组中的逆序对，有什么作用呢。逆序对可以反映插入排序的效率问题，如果逆序对数量多，那么插入排序的效率就低，反之亦然。
那么如何快速的找到逆序对的数量，同时又能够对数组进行排序，并且使得复杂度为O(n*logn)呢？这就可能是一个小问题
看到复杂度为n*logn 有一种亲切感，应为我们可以知道归并排序的时间复杂度为O(n*logn)。 同时归并排序是通过递归的方法建立递归树，利用最小的两个元素进行对比然后逐层向上进行递归，然后对比两个已经排好序的数组，得到最终完整的排好序的数组。
归并排序分为了3步骤;
第一步 拆分
第二步进行 计算两个同样类型但是规模较小的数组
第三步 合并两个已排好序的数组
因此从整个数组拆分过程中，我们将它不断进行拆分，而拆分得到的两个数组，又是和原数组目的和形式相同的（即都是要排序，同时如果不为最小还要进行以上3步）
这样可以想到递归解决问题，每一层进行相同的3步，知道不能进行位置。那么这个不能进行的判断显得格外重要。
那么加入了逆序对后，如何考虑呢，实际上很简单。以为从最下面的含两个元素的数组，到上层含多个元素的数组都有前后之分，这正好与逆序对性质相符，只要我
们找出前面那一个数组中假设L[i] 大于 后面一个数组中某个元素R[j]
然后就知道前面那个数组在该元素L[i]之后的元素都应该是大于R[j]的。因为在归并过程我们也进行了排序。
大概思路就是这样，以下是代码。
[cpp] view plaincopy
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#define Infinite_num 1000
int L[100];
int R[100];
int merge_sort(int Array[],int p,int q,int r)
{
int n1 = q-p+1;
int n2 = r-q;
for(int i=0;i<n1;i++)
{
L[i] = Array[p+i];
}
L[n1] = Infinite_num;
for(i=0;i<n2;i++)
{
R[i] = Array[q+i+1];
}
R[n2] = Infinite_num;
int inversions = 0;
int count = false;
int j=0;
i=0;
for(int k=p;k<=r;k++)
{
if(count==false &&(L[i]>R[j])&&(R[i]!=Infinite_num))
{
inversions = inversions+n1-i;
count = true;
}
if(L[i]<=R[j])
{
Array[k] = L[i];
i++;
}
else
{
Array[k] = R[j];
j++;
count = false;
}
}
return inversions;
}
int merge_inverse(int Array[],int p,int r)
{
int inversions = 0;
int q = -1;
if(p < r)
{
q = (p+r)/2;
inversions = inversions+merge_inverse(Array,p,q);
inversions = inversions+merge_inverse(Array,q+1,r);
inversions = inversions+merge_sort(Array,p,q,r);
}
return inversions;
}
int main(int argc, char* argv[])
{
int Array[] = {1,3,7,8,2,4,6,5};
int inverse_times = 0;
inverse_times = merge_inverse(Array,0,7);
printf("%d",inverse_times);
return 0;
}
那么统计一个数组中的逆序对，有什么作用呢。逆序对可以反映插入排序的效率问题，如果逆序对数量多，那么插入排序的效率就低，反之亦然。
那么如何快速的找到逆序对的数量，同时又能够对数组进行排序，并且使得复杂度为O(n*logn)呢？这就可能是一个小问题
看到复杂度为n*logn 有一种亲切感，应为我们可以知道归并排序的时间复杂度为O(n*logn)。 同时归并排序是通过递归的方法建立递归树，利用最小的两个元素进行对比然后逐层向上进行递归，然后对比两个已经排好序的数组，得到最终完整的排好序的数组。
归并排序分为了3步骤;
第一步 拆分
第二步进行 计算两个同样类型但是规模较小的数组
第三步 合并两个已排好序的数组
因此从整个数组拆分过程中，我们将它不断进行拆分，而拆分得到的两个数组，又是和原数组目的和形式相同的（即都是要排序，同时如果不为最小还要进行以上3步）
这样可以想到递归解决问题，每一层进行相同的3步，知道不能进行位置。那么这个不能进行的判断显得格外重要。
那么加入了逆序对后，如何考虑呢，实际上很简单。以为从最下面的含两个元素的数组，到上层含多个元素的数组都有前后之分，这正好与逆序对性质相符，只要我
们找出前面那一个数组中假设L[i] 大于 后面一个数组中某个元素R[j]
然后就知道前面那个数组在该元素L[i]之后的元素都应该是大于R[j]的。因为在归并过程我们也进行了排序。
大概思路就是这样，以下是代码。
[cpp] view plaincopy
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#define Infinite_num 1000
int L[100];
int R[100];
int merge_sort(int Array[],int p,int q,int r)
{
int n1 = q-p+1;
int n2 = r-q;
for(int i=0;i<n1;i++)
{
L[i] = Array[p+i];
}
L[n1] = Infinite_num;
for(i=0;i<n2;i++)
{
R[i] = Array[q+i+1];
}
R[n2] = Infinite_num;
int inversions = 0;
int count = false;
int j=0;
i=0;
for(int k=p;k<=r;k++)
{
if(count==false &&(L[i]>R[j])&&(R[i]!=Infinite_num))
{
inversions = inversions+n1-i;
count = true;
}
if(L[i]<=R[j])
{
Array[k] = L[i];
i++;
}
else
{
Array[k] = R[j];
j++;
count = false;
}
}
return inversions;
}
int merge_inverse(int Array[],int p,int r)
{
int inversions = 0;
int q = -1;
if(p < r)
{
q = (p+r)/2;
inversions = inversions+merge_inverse(Array,p,q);
inversions = inversions+merge_inverse(Array,q+1,r);
inversions = inversions+merge_sort(Array,p,q,r);
}
return inversions;
}
int main(int argc, char* argv[])
{
int Array[] = {1,3,7,8,2,4,6,5};
int inverse_times = 0;
inverse_times = merge_inverse(Array,0,7);
printf("%d",inverse_times);
return 0;
}
温馨提示：答案为网友推荐，仅供参考
第1个回答 2013-09-01
#include <stdio.h>
int main()
{
int sz[10]={1,2,3,4,5,6,7,8,9,10};
int *pvar=&sz[9]; //指针指向最后一个元素的地址，也就是元素 sz[9]=10的位置
int iTemp; //临时变量，用于实现两数交换
for (int i=0;i<5;i++) //给i赋初值，并且循环5次就够了
{
//实现两个变量对换
iTemp=sz[i];
sz[i]=*pvar;
*pvar=iTemp;
pvar--; //是指针向前移动一个单位
}
for(i=0;i<10;i++) //循环输出数组元素
{
printf("%d ",sz[i]);
}
return 0;
}
int main()
{
int sz[10]={1,2,3,4,5,6,7,8,9,10};
int *pvar=&sz[9]; //指针指向最后一个元素的地址，也就是元素 sz[9]=10的位置
int iTemp; //临时变量，用于实现两数交换
for (int i=0;i<5;i++) //给i赋初值，并且循环5次就够了
{
//实现两个变量对换
iTemp=sz[i];
sz[i]=*pvar;
*pvar=iTemp;
pvar--; //是指针向前移动一个单位
}
for(i=0;i<10;i++) //循环输出数组元素
{
printf("%d ",sz[i]);
}
return 0;
}
第2个回答 2013-09-01
逆序排列的本质就是交换。首先获取数组的长度，然后将第一个与最后一个交换；第二个与倒数第二个交换；以此类推，直到在中间相遇，完成逆序。
int main(){
int sz[10]={1,2,3,4,5,6,7,8,9,10};
int i, tmp;
for (i=0; i<10/2; i++)
{
tmp = sz[i];
sz[i] = sz[10-i-1];
sz[10-i-1] = tmp;
}
for (i=0; i<10; i++)
{
printf("%d ", sz[i]);
}
return 0;
}
第3个回答 2013-09-01
你的i没有赋初值，假如你赋了初值，sz[i]=sz[*pvar];这句话循环到第五次的时候sz[]=10 9 8 7 6 6 7 8 9 10 再循环5次的话结果是怎么样的知道了吧 你这样写是不对的 既然你定义了指针 那就不要这样用指针
int *pvar=sz；
for（int i=9;i>=0;i--）
{
*pvar=sz[i];
printf("d%",*pvar);
pvar++;
}
*pvar='0';
最后那句不加也可以 因为循环里面已经将排序后的数组输出了本回答被网友采纳
int *pvar=sz；
for（int i=9;i>=0;i--）
{
*pvar=sz[i];
printf("d%",*pvar);
pvar++;
}
*pvar='0';
最后那句不加也可以 因为循环里面已经将排序后的数组输出了本回答被网友采纳
第4个回答 2020-03-13
