我们知道，插入排序等几种排序方法在“大部分排序”的数组上效果很好，但在随机数据上效果不佳。
假设我们想要描述这种算法相对于输入数据“排序”的方式的性能改进/退化。生成“越来越排序”或“越来越随机”的元素数组的好方法是什么？我们如何衡量输入的“分类度”？
最佳答案
Number of Inversion是衡量数组排序程度的常用指标。
一对元素(pi,pj)在排列中 p 被称为排列中的反转如果 i<j和 pi >pj .例如，在排列中 (3,1,2,5,4)包含 3 个反转 (3,1) , (3,2)和 (5,4) .
排序数组得到 0 个反转，反向排序数组得到 n*(n-1)/2。
关于algorithm - 针对部分排序的数据分析排序算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5113158/