logo标签列表

对整数数组进行字典序排序 C++

c++arrayssortinglexicographic
18

我希望对一个包含大量整数（比如1百万个）的数组进行字典序排序。

例如：

input [] = { 100, 21 , 22 , 99 , 1  , 927 }
sorted[] = { 1  , 100, 21 , 22 , 927, 99  }

我使用了最简单的方法：

  • 将所有数字转换为字符串（非常耗费内存）
  • 使用 std:sort 和 strcmp 作为比较函数
  • 将字符串转换回整数

有比这更好的方法吗？

你是如何进行转换的？ - Eamonn McEvoy
整数可以有多大？ - Eric Postpischil
12个回答
16
使用适当的比较函数和std::sort()，可以减少内存需求。
比较函数可使用n % 10、n / 10 % 10、n / 100 % 10等来访问各个数字（正整数为例；负整数略有不同）。
你的意思是使用 n%10 等方法而不是将其转换为字符串吗？ - Aseem Goyal
1
是的。而不是事先准备数组（例如转换为字符串），在比较函数中按需进行计算。 - Oswald
8

如果要提供任何自定义排序顺序，您可以向std::sort提供比较器。在这种情况下，它将会有些复杂，使用对数来检查以10为底的数字的各个位。

以下是一个示例 - 内联注释描述了正在发生的事情。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>

int main() {
    int input[] { 100, 21, 22, 99, 1, 927, -50, -24, -160 };

    /**
     * Sorts the array lexicographically.
     * 
     * The trick is that we have to compare digits left-to-right
     * (considering typical Latin decimal notation) and that each of
     * two numbers to compare may have a different number of digits.
     * 
     * This is very efficient in storage space, but inefficient in
     * execution time; an approach that pre-visits each element and
     * stores a translated representation will at least double your
     * storage requirements (possibly a problem with large inputs)
     * but require only a single translation of each element.
     */
    std::sort(
        std::begin(input),
        std::end(input),
        [](int lhs, int rhs) -> bool {
            // Returns true if lhs < rhs
            // Returns false otherwise
            const auto BASE      = 10;
            const bool LHS_FIRST = true;
            const bool RHS_FIRST = false;
            const bool EQUAL     = false;


            // There's no point in doing anything at all
            // if both inputs are the same; strict-weak
            // ordering requires that we return `false`
            // in this case.
            if (lhs == rhs) {
                return EQUAL;
            }

            // Compensate for sign
            if (lhs < 0 && rhs < 0) {
                // When both are negative, sign on its own yields
                // no clear ordering between the two arguments.
                // 
                // Remove the sign and continue as for positive
                // numbers.
                lhs *= -1;
                rhs *= -1;
            }
            else if (lhs < 0) {
                // When the LHS is negative but the RHS is not,
                // consider the LHS "first" always as we wish to
                // prioritise the leading '-'.
                return LHS_FIRST;
            }
            else if (rhs < 0) {
                // When the RHS is negative but the LHS is not,
                // consider the RHS "first" always as we wish to
                // prioritise the leading '-'.
                return RHS_FIRST;
            }

            // Counting the number of digits in both the LHS and RHS
            // arguments is *almost* trivial.
            const auto lhs_digits = (
                lhs == 0
                ? 1
                : std::ceil(std::log(lhs+1)/std::log(BASE))
            );

            const auto rhs_digits = (
                rhs == 0
                ? 1
                : std::ceil(std::log(rhs+1)/std::log(BASE))
            );

            // Now we loop through the positions, left-to-right,
            // calculating the digit at these positions for each
            // input, and comparing them numerically. The
            // lexicographic nature of the sorting comes from the
            // fact that we are doing this per-digit comparison
            // rather than considering the input value as a whole.
            const auto max_pos = std::max(lhs_digits, rhs_digits);
            for (auto pos = 0; pos < max_pos; pos++) {
                if (lhs_digits - pos == 0) {
                    // Ran out of digits on the LHS;
                    // prioritise the shorter input
                    return LHS_FIRST;
                }
                else if (rhs_digits - pos == 0) {
                    // Ran out of digits on the RHS;
                    // prioritise the shorter input
                    return RHS_FIRST;
                }
                else {
                    const auto lhs_x = (lhs / static_cast<decltype(BASE)>(std::pow(BASE, lhs_digits - 1 - pos))) % BASE;
                    const auto rhs_x = (rhs / static_cast<decltype(BASE)>(std::pow(BASE, rhs_digits - 1 - pos))) % BASE;

                    if (lhs_x < rhs_x)
                        return LHS_FIRST;
                    else if (rhs_x < lhs_x)
                        return RHS_FIRST;
                }
            }

            // If we reached the end and everything still
            // matches up, then something probably went wrong
            // as I'd have expected to catch this in the tests
            // for equality.
            assert("Unknown case encountered");
        }
    );

    std::cout << '{';
    for (auto x : input)
        std::cout << x << ", ";
    std::cout << '}';

    // Output: {-160, -24, -50, 1, 100, 21, 22, 927, 99, }
}

示例

有更快的方法来计算一个数中的数字个数, 但以上内容将帮助你入门。

不需要计算数字。对于正整数，如果您拥有所需基数的对数，则具有较低尾数（对数的小数部分）的数字在字典顺序中较早。如果尾数相等，则整数部分较低的数字会先出现。问题是获取对数；您需要检测当真实尾数相等时，即使浮点尾数略有偏差也可以进行更改。这可以更改为测试差异是否在库对数例程的误差范围内，直到整数... - Eric Postpischil
变得如此庞大，以至于连续两个整数的尾数之差与库例程中的误差一样大。(任何熟悉对数表或滑尺计算器的人都知道这一点。)请注意，尾数可能存在的误差必须考虑到对数的大小所强制的误差，而不仅仅是库例程中固有的误差。 - Eric Postpischil
2
@Eric：谢谢。是的，为了这个有些牵强附会的演示，我选择了额外的整数DIV、POW和MOD，而不是引入浮点数的麻烦。 - Lightness Races in Orbit
1
但是你确实有浮点数的问题。std::ceil(std::log(lhs+1)/std::log(BASE)) 可能会偏移一个单位。 - Eric Postpischil
6
这是另一种算法，在排序之前做了一些计算。尽管有额外的复制（见比较），但它似乎相当快。
注意：
  • 仅支持正整数。
  • 仅支持小于std::numeric_limits<int> ::max()/10的整数。
注：您可以优化count_digits和my_pow10，例如请参见Andrei Alexandrescu的C++三个优化技巧和在C ++中计算整数幂的任何方式是否比pow（）更快？ 助手：
#include <random>
#include <vector>
#include <utility>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <limits>
#include <iterator>

// non-optimized version
int count_digits(int p) // returns `0` for `p == 0`
{
    int res = 0;
    for(; p != 0; ++res)
    {
        p /= 10;
    }
    return res;
}

// non-optimized version
int my_pow10(unsigned exp)
{
    int res = 1;
    for(; exp != 0; --exp)
    {
        res *= 10;
    }
    return res;
}

算法（注意-不是原地算法）：

// helper to provide integers with the same number of digits
template<class T, class U>
std::pair<T, T> lexicographic_pair_helper(T const p, U const maxDigits)
{
    auto const digits = count_digits(p);
    // append zeros so that `l` has `maxDigits` digits
    auto const l = static_cast<T>( p  * my_pow10(maxDigits-digits) );
    return {l, p};
}

template<class RaIt>
using pair_vec
    = std::vector<std::pair<typename std::iterator_traits<RaIt>::value_type,
                            typename std::iterator_traits<RaIt>::value_type>>;

template<class RaIt>
pair_vec<RaIt> lexicographic_sort(RaIt p_beg, RaIt p_end)
{
    if(p_beg == p_end) return {};

    auto max = *std::max_element(p_beg, p_end);
    auto maxDigits = count_digits(max);

    pair_vec<RaIt> result;
    result.reserve( std::distance(p_beg, p_end) );

    for(auto i = p_beg; i != p_end; ++i)
        result.push_back( lexicographic_pair_helper(*i, maxDigits) );

    using value_type = typename pair_vec<RaIt>::value_type;

    std::sort(begin(result), end(result),
              [](value_type const& l, value_type const& r)
              {
                  if(l.first < r.first) return true;
                  if(l.first > r.first) return false;
                  return l.second < r.second; }
             );

    return result;
}

使用示例：

int main()
{
    std::vector<int> input = { 100, 21 , 22 , 99 , 1  , 927 };
    // generate some numbers
    /*{
        constexpr int number_of_elements = 1E6;
        std::random_device rd;
        std::mt19937 gen( rd() );
        std::uniform_int_distribution<>
            dist(0, std::numeric_limits<int>::max()/10);
        for(int i = 0; i < number_of_elements; ++i)
            input.push_back( dist(gen) );
    }*/

    std::cout << "unsorted: ";
    for(auto const& e : input) std::cout << e << ", ";
    std::cout << "\n\n";


    auto sorted = lexicographic_sort(begin(input), end(input));

    std::cout << "sorted: ";
    for(auto const& e : sorted) std::cout << e.second << ", ";
    std::cout << "\n\n";
}
由于你的解决方案缺少注释（你被解雇了），我仍在努力理解它；你基本上是对每个输入进行了零填充吗？ - Lightness Races in Orbit
@LightnessRacesinOrbit 我将每个整数乘以10，直到它们都有相同的位数，然后使用结果进行比较。（是的，补零。） - dyp
你的程序速度更快，明显优先考虑速度而不是空间（特别是仅转换每个元素一次），而我的程序则相反。值得注意的是，我不得不删除输出并将迭代次数减少到1e5才能在Coliru运行之前超时；两者在1e4输入下都可以在不到一秒的时间内运行，但是我的程序在1e5输入下达到了2.6秒，而你的程序仍然只有0.04秒；这当然体现了你工作循环的线性复杂性。我对你的解决方案点赞！ - Lightness Races in Orbit
1
当其中一个数字接近最大整数值时，这会存在问题。例如，使用32位int比较1,000,000,000和3时，3将被乘以1,000,000,000，从而导致溢出。此外，应考虑到log10可能返回稍微不准确的结果。 - Eric Postpischil
@EricPostpischil 是的，它也无法处理负数。应该在答案中加入这一点，现在会加上。 - dyp
显示剩余6条评论
6
这是一个社区维基，用于比较解决方案。我采用了nim的代码并使其易于扩展。欢迎添加您的解决方案和输出。
在旧的缓慢计算机（3 GB RAM，Core2Duo U9400）上运行示例，使用g++4.9 @ -O3 -march=native：
元素数量：1e + 03 整数类型大小：4
参考解决方案：Lightness Races in Orbit
解决方案“dyp”： 持续时间：0毫秒和301微秒 与参考解决方案的比较：完全匹配 解决方案“Nim”： 持续时间：2毫秒和160微秒 与参考解决方案的比较：完全匹配 解决方案“nyarlathotep”： 持续时间：8毫秒和126微秒 与参考解决方案的比较：完全匹配 解决方案“notbad”： 持续时间：1毫秒和102微秒 与参考解决方案的比较：完全匹配 解决方案“Eric Postpischil”： 持续时间：2毫秒和550微秒 与参考解决方案的比较：完全匹配 解决方案“Lightness Races in Orbit”： 持续时间：17毫秒和469微秒 与参考解决方案的比较：完全匹配 解决方案“pts”： 持续时间：1毫秒和92微秒 与参考解决方案的比较：完全匹配
==========================================================
元素数量：1e + 04 整数类型大小：4
参考解决方案：Lightness Races in Orbit
解决方案“nyarlathotep”： 持续时间：109毫秒和712微秒 与参考解决方案的比较：完全匹配 解决方案“Lightness Races in Orbit”： 持续时间：272毫秒和819微秒 与参考解决方案的比较：完全匹配 解决方案“dyp”： 持续时间：1毫秒和748微秒 与参考解决方案的比较：完全匹配 解决方案“notbad”： 持续时间：16毫秒和115微秒 与参考解决方案的比较：完全匹配 解决方案“pts”： 持续时间：15毫秒和10微秒 与参考解决方案的比较：完全匹配 解决方案“Eric Postpischil”： 持续时间：33毫秒和301微秒 与参考解决方案的比较：完全匹配 解决方案“Nim”： 持续时间：17毫秒和83微秒 与参考解决方案的比较：完全匹配
==========================================================
元素数量：1e + 05 整数类型大小：4
参考解决方案：Lightness Races in Orbit
解决方案“Nim”： 持续时间：217毫秒和4微秒 与参考解决方案的比较：完全匹配 解决方案“pts”： 持续时间：199毫秒和505微秒 与参考解决方案的比较：完全匹配 解决方案“dyp”： 持续时间：20毫秒和330微秒 与参考解决方案的比较：完全匹配 解决方案“Eric Postpischil”： 持续时间：415毫秒和477微秒 与参考解决方案的比较：完全匹配 解决方案“Lightness Races in Orbit”： 持续
算法必须是带有函数调用运算符模板的结构体，支持以下接口：
template<class RaIt> operator()(RaIt begin, RaIt end);

输入数据的副本作为参数提供，期望算法在相同范围内提供结果（例如原地排序）。

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <random>
#include <vector>
#include <utility>
#include <cmath>
#include <cassert>
#include <chrono>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <iomanip>

using duration_t = decltype(  std::chrono::high_resolution_clock::now()
                            - std::chrono::high_resolution_clock::now());

template<class T>
struct result_t
{
    std::vector<T> numbers;
    duration_t duration;
    char const* name;
};

template<class RaIt, class F>
result_t<typename std::iterator_traits<RaIt>::value_type>
apply_algorithm(RaIt p_beg, RaIt p_end, F f, char const* name)
{
    using value_type = typename std::iterator_traits<RaIt>::value_type;

    std::vector<value_type> inplace(p_beg, p_end);

    auto start = std::chrono::high_resolution_clock::now();

    f(begin(inplace), end(inplace));

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = end - start;

    return {std::move(inplace), duration, name};
}

// non-optimized version
int count_digits(int p) // returns `0` for `p == 0`
{
        int res = 0;
        for(; p != 0; ++res)
        {
            p /= 10;
        }
        return res;
}

// non-optimized version
int my_pow10(unsigned exp)
{
        int res = 1;
        for(; exp != 0; --exp)
        {
            res *= 10;
        }
        return res;
}


// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// paste algorithms here
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


int main(int argc, char** argv)
{
    using integer_t = int;
    constexpr integer_t dist_min = 0;
    constexpr integer_t dist_max = std::numeric_limits<integer_t>::max()/10;
    constexpr std::size_t default_number_of_elements = 1E6;

    const std::size_t number_of_elements = argc>1 ? std::atoll(argv[1]) :
                                           default_number_of_elements;
    std::cout << "number of elements: ";
    std::cout << std::scientific << std::setprecision(0);
    std::cout << (double)number_of_elements << "\n";
    std::cout << /*std::defaultfloat <<*/ std::setprecision(6);
    std::cout.unsetf(std::ios_base::floatfield);

    std::cout << "size of integer type: " << sizeof(integer_t) << "\n\n";

    std::vector<integer_t> input;
    {
        input.reserve(number_of_elements);

        std::random_device rd;
        std::mt19937 gen( rd() );
        std::uniform_int_distribution<> dist(dist_min, dist_max);

        for(std::size_t i = 0; i < number_of_elements; ++i)
            input.push_back( dist(gen) );
    }

    auto b = begin(input);
    auto e = end(input);

    using res_t = result_t<integer_t>;
    std::vector< std::function<res_t()> > algorithms;

    #define MAKE_BINDER(B, E, ALGO, NAME) \
        std::bind( &apply_algorithm<decltype(B),decltype(ALGO)>, \
                   B,E,ALGO,NAME )
    constexpr auto lightness_name = "Lightness Races in Orbit";
    algorithms.push_back( MAKE_BINDER(b, e, lightness(), lightness_name) );
    algorithms.push_back( MAKE_BINDER(b, e, dyp(), "dyp") );
    algorithms.push_back( MAKE_BINDER(b, e, nim(), "Nim") );
    algorithms.push_back( MAKE_BINDER(b, e, pts(), "pts") );
    algorithms.push_back( MAKE_BINDER(b, e, epost(), "Eric Postpischil") );
    algorithms.push_back( MAKE_BINDER(b, e, nyar(), "nyarlathotep") );
    algorithms.push_back( MAKE_BINDER(b, e, notbad(), "notbad") );

    {
        std::srand( std::random_device()() );
        std::random_shuffle(begin(algorithms), end(algorithms));
    }

    std::vector< result_t<integer_t> > res;
    for(auto& algo : algorithms)
        res.push_back( algo() );

    auto reference_solution
        = *std::find_if(begin(res), end(res),
                        [](result_t<integer_t> const& p)
                        { return 0 == std::strcmp(lightness_name, p.name); });
    std::cout << "reference solution: "<<reference_solution.name<<"\n\n";

    for(auto const& e : res)
    {
        std::cout << "solution \""<<e.name<<"\":\n";
        auto ms =
            std::chrono::duration_cast<std::chrono::microseconds>(e.duration);
        std::cout << "\tduration: "<<ms.count()/1000<<" ms and "
                                   <<ms.count()%1000<<" microseconds\n";

        std::cout << "\tcomparison to reference solution: ";
        if(e.numbers.size() != reference_solution.numbers.size())
        {
            std::cout << "ouput count mismatch\n";
            break;
        }

        auto mismatch = std::mismatch(begin(e.numbers), end(e.numbers),
                                      begin(reference_solution.numbers)).first;
        if(end(e.numbers) == mismatch)
        {
            std::cout << "exact match\n";
        }else
        {
            std::cout << "mismatch found\n";
        }
    }
}

当前的算法；请注意，我已经用全局函数替换了数字计数器和10的幂，这样如果有人优化，我们都会受益。

struct lightness
{
    template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        using T = typename std::iterator_traits<RaIt>::value_type;

        /**
         * Sorts the array lexicographically.
         *
         * The trick is that we have to compare digits left-to-right
         * (considering typical Latin decimal notation) and that each of
         * two numbers to compare may have a different number of digits.
         *
         * This is very efficient in storage space, but inefficient in
         * execution time; an approach that pre-visits each element and
         * stores a translated representation will at least double your
         * storage requirements (possibly a problem with large inputs)
         * but require only a single translation of each element.
         */
        std::sort(
            b,
            e,
            [](T lhs, T rhs) -> bool {
                // Returns true if lhs < rhs
                // Returns false otherwise
                const auto BASE      = 10;
                const bool LHS_FIRST = true;
                const bool RHS_FIRST = false;
                const bool EQUAL     = false;


                // There's no point in doing anything at all
                // if both inputs are the same; strict-weak
                // ordering requires that we return `false`
                // in this case.
                if (lhs == rhs) {
                    return EQUAL;
                }

                // Compensate for sign
                if (lhs < 0 && rhs < 0) {
                    // When both are negative, sign on its own yields
                    // no clear ordering between the two arguments.
                    //
                    // Remove the sign and continue as for positive
                    // numbers.
                    lhs *= -1;
                    rhs *= -1;
                }
                else if (lhs < 0) {
                    // When the LHS is negative but the RHS is not,
                    // consider the LHS "first" always as we wish to
                    // prioritise the leading '-'.
                    return LHS_FIRST;
                }
                else if (rhs < 0) {
                    // When the RHS is negative but the LHS is not,
                    // consider the RHS "first" always as we wish to
                    // prioritise the leading '-'.
                    return RHS_FIRST;
                }

                // Counting the number of digits in both the LHS and RHS
                // arguments is *almost* trivial.
                const auto lhs_digits = (
                    lhs == 0
                    ? 1
                    : std::ceil(std::log(lhs+1)/std::log(BASE))
                );

                const auto rhs_digits = (
                    rhs == 0
                    ? 1
                    : std::ceil(std::log(rhs+1)/std::log(BASE))
                );

                // Now we loop through the positions, left-to-right,
                // calculating the digit at these positions for each
                // input, and comparing them numerically. The
                // lexicographic nature of the sorting comes from the
                // fact that we are doing this per-digit comparison
                // rather than considering the input value as a whole.
                const auto max_pos = std::max(lhs_digits, rhs_digits);
                for (auto pos = 0; pos < max_pos; pos++) {
                    if (lhs_digits - pos == 0) {
                        // Ran out of digits on the LHS;
                        // prioritise the shorter input
                        return LHS_FIRST;
                    }
                    else if (rhs_digits - pos == 0) {
                        // Ran out of digits on the RHS;
                        // prioritise the shorter input
                        return RHS_FIRST;
                    }
                    else {
                        const auto lhs_x = (lhs / static_cast<decltype(BASE)>(std::pow(BASE, lhs_digits - 1 - pos))) % BASE;
                        const auto rhs_x = (rhs / static_cast<decltype(BASE)>(std::pow(BASE, rhs_digits - 1 - pos))) % BASE;

                        if (lhs_x < rhs_x)
                            return LHS_FIRST;
                        else if (rhs_x < lhs_x)
                            return RHS_FIRST;
                    }
                }

                // If we reached the end and everything still
                // matches up, then something probably went wrong
                // as I'd have expected to catch this in the tests
                // for equality.
                assert("Unknown case encountered");

                // dyp: suppress warning and throw
                throw "up";
            }
        );
    }
};

namespace ndyp
{
    // helper to provide integers with the same number of digits
    template<class T, class U>
    std::pair<T, T> lexicographic_pair_helper(T const p, U const maxDigits)
    {
        auto const digits = count_digits(p);
        // append zeros so that `l` has `maxDigits` digits
        auto const l = static_cast<T>( p  * my_pow10(maxDigits-digits) );
        return {l, p};
    }

    template<class RaIt>
    using pair_vec
        = std::vector<std::pair<typename std::iterator_traits<RaIt>::value_type,
                                typename std::iterator_traits<RaIt>::value_type>>;

    template<class RaIt>
    pair_vec<RaIt> lexicographic_sort(RaIt p_beg, RaIt p_end)
    {
        if(p_beg == p_end) return pair_vec<RaIt>{};

        auto max = *std::max_element(p_beg, p_end);
        auto maxDigits = count_digits(max);

        pair_vec<RaIt> result;
        result.reserve( std::distance(p_beg, p_end) );

        for(auto i = p_beg; i != p_end; ++i)
            result.push_back( lexicographic_pair_helper(*i, maxDigits) );

        using value_type = typename pair_vec<RaIt>::value_type;

        std::sort(begin(result), end(result),
                  [](value_type const& l, value_type const& r)
                  {
                      if(l.first < r.first) return true;
                      if(l.first > r.first) return false;
                      return l.second < r.second; }
                 );

        return result;
    }
}

struct dyp
{
    template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        auto pairvec = ndyp::lexicographic_sort(b, e);
        std::transform(begin(pairvec), end(pairvec), b,
                       [](typename decltype(pairvec)::value_type const& e) { return e.second; });
    }
};


namespace nnim
{
    bool comp(int l, int r)
    {
      int lv[10] = {}; // probably possible to get this from numeric_limits
      int rv[10] = {};

      int lc = 10; // ditto
      int rc = 10;
      while (l || r)
      {
        if (l)
        {
          auto t = l / 10;
          lv[--lc] = l - (t * 10);
          l = t;
        }
        if (r)
        {
          auto t = r / 10;
          rv[--rc] = r - (t * 10);
          r = t;
        }
      }
      while (lc < 10 && rc < 10)
      {
        if (lv[lc] == rv[rc])
        {
          lc++;
          rc++;
        }
        else
          return lv[lc] < rv[rc];
      }
      return lc > rc;
    }
}

struct nim
{
    template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        std::sort(b, e, nnim::comp);
    }
};

struct pts
{
        template<class T> static bool lex_less(T a, T b) {
          unsigned la = 1, lb = 1;
          for (T t = a; t > 9; t /= 10) ++la;
          for (T t = b; t > 9; t /= 10) ++lb;
          const bool ll = la < lb;
          while (la > lb) { b *= 10; ++lb; }
          while (lb > la) { a *= 10; ++la; }
          return a == b ? ll : a < b;
        }

        template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        std::sort(b, e, lex_less<typename std::iterator_traits<RaIt>::value_type>);
    }
};

struct epost
{
        static bool compare(int x, int y)
        {
                static const double limit = .5 * (log(INT_MAX) - log(INT_MAX-1));

                double lx = log10(x);
                double ly = log10(y);
                double fx = lx - floor(lx);  // Get the mantissa of lx.
                double fy = ly - floor(ly);  // Get the mantissa of ly.
                return fabs(fx - fy) < limit ? lx < ly : fx < fy;
        }

        template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        std::sort(b, e, compare);
    }
};

struct nyar
{
        static bool lexiSmaller(int i1, int i2)
        {
            int digits1 = count_digits(i1);
            int digits2 = count_digits(i2);

            double val1 = i1/pow(10.0, digits1-1);
            double val2 = i2/pow(10.0, digits2-1);

            while (digits1 > 0 && digits2 > 0 && (int)val1 == (int)val2)
            {
                digits1--;
                digits2--;
                val1 = (val1 - (int)val1)*10;
                val2 = (val2 - (int)val2)*10;
            }
            if (digits1 > 0 && digits2 > 0)
            {
                return (int)val1 < (int)val2;
            }
            return (digits2 > 0);
        }

        template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        std::sort(b, e, lexiSmaller);
    }
};

struct notbad
{
        static int up_10pow(int n) {
          int ans = 1;
          while (ans < n) ans *= 10;
          return ans;
        }

        static bool compare(int v1, int v2) {
           int ceil1 = up_10pow(v1), ceil2 = up_10pow(v2);
           while ( ceil1 != 0 && ceil2 != 0) {
              if (v1 / ceil1  < v2 / ceil2) return true;
              else if (v1 / ceil1 > v2 / ceil2) return false;
              ceil1 /= 10;
              ceil2 /= 10;
           }
           if (v1 < v2) return true;
           return false;
        }

        template<class RaIt> void operator()(RaIt b, RaIt e)
    {
        std::sort(b, e, compare);
    }
};
4

我认为以下代码可以作为正整数的排序比较函数，前提是所使用的整数类型远窄于double类型（例如32位的int和64位的double），并且使用的log10程序在精确计算10的幂次时返回完全正确的结果（好的实现会这样做）：

static const double limit = .5 * (log(INT_MAX) - log(INT_MAX-1));

double lx = log10(x);
double ly = log10(y);
double fx = lx - floor(lx);  // Get the mantissa of lx.
double fy = ly - floor(ly);  // Get the mantissa of ly.
return fabs(fx - fy) < limit ? lx < ly : fx < fy;

它通过比较对数的尾数来工作。尾数是对数的小数部分，它们表示一个数字的有效数字的值而无需考虑大小（例如，31、3.1和310的对数具有完全相同的尾数）。 fabs(fx - fy) < limit 的目的是允许在取对数时存在误差，这既是因为 log10 的实现不完美，也是因为浮点格式强制产生一些误差。（31和310的对数的整数部分使用不同数量的位，因此留给有效数字的位数不同，因此它们最终会被舍入到略微不同的值。）只要整数类型明显窄于 double 类型，则计算的 limit 将大得多 与log10中的误差。因此，测试 fabs(fx - fy) < limit 基本上告诉我们，如果精确计算，两个计算的尾数是否相等。
如果尾数不同，则它们表示字典顺序，因此我们返回 fx < fy。如果它们相等，则对数的整数部分告诉我们顺序，因此我们返回 lx < ly。
测试 log10 是否为每个十的幂返回正确结果非常简单，因为这些幂非常少。如果没有，可以轻松进行调整：if (1-fx < limit) fx = 0; if (1-fu < limit) fy = 0;。这允许 log10 在应返回5时返回4.99999等情况的发生。
这种方法的优点是不使用循环或除法（在许多处理器上需要花费时间）。
+1: 对于10万个输入只需0.4秒; 这已经很不错了！我并不是过分追求速度，只是想指出这一点。综合考虑，这看起来是我所需要的答案。 - Lightness Races in Orbit
3
如果您的所有数字都是非负数，并且它们足够小，使得将它们乘以10不会导致溢出，那么这是一种紧凑的解决方案：
template<class T> bool lex_less(T a, T b) {
  unsigned la = 1, lb = 1;
  for (T t = a; t > 9; t /= 10) ++la;
  for (T t = b; t > 9; t /= 10) ++lb;
  const bool ll = la < lb;
  while (la > lb) { b *= 10; ++lb; }
  while (lb > la) { a *= 10; ++la; }
  return a == b ? ll : a < b;
}

按照以下方式运行:

#include <iostream>
#include <algorithm>
int main(int, char **) {
  unsigned short input[] = { 100, 21 , 22 , 99 , 1  , 927 };
  unsigned input_size = sizeof(input) / sizeof(input[0]);
  std::sort(input, input + input_size, lex_less<unsigned short>);
  for (unsigned i = 0; i < input_size; ++i) {
    std::cout << ' ' << input[i];
  }
  std::cout << std::endl;
  return 0;
}
3
这项任务似乎非常适合使用加填充的MSD变体基数排序（http://en.wikipedia.org/wiki/Radix_sort）进行处理。
具体要看你愿意投入多少代码。简单代码的时间复杂度是O(log n)，而完全优化的基数排序则是O(kn)。
1
你可以尝试使用 % 运算符来访问每个单独的数字，例如 121 % 100 将给你第一个数字，但你必须找到一种方法来解决它们大小不同的问题。
因此，请查找数组中的最大值。我不知道是否有内置的函数可以实现这一点，你可以尝试一下。
int Max (int* pdata,int size)
 {
int temp_max =0 ;

for (int i =0 ; i < size ; i++)
 {
    if (*(pdata+i) > temp_max)
    {
        temp_max = *(pdata+i);

    }
 }
 return temp_max;
 }

这个函数将返回数字中的位数。
 int Digit_checker(int n)
{
 int num_digits = 1;

while (true)
{
    if ((n % 10) == n)
        return num_digits;
    num_digits++;
    n = n/10;
}
return num_digits;
}

假设最大数字的位数为n。 接下来以以下格式打开一个for循环： for (int i = 1; i < n ; i++)

然后，您可以通过“data[i] % (10^(n-i))”来访问第一个数字，然后进行排序，然后在下一次迭代中，您将访问第二个数字。不过我不知道您将如何对它们进行排序。

它不适用于负数，并且您需要解决“data[i] % (10^(n-i))”对于比最大值位数少的数字返回自身的问题。

"121 / 100" 和 "121 - 121 % 100" 将会给出第一个数字的访问权限。 - Oswald
@Oswald 仅适用于正整数。 - Matthew Mcveigh
@MatthewMcveigh 哎呀，我像百万次一样掉进了这个陷阱。我真的希望现在我已经免疫了。 - Oswald
1

重载 < 运算符以按字典顺序比较两个整数。对于每个整数，找到不小于给定整数的最小的10^k。然后逐位比较数字。

class CmpIntLex {
int up_10pow(int n) {
  int ans = 1;
  while (ans < n) ans *= 10;
  return ans;
}
public: 
bool operator ()(int v1, int v2) {
   int ceil1 = up_10pow(v1), ceil2 = up_10pow(v2);
   while ( ceil1 != 0 && ceil2 != 0) {
      if (v1 / ceil1  < v2 / ceil2) return true;
      else if (v1 / ceil1 > v2 / ceil2) return false;
      ceil1 /= 10; 
      ceil2 /= 10;
   }
   if (v1 < v2) return true;
   return false;
}
int main() {
vector<int> vi = {12,45,12134,85};
sort(vi.begin(), vi.end(), CmpIntLex());
}
如果你要在全局或文件范围内引入一个执行字典序比较的函数 bool(int, int)，我建议使用比 less 更具体的名称。 :P - Lightness Races in Orbit
1
这是一个不错、简明的解决方案，尽管我觉得它可能需要一些注释和一些const，更不用说一些更好的变量名了。 - Lightness Races in Orbit
我无法在与LRO的解决方案相同的数据集上使您的代码正常工作...（基本上，我复制了DyP的解决方案中的代码，并且没有使用ifdef，每个解决方案都获得了相同随机输入向量的副本），但是您的解决方案似乎无法正常工作（也就是说，它似乎一直在旋转...） - Nim
@Nim 修复了一个错误并进行了更新。同时，它只处理所有整数均为正数的情况。 - notbad
@DyP 是的，我很抱歉 :) - notbad
1
好的，现在可以工作了（并且得到正确的结果）；我的测量数据中启用了解决方案。 - dyp
0

虽然这里的某些其他答案（Lightness's，notbad's）已经展示了相当不错的代码，但我相信我可以添加一种更高效的解决方案（因为它在每个循环中都不需要除法或幂运算; 但它需要浮点数运算，可能会使它变慢，并且对于大数可能不准确）：

#include <algorithm>
#include <iostream>
#include <assert.h>

// method taken from https://dev59.com/zXI_5IYBdhLWcg3wMf5_#1489873
template <class T>
int numDigits(T number)
{
    int digits = 0;
    if (number < 0) digits = 1; // remove this line if '-' counts as a digit
    while (number) {
        number /= 10;
        digits++;
    }
    return digits;
}

bool lexiSmaller(int i1, int i2)
{
    int digits1 = numDigits(i1);
    int digits2 = numDigits(i2);

    double val1 = i1/pow(10.0, digits1-1);
    double val2 = i2/pow(10.0, digits2-1);

    while (digits1 > 0 && digits2 > 0 && (int)val1 == (int)val2)
    {
        digits1--;
        digits2--;
        val1 = (val1 - (int)val1)*10;
        val2 = (val2 - (int)val2)*10;
    }
    if (digits1 > 0 && digits2 > 0)
    {
        return (int)val1 < (int)val2;
    }
    return (digits2 > 0);
}


int main(int argc, char* argv[])
{
    // just testing whether the comparison function works as expected:
    assert (lexiSmaller(1, 100));
    assert (!lexiSmaller(100, 1));
    assert (lexiSmaller(100, 22));
    assert (!lexiSmaller(22, 100));
    assert (lexiSmaller(927, 99));
    assert (!lexiSmaller(99, 927));
    assert (lexiSmaller(1, 927));
    assert (!lexiSmaller(927, 1));
    assert (lexiSmaller(21, 22));
    assert (!lexiSmaller(22, 21));
    assert (lexiSmaller(22, 99));
    assert (!lexiSmaller(99, 22));

    // use the comparison function for the actual sorting:
    int input[] = { 100 , 21 , 22 , 99 , 1 ,927 };
    std::sort(&input[0], &input[5], lexiSmaller);
    std::cout << "sorted: ";
    for (int i=0; i<6; ++i)
    {
        std::cout << input[i];
        if (i<5)
        {
            std::cout << ", ";
        }
    }
    std::cout << std::endl;
    return 0;
}

虽然我必须承认我还没有测试过性能。

是的，我会避免使用浮点数。不过内联测试用例做得很好。 - Lightness Races in Orbit
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接