离散化

例题

给定n (n<=100000)个正整数Ai组成的数列(Ai<=10^9, 1<=i<=n)，希望对该数列从小到大排序，如果采用冒泡排序算法，请计算需要进行的交换次数。

Sample Input 4 321 4321 21 10

Sample Output 5

概念

数据的离散化

应用背景：

离散化是一种常用的技巧，有时数据范围太大，自身无法作为数组的下标保存对应的属性，当数据只与它们之间的相对大小有关，而与具体值无关时，则可以进行离散化。

只表示模糊的相对大小

处理得到的代码

再看代码: for(i=1;i<=N;i++) b[a[i].order]=i;

重复元素处理优化

离散化示例 - 思考：如果有重复元素，如何处理？

输入数据： 4321 321 321 21 21

期望输出： 3 2 2 1 1

sort(a+1, a+1+N, cmp);
b[a[1].order]=1;

for(i=2; count=1; i<=N; i++) {
    if(a[i].val == a[i-1].val)
        b[a[i].order]=count;
    else
        b[a[i].order]=++count;
}