问题
我有一个应用程序，我想对元素a0，a1，...，an-1的数组a进行排序。我有一个比较函数cmp(i，j)比较元素ai和aj和一个交换函数swap(i，j)，它交换数组的元素ai和aj。在应用程序中，执行cmp(i，j)函数可能会非常昂贵，以至于执行一次cmp(i，j)花费的时间比排序中的任何其他步骤都要长(其他cmp(i，j除外) )，当然)一起。您可能会认为cmp(i，j)是相当长的IO操作。
为了这个问题，请假设没有办法使cmp(i，j)更快。假设所有可能使cmp(i，j)更快的优化都已经完成。
问题
昂贵的(i，j)的存在是否可以提供一种更好的算法来避免昂贵的比较操作？如果是，您能指出我这种算法吗？
例
这是一个与我拥有的应用程序并不完全不同的示例。
考虑一组可能较大的文件。在此应用程序中，目标是在其中找到重复的文件。从本质上讲，这可以归结为按任意标准对文件进行排序，然后按顺序遍历它们，输出遇到的相等文件的序列。
当然，海量数据中的读取器很昂贵，因此，例如，一个人只能读取每个文件的第一个兆字节，并对该数据计算哈希函数。如果文件比较相等，则哈希也一样，但相反的情况可能不成立。两个大文件只能在结尾处的一个字节中不同。
在这种情况下，cost(i，j)的实现只是检查散列是否相等。如果是这样，则必须进行昂贵的深度比较。
最佳答案
我将尽力回答每个问题。
传统的排序方法可能会有一些变化，但是总的来说，对列表进行排序所需的最小比较数存在数学上的限制，并且大多数算法都利用了这一点，因为比较通常不便宜。您可以尝试按其他方式进行排序，也可以尝试使用更快的快捷方式来近似实际的解决方案。
我认为您无法绕过至少进行最少数量的比较的必要性，但是您可能可以更改比较的内容。如果您可以比较数据的哈希值或子集而不是整个数据，那肯定会有所帮助。您可以做的任何简化比较操作的方法都会有很大的不同，但是如果不知道数据的具体细节，就很难提出具体的解决方案。
检查这些: