逆序对:修订间差异
小 →top |
小无编辑摘要 |
||
第2行: | 第2行: | ||
[[File:Inversion qtl1.svg|thumb|这个置换中的一个逆序对,可以由位置对(2,4)或元素对(5,2)表示。这个置换的逆序,可以使用基于元素表示法,表示为:(3, 1), (3, 2), (5, 1), (5, 2)和(5,4)。]] |
[[File:Inversion qtl1.svg|thumb|这个置换中的一个逆序对,可以由位置对(2,4)或元素对(5,2)表示。这个置换的逆序,可以使用基于元素表示法,表示为:(3, 1), (3, 2), (5, 1), (5, 2)和(5,4)。]] |
||
在[[计算机科学]]和[[离散数学]]中,一个序列的'''逆序'''(inversion)'''[[有序对|对]]''',是失去自然[[全序|次序]]的元素对。 |
在[[计算机科学]]和[[离散数学]]中,一个序列的'''逆序'''(inversion)'''[[有序对|对]]''',是失去自然[[全序|次序]]的元素对。 |
||
==概述== |
|||
设A为一个有n个[[数字]]的[[有序集]](n>1),其中所有数字各不相同。 |
|||
如果存在正整數i, j使得1 ≤ i < j ≤ n而且A[i] > A[j],則<A[i], A[j]>這一個[[有序對]]稱為A的一個'''逆序對''',也称作逆序。逆序對的數量称作「逆序数」<ref>{{cite book|title = 线性代数|author1 = 王慧|author2 = 于海波|location = 上海|publisher = 上海交通大学出版社|year = 2018|page = 4}}</ref>或「反序數」<ref>{{cite book|title = 高等代数考研600题精解|author = 高金泰|location = 成都|publisher = 西南交通大学出版社|year = 2017|page = 31}}</ref>。 |
|||
例如:数组<2,3,8,6,1>的逆序对为:<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对。 |
|||
对于<2,1>:1 ≤ 1 < 5 ≤ 5 ,A[1] >A[5],所以<A[1],A[5]>为一个合法的逆序对。 |
|||
目前求逆序对数目比较普遍的方法是利用[[归并排序]]做到<math>O(n \log n)</math>的[[时间复杂度]]。 |
|||
当然,也可以利用[[树状数组]]、线段树来实现这种基础功能。复杂度均为<math>O(n \log n)</math>。 |
|||
== 定義 == |
== 定義 == |
||
=== 逆序 === |
=== 逆序 === |
||
設<math>\pi</math>為一個[[排列]],如果<math>i < j</math>而且<math>\pi(i) > \pi(j)</math>, |
設<math>\pi</math>為一個[[排列]],如果<math>i < j</math>而且<math>\pi(i) > \pi(j)</math>, |
||
這個序位<math>(i, j)</math>或這一對元素<math>\bigl(\pi(i), \pi(j)\bigr)</math>被稱為是<math>\pi</math>的一個逆序。通常逆序是對於排列的定義,但也可以用於[[序列]]: |
這個序位<math>(i, j)</math>{{sfn|Aigner|2007|pp=27}}{{sfn|Comtet|1974|pp=237}}或這一對元素<math>\bigl(\pi(i), \pi(j)\bigr)</math>{{sfn|Knuth|1973|pp=11}}{{sfn|Pemmaraju|Skiena|2003|pp=69}}{{sfn|Vitter|Flajolet|1990|pp=459}},被稱為是<math>\pi</math>的一個逆序。通常逆序是對於排列的定義,但也可以用於[[序列]]: |
||
設<math>S</math>是一個序列(或多重排列)。如果<math>i < j</math>而且<math>S(i) > S(j)</math>, |
設<math>S</math>是一個序列(或多重排列{{sfn|Bóna|2012|pp=57}})。如果<math>i < j</math>而且<math>S(i) > S(j)</math>, |
||
這個序位<math>(i, j)</math>或這對元素<math>\bigl(S(i), S(j)\bigr)</math>被稱為是<math>S</math>的一個逆序。 |
這個序位<math>(i, j)</math>{{sfn|Bóna|2012|pp=57}}{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=39}}或這對元素<math>\bigl(S(i), S(j)\bigr)</math>{{sfn|Barth|Mutzel|2004|pp=183}},被稱為是<math>S</math>的一個逆序。 |
||
對於根據元素組成的序列,逆序的定義不是唯一的,因為不同的序位上可能有相同的值對。逆序集是所有逆序的集合。一個排列依其序位而定義的逆序集是,它的[[置換#.E7.AC.A6.E8.99.9F|反向排列]]依其序位而定義的逆序集,反之亦然,只是交換了配對的元素。{{sfn|Gratzer|2016|pp=221}} |
|||
對於根據元素組成的序列,逆序的定義不是唯一的,因為不同的序位上可能有相同的值對。逆序集是所有逆序的集合。一個排列依其序位而定義的逆序集是,它的[[置換#.E7.AC.A6.E8.99.9F|反向排列]]依其序位而定義的逆序集,反之亦然,只是交換了配對的元素。 |
|||
=== 逆序數 === |
=== 逆序數 === |
||
'''逆序數'''是逆序集的基數,它常用於量度排列或序列的已排序程度。 |
一个序列<math>X=\langle x_1,\dots,x_n\rangle</math>的'''逆序數'''<math>\mathtt{inv}(X)</math>{{sfn|Mannila|1985}},是逆序集的基數,它常用於量度排列{{sfn|Vitter|Flajolet|1990|pp=459}}或序列{{sfn|Barth|Mutzel|2004|pp=183}}的已排序程度。 |
||
在一個排列的箭頭指向圖中,它是箭頭指向相交叉的數,也是從自指(identity)排列而得到的Kendall tau距離,以及每個反向相關向量的和,如下列定義。 |
在一個排列的箭頭指向圖中,它是箭頭指向相交叉的數{{sfn|Gratzer|2016|pp=221}},也是從自指(identity)排列而得到的Kendall tau距離,以及每個反向相關向量的和,如下列定義。 |
||
對於逆序數,依序位或依元素而定義的分別並不重要,因為排列及其反向排列都具有相同的逆序數。 |
對於逆序數,依序位或依元素而定義的分別並不重要,因為排列及其反向排列都具有相同的逆序數。 |
||
其它測量(預先)排序程度的方式,包括了為排好序列而從序列中可以刪除元素的最小數量,對序列所“進行”排序的次數和長度,每個元素在已排序位置之上的距離總和(Spearman footrule),以及排序過程中必需的最少交換次數。比較排序算法計算逆序數的時間為{{math|O(''n'' log ''n'')}}。 |
其它測量(預先)排序程度的方式,包括了為排好序列而從序列中可以刪除元素的最小數量,對序列所“進行”排序的次數和長度,每個元素在已排序位置之上的距離總和(Spearman footrule),以及排序過程中必需的最少交換次數{{sfn|Mahmoud|2000|pp=284}}。比較排序算法計算逆序數的時間為{{math|O(''n'' log ''n'')}}{{sfn|Kleinberg|Tardos|2005|pp=225}}。 |
||
目前求逆序对数目比较普遍的方法是利用[[归并排序]]做到<math>O(n \log n)</math>的[[时间复杂度]]。当然,也可以利用[[树状数组]]、线段树来实现这种基础功能。复杂度均为<math>O(n \log n)</math>。 |
|||
=== 相關聯的逆序向量 === |
=== 相關聯的逆序向量 === |
||
有三個類似的向量用於將排列的逆序,壓縮到確定唯一的向量中。它們通常被稱為'''逆序向量'''或'''Lehmer碼'''。本文將逆序向量記為(<math>v</math>),其它的兩個向量有時分別稱為''左''和''右''逆序向量;為了避免與前面的逆序向量混淆,本文將另兩個分別稱為''左逆序計數<math>l</math>''和''右逆序計數<math>r</math>''。左逆序計數是以反向colexicographic次序的排列,右逆序計數則是以字典次序的排列。 |
有三個類似的向量用於將排列的逆序,壓縮到確定唯一的向量中。它們通常被稱為'''逆序向量'''或'''Lehmer碼'''。本文將逆序向量記為(<math>v</math>)<ref>Weisstein, Eric W. [http://mathworld.wolfram.com/InversionVector.html "Inversion Vector"] From [[MathWorld]]--A Wolfram Web Resource</ref>,其它的兩個向量有時分別稱為''左''和''右''逆序向量;為了避免與前面的逆序向量混淆,本文將另兩個分別稱為''左逆序計數<math>l</math>''和''右逆序計數<math>r</math>''。左逆序計數是以反向colexicographic次序的排列<ref>Reverse colex order of finitary permutations {{OEIS|A055089}}</ref>,右逆序計數則是以字典次序的排列。 |
||
[[File:Inversion example; Rothe 1.svg|thumb|Rothe diagram]] |
[[File:Inversion example; Rothe 1.svg|thumb|Rothe diagram]] |
||
* '''逆序向量<math>v</math>''':依據元素的定義,<math>v(i)</math>是較小(右)分量為<math>i</math>的逆序數。<math>v(i)</math>是在<math>\pi</math>之中的<math>i</math>之前,元素較<math>i</math>大的數量。 |
* '''逆序向量<math>v</math>''':依據元素的定義,<math>v(i)</math>是較小(右)分量為<math>i</math>的逆序數。<math>v(i)</math>是在<math>\pi</math>之中的<math>i</math>之前,元素較<math>i</math>大的數量。{{sfn|Knuth|1973|pp=11}} |
||
*:<math>v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}</math> |
*:<math>v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}</math> |
||
* '''左逆序計數<math>l</math>''':依據位置的定義,<math>l(i)</math>是較大(右)分量為<math>l(i)</math>的逆序數。<math>l(i)</math>是在<math>\pi(i)</math>之中的<math>\pi(i)</math>之前,元素較<math>\pi(i)</math>大的數量。 |
* '''左逆序計數<math>l</math>''':依據位置的定義,<math>l(i)</math>是較大(右)分量為<math>l(i)</math>的逆序數。<math>l(i)</math>是在<math>\pi(i)</math>之中的<math>\pi(i)</math>之前,元素較<math>\pi(i)</math>大的數量。 |
||
第247行: | 第237行: | ||
如果依元素將某一排列分配給每個逆序集,所得到的排序將是[[凱萊圖]]的次序,其中的邊對應於連續兩元素的交換。對稱組的凱萊圖與其permutohedron相似,但是每個排列由其反向替換。 |
如果依元素將某一排列分配給每個逆序集,所得到的排序將是[[凱萊圖]]的次序,其中的邊對應於連續兩元素的交換。對稱組的凱萊圖與其permutohedron相似,但是每個排列由其反向替換。 |
||
== |
== 引用 == |
||
{{reflist|4|refs=}} |
|||
=== 参考书目 === |
|||
{{refbegin}} |
|||
* {{cite book |
|||
| last = Aigner | first = Martin |
|||
| title = A course in enumeration |
|||
| chapter = Word Representation |
|||
| publisher = Springer | location = Berlin, New York | year = 2007 | isbn = 978-3642072536}} |
|||
* {{cite journal |
|||
| first1 = Wilhelm | last1 = Barth |
|||
| first2 = Petra | last2 = Mutzel |author2-link = Petra Mutzel |
|||
| title = Simple and Efficient Bilayer Cross Counting |
|||
| journal = [[Journal of Graph Algorithms and Applications]] | volume = 8 | issue = 2 | pages = 179–194 | year = 2004 | doi = 10.7155/jgaa.00088| doi-access = free }} |
|||
* {{cite book |
|||
| last = Bóna | first = Miklós | author-link = Miklós Bóna |
|||
| title = Combinatorics of permutations |
|||
| chapter = 2.2 Inversions in Permutations of Multisets |
|||
| publisher = CRC Press | location = Boca Raton, FL | year = 2012 | isbn = 978-1439850510 }} |
|||
* {{cite book |
|||
| last = Comtet | first = Louis |
|||
| title = Advanced combinatorics; the art of finite and infinite expansions |
|||
|url = https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics |
|||
| chapter = 6.4 Inversions of a permutation of [n] |
|||
| publisher = D. Reidel Pub. Co | location = Dordrecht,Boston | year = 1974 | isbn = 9027704414 }} |
|||
* {{cite book |
|||
| first1=Thomas H. |last1=Cormen |authorlink1=Thomas H. Cormen |
|||
| last2=Leiserson |first2=Charles E. |authorlink2=Charles E. Leiserson |
|||
| last3=Rivest |first3=Ronald L. |authorlink3=Ron Rivest |
|||
| last4=Stein |first4=Clifford |authorlink4=Clifford Stein |
|||
| title = [[Introduction to Algorithms]] |
|||
| publisher = MIT Press and McGraw-Hill |
|||
| year = 2001 |
|||
| isbn = 0-262-53196-8 |
|||
| edition = 2nd |
|||
}} |
|||
* {{cite book |
|||
| last = Gratzer | first = George | authorlink = George Grätzer |
|||
| title = Lattice theory. special topics and applications |
|||
| chapter = 7-2 Basic objects |
|||
| publisher = Birkhäuser | location = Cham, Switzerland | year = 2016 | isbn = 978-3319442358 }} |
|||
* {{cite book |
|||
|last1=Kleinberg|first1=Jon |
|||
|last2=Tardos|first2=Éva |
|||
|title=Algorithm Design |
|||
|year=2005 |
|||
|isbn=0-321-29535-8 }} |
|||
* {{cite book |
|||
| last1 = Knuth | first1 = Donald |
|||
| title = [[The Art of Computer Programming]] |
|||
| chapter = 5.1.1 Inversions |
|||
| publisher = Addison-Wesley Pub. Co | year = 1973 | isbn = 0201896850}} |
|||
* {{cite book |
|||
|title=Sorting: a distribution theory |
|||
|chapter=Sorting Nonrandom Data |
|||
|volume=54 |
|||
|series=Wiley-Interscience series in discrete mathematics and optimization |
|||
|first=Hosam Mahmoud |last=Mahmoud |
|||
|publisher=Wiley-IEEE |year=2000 |isbn=978-0-471-32710-3}} |
|||
* {{cite book |
|||
|title=Computational discrete mathematics: combinatorics and graph theory with Mathematica |
|||
|chapter=Permutations and combinations |
|||
|first1=Sriram V. |last1=Pemmaraju |
|||
|first2=Steven S.|last2=Skiena |
|||
|publisher=Cambridge University Press |year=2003 |isbn=978-0-521-80686-2}} |
|||
* {{cite book |
|||
|title=Algorithms and Complexity |
|||
|volume=1 |
|||
|first1=J.S. |last1=Vitter |
|||
|first2=Ph. |last2=Flajolet |
|||
|editor1-first=Jan |editor1-last=van Leeuwen|editor1-link=Jan van Leeuwen |
|||
|edition=2nd |
|||
|publisher=Elsevier |year=1990 |isbn=978-0-444-88071-0 |
|||
|chapter=Average-Case Analysis of Algorithms and Data Structures |
|||
}} |
|||
{{refend}} |
|||
== |
=== 延伸阅读 === |
||
{{refbegin}} |
|||
* {{cite journal|journal=Journal of Integer Sequences|volume=4|year=2001|title=Permutations with Inversions|first=Barbara H.|last=Margolius}} |
|||
{{refend}} |
|||
=== 预排序措施 === |
|||
{{refbegin}} |
|||
*{{cite journal |
|||
| last = Mannila | first = Heikki | author-link = Heikki Mannila |
|||
| date = April 1985 |
|||
| doi = 10.1109/tc.1985.5009382 |
|||
| issue = 4 |
|||
| journal = IEEE Transactions on Computers |
|||
| pages = 318–325 |
|||
| title = Measures of presortedness and optimal sorting algorithms |
|||
| volume = C-34}} |
|||
* {{cite journal|first1=Vladimir|last1=Estivill-Castro|first2=Derick|last2=Wood|author2-link=Derick Wood|title=A new measure of presortedness|journal=Information and Computation|volume=83|issue=1|pages=111–119|year=1989|doi=10.1016/0890-5401(89)90050-3|doi-access=free}} |
|||
* {{cite journal|first=Steven S.|last=Skiena|year=1988|title=Encroaching lists as a measure of presortedness|journal=BIT|volume=28|issue=4|pages=755–784|doi=10.1007/bf01954897|s2cid=33967672}} |
|||
{{refend}} |
|||
[[Category:置换]] |
|||
[[Category:序理论]] |
[[Category:序理论]] |
||
[[Category:字符串相似性度量]] |
|||
[[Category:排序算法]] |
|||
[[Category:组合数学]] |
|||
[[Category:离散数学]] |
2023年5月29日 (一) 02:18的版本
此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2014年4月8日) |
在计算机科学和离散数学中,一个序列的逆序(inversion)对,是失去自然次序的元素对。
定義
逆序
設為一個排列,如果而且, 這個序位[1][2]或這一對元素[3][4][5],被稱為是的一個逆序。通常逆序是對於排列的定義,但也可以用於序列:
設是一個序列(或多重排列[6])。如果而且, 這個序位[6][7]或這對元素[8],被稱為是的一個逆序。
對於根據元素組成的序列,逆序的定義不是唯一的,因為不同的序位上可能有相同的值對。逆序集是所有逆序的集合。一個排列依其序位而定義的逆序集是,它的反向排列依其序位而定義的逆序集,反之亦然,只是交換了配對的元素。[9]
逆序數
一个序列的逆序數[10],是逆序集的基數,它常用於量度排列[5]或序列[8]的已排序程度。
在一個排列的箭頭指向圖中,它是箭頭指向相交叉的數[9],也是從自指(identity)排列而得到的Kendall tau距離,以及每個反向相關向量的和,如下列定義。
對於逆序數,依序位或依元素而定義的分別並不重要,因為排列及其反向排列都具有相同的逆序數。
其它測量(預先)排序程度的方式,包括了為排好序列而從序列中可以刪除元素的最小數量,對序列所“進行”排序的次數和長度,每個元素在已排序位置之上的距離總和(Spearman footrule),以及排序過程中必需的最少交換次數[11]。比較排序算法計算逆序數的時間為O(n log n)[12]。
目前求逆序对数目比较普遍的方法是利用归并排序做到的时间复杂度。当然,也可以利用树状数组、线段树来实现这种基础功能。复杂度均为。
相關聯的逆序向量
有三個類似的向量用於將排列的逆序,壓縮到確定唯一的向量中。它們通常被稱為逆序向量或Lehmer碼。本文將逆序向量記為()[13],其它的兩個向量有時分別稱為左和右逆序向量;為了避免與前面的逆序向量混淆,本文將另兩個分別稱為左逆序計數和右逆序計數。左逆序計數是以反向colexicographic次序的排列[14],右逆序計數則是以字典次序的排列。
- 逆序向量:依據元素的定義,是較小(右)分量為的逆序數。是在之中的之前,元素較大的數量。[3]
- 左逆序計數:依據位置的定義,是較大(右)分量為的逆序數。是在之中的之前,元素較大的數量。
- 右逆序計數,通常稱為Lehmer碼:依據位置的定義,是較小(左)分量為i的逆序數。是之中的之後,元素較小的數量。
Rothe圖可以協助找出和。Rothe圖是以黑點來表示1的排列矩陣,每一個位置上若為逆序(通常以叉號表示)則在其右側與下方即有一點。是圖中第列排列逆序的加總,而是欄中排列逆序的加總。排列矩陣的倒反即是此矩陣的轉置,因此某一排列的即是它轉置的,反之亦然。
範例:四個元素的全部排列
下面可排序表顯示了四個元素的集合,它的逆序集會有不同位置的24種排列、逆序相關向量和逆序數(右欄是它的反向排列,用於以colex排序)。可以看出和的位數總是相同,而和與位逆序集有關。 最右側欄是排列左上右下對角線的總和,如三角形圖示,以及r是左下右上對角線的總和(配對在下降對角線中其右側都是2,3,4組成,而在上升對角線中的左側都是1,2,3組成)。 此表中的預設排序是反向colex次序,這與的colex次序相同。的字典序與的字典序相同。
四個元素的全部排列表 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
排列的弱次序
n物品排列的集合其部份次序的結構,稱為排列的弱次序,而構成格。 以逆序集的子集關係繪出的哈斯圖,則構成了稱為permutohedron的骨架。 如果依位置將某一排列分配給每個逆序集,所得到的排序是permutohedron的次序,其中的邊對應於連續兩元素的交換。這是排列的弱排序。The identity is its minimum, and the permutation formed by reversing the identity is its maximum. 如果依元素將某一排列分配給每個逆序集,所得到的排序將是凱萊圖的次序,其中的邊對應於連續兩元素的交換。對稱組的凱萊圖與其permutohedron相似,但是每個排列由其反向替換。
引用
- ^ Aigner 2007,第27頁.
- ^ Comtet 1974,第237頁.
- ^ 3.0 3.1 Knuth 1973,第11頁.
- ^ Pemmaraju & Skiena 2003,第69頁.
- ^ 5.0 5.1 Vitter & Flajolet 1990,第459頁.
- ^ 6.0 6.1 Bóna 2012,第57頁.
- ^ Cormen et al. 2001,第39頁.
- ^ 8.0 8.1 Barth & Mutzel 2004,第183頁.
- ^ 9.0 9.1 Gratzer 2016,第221頁.
- ^ Mannila 1985.
- ^ Mahmoud 2000,第284頁.
- ^ Kleinberg & Tardos 2005,第225頁.
- ^ Weisstein, Eric W. "Inversion Vector" From MathWorld--A Wolfram Web Resource
- ^ Reverse colex order of finitary permutations (OEIS數列A055089)
参考书目
- Aigner, Martin. Word Representation. A course in enumeration. Berlin, New York: Springer. 2007. ISBN 978-3642072536.
- Barth, Wilhelm; Mutzel, Petra. Simple and Efficient Bilayer Cross Counting. Journal of Graph Algorithms and Applications. 2004, 8 (2): 179–194. doi:10.7155/jgaa.00088 .
- Bóna, Miklós. 2.2 Inversions in Permutations of Multisets. Combinatorics of permutations. Boca Raton, FL: CRC Press. 2012. ISBN 978-1439850510.
- Comtet, Louis. 6.4 Inversions of a permutation of [n]. Advanced combinatorics; the art of finite and infinite expansions. Dordrecht,Boston: D. Reidel Pub. Co. 1974. ISBN 9027704414.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001. ISBN 0-262-53196-8.
- Gratzer, George. 7-2 Basic objects. Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. 2016. ISBN 978-3319442358.
- Kleinberg, Jon; Tardos, Éva. Algorithm Design. 2005. ISBN 0-321-29535-8.
- Knuth, Donald. 5.1.1 Inversions. The Art of Computer Programming. Addison-Wesley Pub. Co. 1973. ISBN 0201896850.
- Mahmoud, Hosam Mahmoud. Sorting Nonrandom Data. Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization 54. Wiley-IEEE. 2000. ISBN 978-0-471-32710-3.
- Pemmaraju, Sriram V.; Skiena, Steven S. Permutations and combinations. Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. 2003. ISBN 978-0-521-80686-2.
- Vitter, J.S.; Flajolet, Ph. Average-Case Analysis of Algorithms and Data Structures. van Leeuwen, Jan (编). Algorithms and Complexity 1 2nd. Elsevier. 1990. ISBN 978-0-444-88071-0.
延伸阅读
- Margolius, Barbara H. Permutations with Inversions. Journal of Integer Sequences. 2001, 4.
预排序措施
- Mannila, Heikki. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers. April 1985, C–34 (4): 318–325. doi:10.1109/tc.1985.5009382.
- Estivill-Castro, Vladimir; Wood, Derick. A new measure of presortedness. Information and Computation. 1989, 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3 .
- Skiena, Steven S. Encroaching lists as a measure of presortedness. BIT. 1988, 28 (4): 755–784. S2CID 33967672. doi:10.1007/bf01954897.