哪种排序算法能够更快地提供近似/近似排序？

Question

哪种排序算法产生的中间排序是好的近似值？

通过"良好的近似",我的意思是根据Kendall的tau和Spearman的脚趾等指标来确定有序列表与另一个列表的"远"(在这种情况下,确切的排序)

我想到的特定应用是人类进行主观成对比较的地方,并且可能无法进行所有n log n比较,例如heapsort或best-case quicksort.

哪些算法比其他算法更快将列表提升到接近/近似排序？

Answer 1

您可能想要查看shell排序算法.

AFAIK它是唯一可以用于主观比较的算法(意味着你不会有任何关于中值的暗示),它会在每次传递时更接近正确的排序.

以下是http://en.wikipedia.org/wiki/Shell_sort的更多信息

Answer 2

我认为是冒泡排序。优点是您可以通过额外的数据扫描来逐渐改进排序。