我有一个项目 list ；我想对它们进行排序，但我想要一小部分随机性，这样它们就不会严格按顺序排列，只是按平均顺序排序。
我怎样才能最有效地做到这一点？
我不介意随机数的质量不是特别好，例如它只是基于输入的机会排序，例如提前终止的不完全排序。
上下文通过引入非常轻微的不精确元素来实现近乎贪婪的搜索；这是一个紧密的循环，因此要考虑排序和调用 random() 的速度
我当前的代码是执行 std::sort(这是 C++)，然后在数组的早期部分执行非常短的随机播放:
for(int i=0; i<3; i++) // I know I have more than 6 elements
std::swap(order[i],order[i+rand()%3]);
最佳答案
使用 JSort 的前两遍.建堆两次，但不执行插入排序。如果随机元素不够小，重复。
有一种方法(与不完整的 JSort 不同)允许更好地控制生成的随机性，并且时间复杂度取决于随机性(需要的随机结果越多，时间复杂度越低)。将堆排序与 Soft heap 结合使用.软堆的详细描述见pdf 1或 pdf 2 .
关于c++ - 如何有效地*几乎*对列表进行排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9116361/