int*_*nt3 7 sorting algorithm
我们知道几种排序,例如插入排序,对于"大多数排序"并且在随机数据上不太好的阵列非常有用.
假设我们想要分析这种算法相对于输入数据的"排序"方式的性能改进/降级.什么是生成"越来越多排序"或"越来越随机"的元素数组的好方法？我们如何衡量输入的"排序"？
Zim*_*bao 10
反转次数是数组排序量的常用度量.
(pi,pj)如果i<j和,置换p中的一对元素被称为置换中的反转 pi >pj.例如,在排列中 (3,1,2,5,4)包含3个反转(3,1),(3,2)和(5,4).
(pi,pj)
i<j
pi >pj
(3,1,2,5,4)
(3,1)
(3,2)
(5,4)
排序数组得到0反转,反向排序数组得到n*(n-1)/ 2.
归档时间：
15 年，7 月 前
查看次数：
479 次
最近记录：
13 年，5 月 前