实际上，除了性能指标外，还有其他特征通常也同样重要。其中之一就是自然。这是什么？如果在对数组进行几乎排序时速度更快，则排序称为自然排序。哪些数组可以视为“几乎已排序”？这是两个具有相同元素的数组：
{1,2,9,3,4,5,7,6,8,10}和{9,1,6,3,10,5,4,2， 8.7}
即使是肉眼，您也可以看到第一个数组更有序（只有9和7是“不适当的”）。而在第二个数组中，数字是随机混合的。秩序的程度是什么？答案是已知的-倒数。如果A [j] <A [i]，则 j> i的一对元素A [i]和A [j]构成逆。 （在此注释中，排序的目的始终是升序。）
现在我们可以给出一个精确的定义：如果原始数组中的反转次数减少时排序速度降低，则排序称为自然排序。
在排序世界中，自然性是一种相当“稀有的果实”-S，QuickSort和Shell排序都不具有此属性。但是有人可能会说，有一种算法是绝对自然的-它是插入排序。尽管此算法对于每个有教养的人都是众所周知的，但让我简要地重复一下它的本质。
要排序的数组从头到尾扫描一次。一旦发现第i个元素和第（i-1）个元素形成一个反转，第i个元素就被“掷回”（这是通过将数组开头的所需段向右移动一个位置来实现的）。从该描述中可以清楚地看到，如果数组中的反转很少，则该算法将很快“飞过”数组。如果根本没有反演，则该算法将在O（n）时间内完成。但是在这种情况下，QuickSort会很长且乏味，无法选择一个分隔元素，将已经排序的数组划分为多个段，等等。但是，由于存在大量反转，这种情况当然会相反：插入排序的性能将下降为O（n ^ 2），而QuickSort将成为冠军-O（n * log（n））。
从我的角度来看，这种情况提出了一个自然的问题：有多少个反演胜于自然，并且插入排序的工作速度比QuickSort快？
为了回答这个问题，我进行了一系列计算实验。其实质如下。取取范围为3000到30,000个元素的整数数组，将一定数量的反转引入其中，然后通过插入和快速排序对数组进行排序。测量了排序时间（以系统滴答为单位）。为了求平均，将每种种类重复10次。结果如下：
图片显示了排序时间对引入的反转次数的依赖性。覆盆子系列当然是QuickSort，蓝色系列是插入排序。对于3万个元素的数组大小，最多约40万个反转是“自然胜利”。对于排序较少的数组，QuickSort已经更加有用。
下一张图片显示了关键的反演次数对数组大小的经验依赖性。
不难看出，对于大小为n的数组，临界的反转数约为10 * n。随着更多的反转，QuickSort变得很有用。应当注意，长度为n的数组的最大反转数为n *（n-1）/ 2。值10 * n是其中很小的一部分。这不足为奇。
据说，这些实验的结果取决于很多因素（编程语言，要排序的数据类型等）。老实说，我懒于更详细地探讨这些问题。我的实验是在VBA环境中的Microsoft Excel中完成的：
测试源代码
Private Declare Function GetTickCount Lib "kernel32" () As Long
':::
Sub JSort(A() As Long)
n& = UBound(A, 1)
For i& = 2 To n
If A(i&) < A(i& - 1) Then
j& = i& - 1
x& = A(i&)
Do While (A(j&) > x&)
A(j& + 1) = A(j&)
j& = j& - 1
If j& = 0 Then Exit Do
Loop
A(j& + 1) = x&
End If
Next i&
End Sub
':::
Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
If (e - b) <= 1 Then Exit Sub
i& = b
j& = e
w& = A((i& + j&) / 2)
Do While (i& < j&)
Do While (A(i&) < w&)
i& = i& + 1
Loop
Do While (A(j&) > w&)
j& = j& - 1
Loop
If i& < j& Then
tmp& = A(i&)
A(i&) = A(j&)
A(j&) = tmp&
i& = i& + 1
j& = j& - 1
End If
Loop
If j& > b Then QSort A, b, j&
If i& < e Then QSort A, i&, e
End Sub
'::: ( )
Sub InsInv(A() As Long, k As Long)
n& = UBound(A, 1)
For i& = 1 To k
Do
k1& = n& * Rnd
k2& = n& * Rnd
If (k1& <> k2&) And (k1& >= 1) And (k2& >= 1) Then Exit Do
Loop
tmp& = A(k1&)
A(k1&) = A(k2&)
A(k2&) = tmp&
Next i&
End Sub
':::
Function NumInv(A() As Long) As Long
n& = UBound(A, 1)
For i& = 1 To n& - 1
For j& = i& + 1 To n&
If A(j&) < A(i&) Then NumInv = NumInv + 1
Next j&
Next i&
End Function
':::
Sub Gtest_1()
Dim Eta() As Long
Dim Arr() As Long
Size& = CLng(InputBox("Sz="))
ReDim Eta(1 To Size&) As Long
ReDim Arr(1 To Size&) As Long
Randomize
For i& = 1 To Size&
Eta(i&) = i&
Next i&
q# = Size& * (Size& - 1) / 2
For iii% = 1 To 10
InsInv Eta, CLng(iii%)
ni# = CDbl(NumInv(Eta))
Cells(iii%, 1).Value = ni#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
JSort Arr
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
Next l%
Cells(iii%, 2).Value = S#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
QSort Arr, 1, Size&
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
If Not check(Arr) Then Exit Sub
Next l%
Cells(iii%, 3).Value = S#
DoEvents
Next iii%
MsgBox "OK"
End Sub
感谢您的关注！
PS
并感谢所有指出我的错误的人！（Timsort的拼写不正确-在第一版中有“ TeamSort”和QuickSort中缺少的“ i”）。是的！-（特别针对完美主义者）QuickSort可以“降低”到二次性能。但是在这篇文章中，我考虑的不是QuickSort最坏的情况，而是最佳的使用情况。