sorting - "partially sorted"的数学定义

Question

例如，插入排序被描述为部分排序数组的有效算法。但如何精确定义“部分排序”呢？

Answer 1

这是一个只有少数元素不合适的数组。如果没有指定百分比或其他阈值，则部分排序和未排序之间没有严格的区别。

正式定义来自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. [...]