7-3 起泡排序——从冒泡到归并
· 阅读需 2 分钟
问题
题面描述
如下是一个起泡排序的修改程序:
long long BubbleSort(int r[],int n){
int bound,exchange=n-1;
long long ans=0;
while(exchange!=0){
bound=exchange,exchange=0;
for(int j=0;j<bound;j++){
if(r[j]>r[j+1])
{
int temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
ans++;
exchange=j;
}
}
}
return ans;
}请你给出上述函数的返回值。
输入描述
第一行一个正整数 n (1 ≤ n ≤ 2⋅10^5^) 接下来一行共 n 个数,依次为 r[] 中的元素且 r >中的元素 r[i] (0 ≤ i < n) 满足 −10^18^ ≤ r[i] ≤ 10^18^。
输出描述
一行一个数,函数的返回值。
样例
样例1
样例输入
1
1样例输出
0
样例2
样例输入
2
1 2样例输出
0
代码长度限制 | 16 KB
时间限制 | 1000 ms
内存限制 | 512 MB
分析
要求对一个最大有 (约 )个元素的数列进行降序排序,并输出排序过程中发生交换的次数。
乍一看是要优化算法。实际上,无序序列在降序排序过程中发生的元素交换次数,正是原序列的各元素 逆序数之和。
- 最大元素个数在 int32 范围内;
- 单个元素的范围为 [, ](约 [, ]),远超 int32 范围,需要用 int64 来存储;
因此只需求输入数列的逆序数和即可,算法选择归并排序。
实现
#include<iostream>
long long ans = 0;
const int n = 200000;
long long a[n];
long long tmp[n];
void merge(int l, int m, int r) {
int i = l;
int j = m + 1;
int k = l;
while (i <= m && j <= r) {
if (a[i] > a[j]) {
tmp[k++] = a[j++];
ans += static_cast<long long>(m - i + 1);
}
else {
tmp[k++] = a[i++];
}
}
while (i <= m) {
tmp[k++] = a[i++];
}
while (j <= r) {
tmp[k++] = a[j++];
}
for (k = l; k <= r; k++) {
a[k] = tmp[k];
}
}
void mergeSort(int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(l, m);
mergeSort(m + 1, r);
merge(l, m, r);
}
}
int main() {
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
mergeSort(0, n - 1);
std::cout << ans << std::endl;
return 0;
}
提交后顺利通过。