跳到主要内容

1 篇博文 含有标签「排序算法」

查看所有标签

· 阅读需 2 分钟
El Syzomnia

问题​

题面描述

如下是一个起泡排序的修改程序:

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

作者 | cugbacm
单位 | 中国地质大学（北京）
代码长度限制 | 16 KB
时间限制 | 1000 ms
内存限制 | 512 MB

分析​

要求对一个最大有 2⋅1052 \cdot 10^5（约 2182^{18}）个元素的数列进行降序排序，并输出排序过程中发生交换的次数。

乍一看是要优化算法。实际上，无序序列在降序排序过程中发生的元素交换次数，正是原序列的各元素 逆序数之和。

  1. 最大元素个数在 int32 范围内；
  2. 单个元素的范围为 [−1018-10^{18}, 101810^{18}]（约 [−260-2^{60}, 2602^{60}]），远超 int32 范围，需要用 int64 来存储；

因此只需求输入数列的逆序数和即可，算法选择归并排序。