1

我正在尝试编写一个计数排序函数，但由于某种原因，它卡在了我的第一个 for 循环中。有人能告诉我我的逻辑有什么问题吗？我是 C++ 新手，所以请解释任何答案，以便我学习。提前致谢！

maxInt编辑：只有当我输入小于 130,000时，我才会遇到问题（弹出窗口说“CountSort.exe 已停止工作”） 。如果我输入任何高于它的数字，它就会很好。我要排序的数字列表来自我阅读的外部 .txt 文件。这些数字是：1 4 6 2 34 65 2 3 64 2 12 97 56 45 3 43 23 99 2

struct CalcMaxInt
{
    int maxInt;
    CalcMaxInt () : maxInt(0) {}
    void operator () (int i) { if (i > maxInt) maxInt = i; }
};

void countSort(vector<int> &numbers)
{
    CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());
    int maxInt = cmi.maxInt + 1;

    vector <int> temp1(maxInt);
    vector <int> temp2(maxInt);
    int min = 0;

  for (int i = 0; i < numbers.size(); i++)
  {
      temp2[numbers[i]] = temp2[numbers[i]] + 1;
  }

  for (int i = 1; i <= maxInt; i++)
  {
      temp2[i] = temp2[i] + temp2[i - 1];
  }

  for (int i = numbers.size() - 1; i >= 0; i--)
  {
      temp1[temp2[numbers[i]] - 1] = numbers[i];
      temp2[numbers[i]] = temp2[numbers[i]] -1;
  }

   for (int i =0;i<numbers.size();i++)
   {
       numbers[i]=temp1[i];
   }
   return;
}
4

1 回答 1

4

我没有寻找算法错误，但是应该调整临时向量的大小并初始化为0（这只是为了偏执，默认初始化程序int应该是0）。

vector<int> temp1(maxInt, 0);
vector<int> temp2(maxInt, 0);

修复后，该程序似乎在我的系统上运行，正确排序了一个反向排序的数组。但是，您应该使用更完整的测试用例集进行测试。

由于计数排序的工作方式，maxInt参数需要是一个至少比输入数组所保存的最大值大一倍的值。

您可以修改函数以通过向量来定位最大的向量。

struct CalcMaxInt {
    int maxInt;
    CalcMaxInt () : maxInt(0) {}
    void operator () (int i) { if (i > maxInt) maxInt = i; }
};

CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());
int maxInt = cmi.maxInt + 1;

然后，您不必将其传递进去。

您可能想要添加一些代码来打印您输入的内容，以便您确定它是您认为应该是的。

于 2012-06-13T00:44:59.630 回答