algorithm - 交换后的排序检查

Question

所以我有一个任务有问题。

您已经给出了数字序列和 n 个操作，每个操作有两个数字(此给定序列中的索引)。

您必须检查每个操作后的序列是否排序。 (应用每个操作)。

我的问题是我的解决方案太慢了。它在 O(n^2) 中起作用。 (我只是进行交换并使用 c++11 中的 is_sorted)。如何让它更快？

提前致谢

Answer 1

我认为你的意思是你有一个序列，比如说...

3, 9, 34, 8, 5, 25, 10

还有一个交换两个数字的操作，所以 swap[2, 4](当然是零索引)会产生

3, 9, 5, 8, 34, 25, 10

即使操作不交换，而是执行一些仅作用于这两个数字的其他操作，该算法仍然有效；事实上，这将适用于更改该数组中任何数字的任何内容:

首先，我会保留一个 bool 值辅助数组，它告诉我序列中的每个成员是否大于它前面的数字，表明这个数字相对于它前面的数字是否就位或按顺序排列。然后，我还会计算这些 bool 值中有多少是真的。当适当的数字计数等于序列中的项目数时，序列被排序。当对序列中的任何数字进行更改时，我会使用以下算法进行检查:

float MySequence[LengthOfSequence];
bool IsNumInPlace[LengthOfSequence];
int CountOfNumsInPlace;

... something loads MySequence ...

// this starts that helper array of booleans
IsNumInPlace[0] = true;
CountOfNumsInPlace = 1;
for (i = 1; i < LengthOfSequence; i++) {
   IsNumInPlace[i] = (MySequence[i] > MySequence[i-1]);
   if (IsNumInPlace[i]) CountOfNumsInPlace++;
}


... something changes item at index "x" in the sequence ...
// whether this number, and possibly the one after it, are in place, needs
// to be rechecked
CheckThisItem(x);
if (x < LengthOfSequence - 1) CheckThisItem(x + 1);

... the array is sorted, at this point, if CountOfNumsInPlace is equal to the number of items in the array ...

关键在于这个小函数，它根据给定索引处的值是否大于或等于它之前的项目的值来增加或减少“就地项目”的数量。

private void CheckThisItem(int ItemChanged) {
    bool IsNewNumInPlace= (ItemChanged == 0) ||
                          (MySequence[ItemChanged] >= MySequence[ItemChanged - 1]);
    if (IsNumInPlace[ItemChanged] && !IsNewNumInPlace) {
        CountOfNumsInPlace--;
    } else if (!IsNumInPlace[ItemChanged] && IsNewNumInPlace) {
        CountOfNumsInPlace++;
    }
    IsNumInPlace[ItemChanged] = IsNewNumInPlace;
}

这应该会为您提供一个 O(n) 的算法。您不会将数组中的每个项目与其周围的项目进行重新比较，以查看该数组是否按顺序排列，即使是那些没有受到影响的项目。您只是将更改的项目与它之前的项目和之后的项目进行比较。

请注意，数组中的第一项相对于它之前的项被认为是“就位”的。因为它前面没有项目(它是第一个)，所以没有什么不合适的，所以就排序而言它是“好的”。

如果您的操作对序列中的两个项目进行了更改，那么只需将最后一部分执行两次，每个更改的数字一次。