【排序 · I】一种通过维护元素位置进行排序的方法

· · 休闲·娱乐

一种通过维护元素位置进行排序的方法

这文章太垃圾了被转到休闲娱乐区了。

引子

我在看 cff 老师的游记时，看到了这样几句话：

在手动排序某些东西的时候突然想到“插入排序为什么不二分找插入的位置呢”，然后发现原来插入之后数组元素后移也需要时间复杂度。

如果比较所需的时间较多就需要这么做吧，应该。不对，那我也可以选其它排序。

不过手动排序的话二分插入排序还是挺方便的（

我们发现，插入排序的瓶颈在于“插入之后数组元素后移”。

那我们能否打破瓶颈呢？

思路

我们发现，每次插入一个元素，比这个元素大的元素都得后移。那我们能否抽象这个“后移”，使其时间复杂度降为 O(\log n) 或者更优呢（其实最后没有更优，希望后人在不在其他地方排序的前提下做到更优）？

作为一个做过一些题目的 OIer，我们可以发现：这个“后移”操作不正是把比这个数大的元素位置加一吗？

作为一个学过一些东西的 OIer，我们可以发现：这个“加一”操作是可以维护的，每次处理一个数就把这个数到一个很大很大的数（反正超过数组的最大值就行）的“位置”都加一。

居然都不用二分了。

具体（伪）代码：

# 我觉得用 Python 渲染效果好一些
# 但是这看起来像个缝合怪
for i in n:
  input(a[i]);
for i in n:
  for j in i~inf: # inf 为“很大很大的数”
    c[j]++; # c[j] 为维护的位置
for i in n:
  b[c[i]]=a[i];
for i in n:
  a[i]=b[i];

但是这个代码有好几个硬伤，我们一个一个处理。

复杂度依旧 O(n^2)

这个“插入”依旧是时间复杂度瓶颈，但是我们发现这程序里要用到 c 的地方无非就两处，所需要的操作也就只有区间修改和单点查询。

作为一个学过一些数据结构的 OIer，我们发现维护这个 c 的数据结构需要满足以下几点：

作为一个没学过多少数据结构的 OIer，我们只能想到动态开点线段树了。

代码上看，第二个要求好写点，所以就写第二个要求了。

具体（伪）代码：

for i in n:
  input(a[i]);
for i in n:
  add(a[i],inf,1); # a[i]~inf 加一
for i in n:
  b[query(0,a[i])]=a[i];
for i in n:
  a[i]=b[i];

不能处理元素有重复的情况

举个例子：a=[5,5,5,5]，一通捣鼓之后 c=[0,0,0,5,\dots]，然后又是一通捣鼓之后，a 就变成 [0,0,0,5] 了。

这很明显不对啊！

但是这个问题很好办，就是这样：

  1. 先把 b 内的所有元素设为一个 a 中永远用不上的值（例如 -\text{inf}）。
  2. 再设一个缓存变量 s。
  3. 从后往前修改（因为同一个元素会被统计多次，位置肯定会在常规方法排序后那个元素所在的最后一个位置），如果 b_i=-\text{inf}，那么 b_i=s，否则 s=b_i。

具体（伪）代码：

fill(b,-inf);
s=0;
for i in 1~n:
  input(a[i]);
for i in 1~n:
  add(a[i],inf,1); # a[i]~inf 加一
for i in 1~n:
  b[query(0,a[i])]=a[i];
for i in n~1:
  if(b[i]=-inf) b[i]=s;
  else s=b[i];
for i in n:
  a[i]=b[i];

无法处理负数

那这个就更简单了，给所有 a_i 加上 \text{inf} 就行了。

当然还有这些地方要修改：

  2. 最后 a_i 要减 \text{inf}。
  3. 程序中还有些需要 \text{inf} 的地方需要变大，来达到 \text{inf} 的原本目的。建议改成 4×\text{inf}。
finf=4*inf;
fill(b,-finf);
s=0;
for i in n:
  input(a[i]);
  a[i]+=inf;
for i in 1~n:
  add(a[i],finf,1); # a[i]~inf 加一
for i in n:
  b[query(0,a[i])]=a[i];
for i in 1:
  if(b[i]=-finf) b[i]=s;
  else s=b[i];
for i in n:
  a[i]=b[i]-inf;

说点别的

  2. 没 sort 快活着干啥
  3. 其实如果 \log \text{inf}>n 可以暴力插入。

其实可能有很多人想到了这个算法。但是可能我因为过于自大将其写了下来，浪费大家的时间，抱歉。

ヾ(•ω•`)o

希望你们能对算法做些优化！