问整数个数固定的排序向量

EN

vector<int> v;
// fill v with values
unordered_set<int> s(begin(v), end(v));
vector<int> sorted_v(begin(s), end(s));
sort(begin(sorted_v), end(sorted_v));
unordered_multiset<int> v_count(begin(v), end(v));
for (size_t i = 0; i < sorted_v.size(); ++i)
    cout << "For the " << i << "th value == " << sorted_v[i] << " there are " << v_count.count(v[i]) << " of them." << endl;

void sort(std::vector<int>& v)
{
    double start = std::clock();
    int* table = new int[MAX];
    for (int i = 0; i < MAX; ++i)
    {
        table[i] = 0;
    }
    for (int i = 0; i < size; ++i)
    {
        ++table[v[i]];
    }
    int cur = 0;
    for (int i = 0; i < MAX; ++i)
    {
        for (int j = 0; j < table[i]; ++j)
        {
            v[cur++] = i;
        }
    }
    delete[] table;
    std::cout << "count sort over char array took " << (std::clock() - start) / CLOCKS_PER_SEC << " s" << std::endl;
}

void sort6(int* v, int size)
{
    double start = std::clock();
    int* table = new int[MAX];
    for (int i = 0; i < MAX; ++i)
    {
        table[i] = 0;
    }
    int* end = v + size;
    for (int* vi = v; vi < end; ++vi)
    {
        ++table[*vi];
    }
    int* cur = v;
    for (int i = 0; i < MAX; ++i)
    {
        int count = table[i];
        for (int j = 0; j < count; ++j)
        {
            *(cur++) = i;
        }
    }
    std::cout << "count sort with pointers over char array took " << (std::clock() - start) / CLOCKS_PER_SEC << " s" << std::endl;
    delete[] v;
    delete[] table;
}

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstdint>

void special_sort(std::vector<int>& v, const size_t nExpectedMaxDifferentValues)
{
    typedef int_fast32_t Value;
    typedef size_t Count;
    static_assert(sizeof(Value) >= sizeof(int), "please define Value to int on this platform");

    struct ValHash
    {
        inline std::size_t operator()(const Value k) const
        {
            return k;
        }
    };

    std::unordered_map<Value, Count, ValHash> counts;

    counts.reserve(nExpectedMaxDifferentValues * 100);
    for (const auto x : v)
        ++counts[x];

    std::vector<Value> sorted_numbers;
    sorted_numbers.reserve(counts.size());
    for (const auto& p : counts)
        sorted_numbers.push_back(p.first);

    std::sort(std::begin(sorted_numbers), std::end(sorted_numbers));

    // fill vector with sorted data:
    int* p = v.data();
    for (const auto x : sorted_numbers)
    {
        for (Count i = counts[x]; i > 0; --i)
        {
            *p++ = x;
        }
    }
}

#include <random>
#include <limits>
#include <time.h>
#include <iostream>

int main()
{
    std::cout << "Initialize..." << std::endl;
    const size_t N = 100000000;
    const size_t M = 101;

    std::mt19937 gen(5); // use constant to easily reproduce the test
    std::uniform_int_distribution<int> disInt(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
    std::vector<int> v1;
    v1.reserve(M);

    for (size_t i = 0; i < M; ++i)
        v1.push_back(disInt(gen));

    std::uniform_int_distribution<size_t> disIndex(0, M-1);
    std::vector<int> v2;
    v2.reserve(N);

    for (size_t i = 0; i < N; ++i)
        v2.push_back(v1[disIndex(gen)]);

    std::cout << "Sort..." << std::endl;
    const clock_t begin_time = clock();

    special_sort(v2, M);

    const double seconds = double(clock() - begin_time) / CLOCKS_PER_SEC;
    std::cout << "Sorting took " << int(seconds * 1000) << " ms" << std::endl;
    return 0;
}

Initialize...
Sort...
Sorting took 374 ms