algorithm - 如何最快地对稀疏向量进行排序

Question

我有一个整数向量。 vector的大小在2k左右，vector中的每个数都在[0, 2M]范围内，很可能为0。

由于它是一个稀疏向量，我想知道是否有比常规算法更好的算法来对向量进行排序？哪种排序算法最适合这种情况？

谢谢

Answer 1

这个答案可能有点太明显了......

既然大多数条目都是零，为什么不做一个初步的交换，这样所有的零都在一个向量的末端和另一个的非零元素。

从两端开始向量。从一端搜索第一个非零元素，从另一端搜索第一个零元素。交换它们然后继续，直到两个搜索位置相遇。现在向量在交汇点被分成两部分。一部分仅包含零元素，另一部分包含非零元素。从非零元素的交汇点开始对向量进行排序。真正需要分类的项目应该很少。

当对大约几十个元素进行排序时，实际使用的排序算法从性能的角度来看并没有太大区别(对于大约六个元素，冒泡排序很难被击败!)。