c++ - 有什么方法可以使这种排序算法具有线性时间复杂度？

Question

我正在我的数据结构和算法类中进行此作业分配，要求我制作一个随机数数组，一个计数器数组，并使用C++中的两个数组制作自己的排序算法。

计数器数组基本上将包含对数字数组进行排序时每个元素应该去的位置的索引，因此counters [i]的值将是对array [i]进行排序后的位置的索引。它使用此代码，并且由我们的教授给出:

for (int i = 1; i < arraySize; i++)
        for (int j = 0; j < i; j++)
        {
            if (array[i] < array[j])
                counters[j]++;

            else
                counters[i]++;
        }

我以为使用这两个数组，我们将能够设计一种排序算法，该算法的时间复杂度为O(n)，因此我尝试了一种实现此目的的方法，然后我想到了:

for (int i = 0; i < arraySize; i++)
    {
       int index = counters[i];
       swap(array[i], array[counters[i]]);
       swap(counters[i], counters[index]);
    }

对于每次迭代，我都将array [i]与array [counters [i]]交换，因为counters [i]确定了array [i]的索引，然后我还交换了计数器中的值以确保计数器保持与相应值相同的索引。

由于某种原因，这无法正确实现排序，但是我不明白为什么。

我正在考虑使用另一种排序算法，但我想先尝试一下，因为它将是O(n)。

有人可以帮忙吗？

谢谢。

Answer 1

由于教授给了您计数(btw甚至可以正确处理重复项)，因此我同意您应该使用它来完成附加O(n)的排序。

为此，请继续将array[i]中的内容交换到其所属位置，直到array[i]中包含其中的内容。然后才转到i+1。这样，您知道array[0..i]都包含那里的内容(因此，在所有内容中它都属于它)。

  for (int i = 0; i < arraySize; i++) {
    int belongs_at = counters[i];
    while (belongs_at != i) {
      swap(array[i], array[belongs_at]);
      swap(counters[i], counters[belongs_at]);
      belongs_at = counters[i];
    }
  }

这是O(n)，因为内部循环的每次迭代都将一个(或两个)更多的值放入其所属的位置，并且总体上您不能在其所属的位置上放入n个以上的值，因此总体上您不能拥有多于n个内循环迭代。

让我们以{20, 50, 60, 70, 10, 40, 30}为例，看看在for -loop每次迭代结束时数组的样子:

10 20 60 70 50 40 30   # The while-loop fixed the cycle 20->50->10
10 20 60 70 50 40 30   # 20 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # The while-loop fixed the cycle 60->40->70->30
10 20 30 40 50 60 70   # 40 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 50 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 60 was already where it belongs, so nothing happened
10 20 30 40 50 60 70   # 70 was already where it belongs, so nothing happened

让我们看一个您出错的示例:{1, 2, 3, 0}。首先，将1交换到它所属的位置:{2, 1, 3, 0}。这仍然使2不属于它!您希望它能在以后得到解决。但这永远不会发生，因为您随后将1与自身交换，然后将3与0交换，然后将3与自身交换。但是，如果在i=0处继续前进，直到array[i]包含其中的内容，那么您就不会危险地将2留在那儿，而是立即进行修复。

完整代码，也为at repl.it(产生上面的输出):

#include <iostream>
using namespace std;

int main() {

  // Sample array
  int arraySize = 7;
  int array[7] = {20, 50, 60, 70, 10, 40, 30};

  // Count
  int counters[7] = {};
  for (int i = 1; i < arraySize; i++)
    for (int j = 0; j < i; j++)
      if (array[i] < array[j])
        counters[j]++;
      else
        counters[i]++;

  // Sort
  for (int i = 0; i < arraySize; i++) {
    int belongs_at = counters[i];
    while (belongs_at != i) {
      swap(array[i], array[belongs_at]);
      swap(counters[i], counters[belongs_at]);
      belongs_at = counters[i];
    }

    // Show
    for (int i = 0; i < arraySize; i++)
      cout << array[i] << ' ';
    cout << endl;
  }
}