在关于排序算法的维基百科文章中， http ://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms 在冒泡排序下它说：冒泡排序也可以有效地用于几乎排序的任何长度的列表（即，元素并没有明显不合适）
所以我的问题是：如果不首先使用排序算法对列表进行排序，如何知道它是否接近排序？
问问题
83 次
2 回答
0
你熟悉一般的排序下限吗？您可以证明，在基于比较的排序算法中，任何排序算法都必须在平均情况下进行 Ω(n log n) 比较。你证明这一点的方法是通过信息论论证。基本思想是有 n! 输入数组的可能排列，并且由于您可以了解获得哪种排列的唯一方法是进行比较，因此您必须至少进行 lg n! 比较以确定您知道输入排列的结构。
我还没有计算出这方面的数学，但我怀疑你可以提出类似的论点来表明很难了解特定数组的排序方式。从本质上讲，如果您不进行大量比较，那么您将无法区分一个大部分已排序的数组和一个实际上距离排序很远的数组。因此，我所知道的所有算法都需要花费大量时间来衡量“排序性”。
例如，数组中“排序”级别的一种度量是该数组中的反转次数。您可以使用基于合并排序的分而治之算法在 O(n log n) 时间内计算数组中的反转次数，但使用该运行时您可以只对数组进行排序。
通常，您知道您的数组大部分已排序的方式是先验地知道它是如何生成的。例如，如果您正在查看从上午 8 点到下午 12 点收集的温度数据，则很可能数据已经大部分排序（以传感器读数质量的一些差异为模）。如果您的数据随着时间的推移查看股票价格，那么它也很可能是经过排序的，除非公司的轨迹非常不稳定。其他一些算法也对数组进行部分排序；例如，当要排序的数组的大小很小时，快速排序实现停止排序并用最终的插入排序通道跟进所有内容并不少见，因为那时每个元素都不会离其最终位置很远。
于 2015-08-27T19:12:53.267 回答
0
我不相信存在任何关于数组的排序或随机程度的标准化度量。
您可以提出自己的衡量标准 - 比如计算无序的相邻对的数量（在评论中建议），或者计算出现在数组中较小数字之前的较大数字的数量（这比简单的单经过）。
于 2015-08-27T21:06:00.140 回答