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]);
    }

对于每次迭代，我将数组 [i] 与数组 [计数器 [i]] 交换，因为计数器 [i] 确定数组 [i] 的索引，然后我还交换计数器中的值以确保计数器与它们的对应值保持在同一索引中。

出于某种原因，这没有正确实现排序，但我不明白为什么。

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

任何人都可以帮忙吗？

谢谢。

标签： c++algorithmsortingdata-structuresbig-o

Answer 1

由于教授给了你计数（顺便说一句，它甚至可以正确处理重复项），我同意你应该用它来完成额外的 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放在那里危险地不合适，而是马上修复它。

完整的代码，也在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;
  }
}