我实际上是在尝试解决一个问题，我有一个已排序的数组，但有几个数字是相反的。例如:1 2 3 4 9 8 7 11 12 14 是数组。
现在，我的第一个想法是应用 二分搜索 算法来查找 PEAK ( a[i]>a[i+1] && a[i]>a[i- 1])
但是，我觉得它可能不会总是给出正确的结果。此外，它可能效率不高，因为列表几乎已排序。
下一个印象:应用插入排序，因为列表已排序，如果我没记错的话，插入排序在这种情况下提供最佳性能。
那么谁能提出更好的解决方案或者我的解决方案是否正确？高效还是低效？
P.S - 这不是家庭作业!
更新:插入排序(在这种情况下为 O(n))或线性扫描以找到子序列，然后再次反转它(O(n))。如果我们可以优化它，有机会吗？或者可能在 O(logn) 中执行？
最佳答案
线性搜索第一个反转(即 a[i+1] < a[i] )，调用其索引 inv1 .继续直到反转停止，调用最后一个索引 inv2 .反转 inv1 之间的数组和 inv2 , 包括在内。
在您的示例中，inv1是 4，inv2是 6;数组元素从零开始编号。
该算法与原始条目数成线性关系。
关于arrays - 给定一个有序数组，其中有几个数字是颠倒的。如何排序？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11724879/