如何选择列表中所有无序的元素？

这个问题源于评论里的讨论这个答案 https://stackoverflow.com/questions/1390832/how-to-sort-nearly-sorted-array-in-the-fastest-time-possible-java/1390842#1390842.

首先，我们很难定义什么是无序。以 Pavel Shved 给出的例子为例，在列表 [1,5,10,2,3,4,5,6,7,8,9,10,11] 中，我们可以“清楚地”看到 5 和 10（索引 1 2) 发生故障。但简单地检查某种排序列表不变量的简单算法不会指出这些。

• 检查a[i-1]<=a[i] for all 0<i<=N将产生索引 3 处的元素（即 2）；

• 检查a[j]<=a[i] for all 0<=i<=N and 0<=j<=i将产生索引 3 到 12 中的所有元素；

我的问题是：你能想出一种算法来解决这个问题并产生“正确答案”（即索引 1 和 2）吗？如果是这样，它会在什么时间和内存复杂度下运行？

也许最好的方法是首先找到最长递增子序列 http://en.wikipedia.org/wiki/Longest_increasing_subsequence然后将不属于该序列的所有元素视为乱序。链接页面上提供的算法运行于O(n log n)时间和用途O(n)空间（除了列表本身的空间）。

对于您的示例情况，这种方法肯定会产生正确的答案，因为最长的递增子序列将是 1 到 11 序列，不包括额外的 5 和 10。