如何最快地排序稀疏向量

Question

我有一个整数向量。向量的大小约为2k，向量中的每一个数都在0，2M的范围内，很有可能是0。

因为它是稀疏向量，我想知道是否有比常规算法更好的算法来排序向量？在这种情况下，哪种排序算法最好？

谢谢

Answer 1

如果你有一个2000元素的向量，不要太担心如何排序它.它很小！

也就是说，如果你有一个有n个整数的向量，每一个都在0到M之间，而且M是小的，你可以用计数排序在O(n)时间内对它进行排序。

如果向量在某个已知范围内有n个实数，并且这些数是均匀分布的，则可以使用桶分类在O(n)期望时间内对它们进行排序。

Answer 2

这个答案可能太明显了..。

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

从向量的两端开始。从一端搜索第一个非零元素，从另一端搜索第一个零元素。交换它们，然后继续，直到这两个搜索位置相遇为止。该向量现在在集合点被划分为两部分。一个部分只包含零元素，另一部分包含非零元素。将集合点上的向量排序到非零元素上。应该有非常少的项目确实需要排序。

在对几十个元素进行排序时，实际使用的排序算法从性能角度看并没有多大区别(对于大约6个元素来说，气泡排序是很难克服的！)

Answer 3

您描述的是一个规则的密集向量，它恰好有很多0元素。稀疏向量只存储非零元素，如果没有存储元素，则假定为0。

要对稀疏向量进行排序，只需将其正常排序。2000已经很小了，但是如果您真正使用稀疏结构，并且“元素很可能是0”，那么这个数字就会小得多。

稀疏结构的一个例子是vector< pair<int, double> >，其中pair.first是索引，pair.second是值。