1

我正在编写一个计数排序函数，当我运行它时，会弹出一个窗口说“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;
}
4

3 回答 3

2

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

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

您必须修复 temp2 才能拥有 maxInt+1 元素或 i < maxInt 才能看不到错误。

于 2012-06-18T01:26:00.557 回答
1

你这样做的重点不就是：

 CalcMaxInt cmi = std::for_each(numbers.begin(), numbers.end(), CalcMaxInt());

获取最大元素？

我会将您的代码更改为以下内容。 

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

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

    // then the rest the same starting with the for loops
    // but with the fix that @kcm1700 mentioned to the for loop
}
于 2012-06-18T01:33:46.750 回答
0

不应该标注temp1尺寸numbers.size()+1吗？

于 2012-06-18T02:27:01.517 回答