"partially sorted" 的数学定义
Mathematical definition of "partially sorted"
例如，插入排序被描述为一种用于部分排序数组的高效算法。但是如何精确定义"partially sorted"？
这是一个几乎没有错位元素的数组。如果不指定百分比或其他阈值，则部分排序和未排序之间没有严格的区别。
Robert Sedgewick 和 Kevin Wayne Algorithms 的正式定义：
More generally, we consider the concept of a partially sorted array, as follows: An inversion is a pair of entries that are out of order in the array. For instance, E X A M P L E has 11 inversions: E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, and L-E. If the number of inversions in an array is less than a constant multiple of the array size, we say that the array is partially sorted.
Insertion sort 的维基百科页面表述如下：
[...] the array A will be partially sorted in the sense that each element is at most K positions away from its final, sorted position. [...]
例如，插入排序被描述为一种用于部分排序数组的高效算法。但是如何精确定义"partially sorted"？
这是一个几乎没有错位元素的数组。如果不指定百分比或其他阈值，则部分排序和未排序之间没有严格的区别。
Robert Sedgewick 和 Kevin Wayne Algorithms 的正式定义：
More generally, we consider the concept of a partially sorted array, as follows: An inversion is a pair of entries that are out of order in the array. For instance, E X A M P L E has 11 inversions: E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, and L-E. If the number of inversions in an array is less than a constant multiple of the array size, we say that the array is partially sorted.
Insertion sort 的维基百科页面表述如下：
[...] the array A will be partially sorted in the sense that each element is at most K positions away from its final, sorted position. [...]