- 科技
- 合并排序
递归版的合并排序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int maxn
=1e5+10;
int b
[maxn
],num
[maxn
];
void Merge(int l
,int r
)
{
int mid
=(l
+r
)/2;
int i
=l
,j
=mid
+1;
int k
=l
;
while (i
<=mid
|| j
<=r
) {
if(j
>r
|| (i
<=mid
&& num
[i
]<num
[j
])) b
[k
++]=num
[i
++];
else b
[k
++]=num
[j
++];
}
for(int i
=l
;i
<k
;i
++) num
[i
]=b
[i
];
}
void MergeSort(int l
,int r
)
{
if(l
<r
)
{
int mid
=(l
+r
)/2;
MergeSort(l
, mid
);
MergeSort(mid
+1, r
);
Merge(l
,r
);
}
}
int main(int argc
, char *argv
[]) {
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&num
[i
]);
MergeSort(1,n
);
for(int i
=1;i
<=n
;i
++) printf("%d ",num
[i
]);
}
利用合并排序还可以求逆序对
只需在 处加一句 cnt+=mid-i+1 即可
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int maxn
=1e5+10;
long long cnt
=0;
int b
[maxn
],num
[maxn
];
void Merge(int l
,int r
)
{
int mid
=(l
+r
)/2;
int i
=l
,j
=mid
+1;
int k
=l
;
while (i
<=mid
|| j
<=r
) {
if(j
>r
|| (i
<=mid
&& num
[i
]<num
[j
])) b
[k
++]=num
[i
++];
else { b
[k
++]=num
[j
++]; cnt
+=mid
-i
+1; }
}
for(int i
=l
;i
<k
;i
++) num
[i
]=b
[i
];
}
void MergeSort(int l
,int r
)
{
if(l
<r
)
{
int mid
=(l
+r
)/2;
MergeSort(l
, mid
);
MergeSort(mid
+1, r
);
Merge(l
,r
);
}
}
int main(int argc
, char *argv
[]) {
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&num
[i
]);
MergeSort(1,n
);
printf("%lld\n",cnt
);
}
自然合并排序
#include<stdio.h>
const int maxn
= 1e5+10;
int num
[maxn
];
int rec
[maxn
];
int b
[maxn
];
void merge(int l
,int r
,int mid
) {
int i
=l
,j
=mid
+1;
int k
=l
;
while (i
<=mid
|| j
<=r
) {
if(j
>r
|| (i
<=mid
&& num
[i
]<num
[j
])) b
[k
++]=num
[i
++];
else b
[k
++]=num
[j
++];
}
for(int i
=l
;i
<k
;i
++) num
[i
]=b
[i
];
}
int pass(int n
)
{
int cnt
=0;
int maxx
=num
[1];
rec
[cnt
++]=1;
for(int i
=2;i
<=n
;i
++) {
if(num
[i
]<maxx
) rec
[cnt
++]=i
;
maxx
=num
[i
];
}
rec
[cnt
++]=n
+1;
return cnt
;
}
void mergeSort(int n
) {
int cnt
=pass(n
);
while(cnt
!=2){
for(int i
=0;i
<cnt
;i
+=2)
merge(rec
[i
],rec
[i
+2]-1,rec
[i
+1]-1);
cnt
=pass(n
);
}
}
int main() {
int n
;
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++) scanf("%d",&num
[i
]);
mergeSort(n
);
for(int i
=1;i
<=n
;i
++) printf("%d ",num
[i
]);
}
Processed:
0.010, SQL:
9
