Ищете самый быстрый способ сортировки списка из 2000 элементов, состоящих из трех различных значений в C ++

Question

В основном программе будет предоставлен список элементов, и они должны быть отсортированы по трем различным «корзинам». Думайте об этом, как будто вы сортируете три цвета мрамора. Все предметы имеют тип char. спасибо за помощь.

Answer 1

Это на самом деле не классическая проблема «сортировки»… поскольку существует только фиксированное количество возможных значений, это известно как проблема разбиение , и существует эффективное решение для трехстороннего подхода.раздел, известный как голландский флаг сортировки , впервые предложенный Edsger Dijkstra.

Этот алгоритм работает в O ( n ) и требует только одного прохода по массиву.

Алгоритм также можно найти довольно тривиально, развивая инвариант цикла.

Answer 2

Другой вариант - два вызова на раздел :

vector<char> v(2000);
...
std::partition(
    std::partition(
        v.begin(),
        v.end(),
        function_to_match_first_value()),
    v3.end(),
    function_to_match_second_value());

Answer 3

Я думаю, что это идеально подходит для сортировки сегментов: в основном создайте список из 256 значений типа int и каждый раз, когда вы встречаете значение в вашем списке, увеличивайте счетчик для этого значения.Затем выполните итерации, чтобы привести их в порядок.Это O (n).

Answer 4

Вы смотрели на это?http://www.sorting -algorithms.com / с небольшим числом уникальных клавиш

Answer 5

std::sort.Затем O(n) ищет границы.