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 来存储;
因此只需求输入数列的逆序数和即可,算法选择归并排序。