3

我实际上是在尝试解决一个问题，即我有一个已排序但有几个数字颠倒的数组。例如： 1 2 3 4 9 8 7 11 12 14是数组。

现在，我的第一个想法是应用一个Binary Search算法来找到一个PEAK ( a[i]>a[i+1] && a[i]>a[i-1])

但是，我觉得它可能并不总是给出正确的结果。此外，由于列表几乎已排序，因此它可能效率不高。

下一个印象：Insertion Sort如果我没记错的话，由于列表已排序并且插入排序在这种情况下提供最佳性能，因此应用。

那么任何人都可以提出更好的解决方案，或者我的解决方案是否正确？有效还是无效？

PS-这不是作业！

更新：插入排序（在这种情况下为 O（n））或线性扫描以找到子序列，然后再次反转它（O（n））。如果我们可以优化它，还有机会吗？或者可能在 O(logn) 中做？

4

5 回答 5

4

线性搜索第一个反转（即a[i+1] < a[i]），称为它的索引inv1。继续直到反转停止，调用最后一个索引inv2。反转 和 之间的数组inv1，inv2包括在内。

在您的示例中，inv1是 4，并且inv2是 6；数组元素从零开始编号。

该算法在原始条目的数量上是线性的。

于 2012-07-30T15:50:26.567 回答
3

如果您确定列表已排序，除了嵌入的反向子序列，我建议您进行简单扫描，检测反向子序列的开头（通过查找第一个反向变化），扫描到末尾子序列（更改恢复正确方向）并反转子序列。如果它们不重叠，这也应该适用于多个子序列。复杂度应该是 O(n)。

于 2012-07-30T15:49:14.383 回答
1

注意：应该有一个额外的决定是在 {4,9} 之间还是在 {9,8} 之间进行切割。（我只是添加一个;-)

#include <stdio.h>

int array[] = {1,2,3,4,9,8,7,11,12,14};

unsigned findrev(int *arr, unsigned len, unsigned *ppos);
void revrev(int *arr, unsigned len);

unsigned findrev(int *arr, unsigned len, unsigned *ppos)
{
unsigned zlen,pos;

for(zlen=pos=0; pos < len-1; pos++ ) {
        if (arr[pos+1] < arr[pos]) zlen++;
        else if (zlen) break;
        }
if (zlen) *ppos = pos - zlen++;

return zlen;
}

void revrev(int *arr, unsigned len)
{
unsigned pos;
for (pos = 0; pos < --len; pos++) {
        int tmp;
        tmp = arr[pos];
        arr[pos] = arr[len] ;
        arr[len] = tmp;
        }
}

int main(void)
{
unsigned start,len;

len = findrev(array, 10, &start);
printf("Start=%u Len=%u\n", start, len);
revrev(array+start, len);

for (start=0; start < 10; start++) {
        printf(" %d", array[start] );
        }
printf("\n"  );

return 0;
}

注意：反向运行的长度也可以通过二进制搜索大于（或等于）反向序列的第一个元素的第一个值来找到。

于 2012-07-30T16:15:05.887 回答
0

Timsort 非常擅长对大部分已经排序的数组进行排序 - 最重要的是，它通过使用两个不同的合并步骤来进行就地合并排序，具体取决于哪个会更好。我被告知它可以在 python 和 java 标准库中找到，也许还有其他标准库。不过，您仍然可能不应该在循环内使用它 - 在循环内，最好使用 treap（以获得良好的平均速度）或红黑树（以获得低标准偏差速度）。

于 2012-07-30T17:10:15.753 回答
0

我认为线性解决方案 [O(n)] 是最好的解决方案，因为在 n 个数字的列表中，如果 n/2 个数字是反向排序的，如下例所示，我们将不得不反转 n/2 个数字，这会给出 O( n)。

即使在这种情况下，对于类似的序列，我认为在最坏的情况下插入排序将是 O (n^2) 而不是 O (n)。

示例：考虑一个具有以下分布的数组，我们尝试使用插入排序，

n/4 个已排序的数字 | n2 个逆序数 | n/4 个已排序的数字

对于 n/2 个反向排序的数字，排序复杂度将为 O(n^2)。

于 2012-08-04T02:45:41.700 回答