Подсчет Сортировка застревает в цикле

Question

Я пытаюсь написать функцию сортировки подсчета, но по какой-то причине она застревает внутри моего первого цикла. Может ли кто-нибудь сказать мне, что не так с моей логикой? Я новичок в C++, поэтому, пожалуйста, объясните любые ответы, чтобы я мог учиться. Заранее спасибо!

EDIT: У меня возникла проблема (всплывающее окно с надписью «CountSort.exe перестало работать») только при вводе maxInt менее 130 000. Если я ввешу любое число выше, чем это, он отлично работает. Список номеров, которые я хочу сортировать, - это внешний файл .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; 
} 

Answer 1

Я не искал алгоритмические ошибки, но временные векторы должны иметь размеры, и инициализируются до 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; 

Тогда вам не придется пройти его.

Вы можете добавить некоторый код, чтобы распечатать то, что вы читаете в для ввода, так что вы уверены, что это то, что вы подумайте, что это должно быть.