c++ - 计数排序无限循环

我正在编写计数排序功能，运行该功能时，会弹出一个窗口，提示“filename.exe停止工作”。调试之后，它似乎陷入了第二个for循环中。真正令我困惑的是，如果我将maxInt设置为大于130000的任何数字，它将起作用，但是如果它的130000或更低的数字得到该错误消息。我用来排序的文件只有大约20个数字。

#include <iterator>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
using namespace std;

std::string file = "";
std::vector<int> numbers;

void CountingSort(vector<int> &numbers);

int main()
{
    std::cout << "Which file would you like to sort?\n";
    std::cin >> file;

    std::ifstream in(file.c_str());

    // Read all the ints from in:
    std::copy(std::istream_iterator<int>(in), std::istream_iterator<int>(),
            std::back_inserter(numbers));

    CountingSort(numbers);

    // Print the vector with tab separators:
    std::copy(numbers.begin(), numbers.end(),
            std::ostream_iterator<int>(std::cout, "\t"));
    std::cout << std::endl;

    return 0;
}

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

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

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

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

最佳答案

您正在尝试访问超出适当范围的元素。
temp2的范围为[0 ... maxInt-1]，但以下代码使用的temp2 [maxInt]超出范围。

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

您必须将temp2修复为具有maxInt + 1元素，或者将i

关于c++ - 计数排序无限循环，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11076015/