寻找一种算法，尽可能少的比较操作 [英] Looking for a sort algorithm with as few as possible compare operations

问题描述

我要排序，其中比较是人类进行项目：

I want to sort items where the comparison is performed by humans:

• 图片
• 工作项目优先级
• ...

有关这些任务比较的数量是性能的限制因素

For these tasks the number of comparisons is the limiting factor for performance.

• 什么是需要比较的最小数量（我假设> N 对于 N 项目）？
• 在哪个算法保证这一最低多少？

• What is the minimum number of comparisons needed (I assume > N for N items)?
• Which algorithm guarantees this minimum number?

推荐答案

我不认为你很可能会得到比的有关排序的维基百科页面。

I don't think you're likely to get a better answer than the Wikipedia page on sorting.

摘要：

• 对于任意的比较（在这里你不能使用像基数排序），最好你能做到的，是为O（n log n）的
• 各种算法实现这一点 - 见的算法比较
。
• 在常用的快速排序是O（n log n）的一个典型案例，但为O（n ^ 2）在最坏的情况;经常有办法避免这种情况，但如果你真的担心比较的成本，我喜欢的东西归并或堆排序去。这部分取决于现有的数据结构。

如果人类正在做比较，是他们也做了排序？你有你需要使用一个固定的数据结构，或者你能有效地创建使用平衡二叉树插入排序的副本吗？什么是存储需求？

If humans are doing the comparisons, are they also doing the sorting? Do you have a fixed data structure you need to use, or could you effectively create a copy using a balanced binary tree insertion sort? What are the storage requirements?

这篇关于寻找一种算法，尽可能少的比较操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！