试图弄清楚哪种类型的数组最多包含 n 次反转，其中 n 是数组大小。我在想一个几乎已排序的数组将属于这种情况，并且还有一个几乎完全排序的数组，其中最大元素和最小元素切换，例如..
9 2 3 4 5 6 7 8 1
所以我的想法是，当一个数组最多有 n 次反转时，可以肯定地说该数组几乎是排序的吗？或者还有其他情况，数组最多有 n 次反转并且几乎没有排序。
“最少”排序的数组（即反向排序）有1 + 2 + 3 + ... + n-1 = n(n-1)/2反转。
一个数组的反转越少，它的排序就越“多”。
而且，由于n它比 小很多n(n-1)/2，因此可以调用具有n“几乎排序”的反转数组。
这个数组有n-1反转：
9 1 2 3 4 5 6 7 8
针对您的评论，插入排序的复杂性是O(n + d)，其中d是反转的数量，因此它将运行O(n)反转O(n)。