сортировать массив целых чисел лексикографически

Чтобы обеспечить любой заказ сортировки, вы можете предоставить компаратор 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, }
}

демонстрация

Существуют более быстрые способы вычисления количества цифр в числе., но вышесказанное поможет вам начать.

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

Замечания:

• поддерживает только натуральные числа
• в поддерживает только целые числа <знак равно std::numeric_limits<int>::max()/10

_{Нотабене вы можете оптимизировать count_digits а также my_pow10; например, см. Три совета по оптимизации для C ++ от Андрея Александреску а также В любом случае быстрее, чем pow (), чтобы вычислить целую степень 10 в C ++?}

Помощники:

#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";
}

Вот вики сообщества для сравнения решений. Я взял код Нима и сделал его легко расширяемым. Не стесняйтесь добавлять свои решения и результаты.

Пример запускает старый медленный компьютер (3 ГБ ОЗУ, Core2Duo U9400) с g ++ 4.9 @ -O3 -march=native:

количество элементов: 1e + 03
размер целочисленного типа: 4

эталонное решение: гонки на орбите

Решение "Дип":
длительность: 0 мс и 301 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Ним":
длительность: 2 мс и 160 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Нярлатхотеп":
длительность: 8 мс и 126 мкс
Сравнение с эталонным решением: точное соответствие
Решение "notbad":
длительность: 1 мс и 102 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Эрик Постпищил":
длительность: 2 мс и 550 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Гонки Легкости на Орбите":
длительность: 17 мс и 469 мкс
Сравнение с эталонным решением: точное соответствие
Решение "оч":
длительность: 1 мс и 92 мкс
Сравнение с эталонным решением: точное соответствие

================================================== ========

количество элементов: 1e + 04
размер целочисленного типа: 4

Эталонное решение: Гонки Легкости на Орбите

Решение "Нярлатхотеп":
длительность: 109 мс и 712 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Гонки Легкости на Орбите":
длительность: 272 мс и 819 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Дип":
длительность: 1 мс и 748 мкс
Сравнение с эталонным решением: точное соответствие
Решение "notbad":
длительность: 16 мс и 115 мкс
Сравнение с эталонным решением: точное соответствие
Решение "оч":
длительность: 15 мс и 10 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Эрик Постпищил":
длительность: 33 мс и 301 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Ним":
длительность: 17 мс и 83 мкс
Сравнение с эталонным решением: точное соответствие

================================================== ========

количество элементов: 1e + 05
размер целочисленного типа: 4

Эталонное решение: Гонки Легкости на Орбите

Решение "Ним":
длительность: 217 мс и 4 мкс
Сравнение с эталонным решением: точное соответствие
Решение "оч":
длительность: 199 мс и 505 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Дип":
длительность: 20 мс и 330 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Эрик Постпищил":
длительность: 415 мс и 477 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Гонки Легкости на Орбите":
длительность: 3955 мс и 58 мкс
Сравнение с эталонным решением: точное соответствие
Решение "notbad":
длительность: 215 мс и 259 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Нярлатхотеп":
длительность: 1341 мс и 46 мкс
Сравнение с эталонным решением: обнаружено несоответствие

================================================== ========

количество элементов: 1e + 06
размер целочисленного типа: 4

Эталонное решение: Гонки Легкости на Орбите

Решение "Гонки Легкости на Орбите":
длительность: 52861 мс и 314 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Эрик Постпищил":
длительность: 4757 мс и 608 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Нярлатхотеп":
длительность: 15654 мс и 195 мкс
Сравнение с эталонным решением: обнаружено несоответствие
Решение "Дип":
длительность: 233 мс и 779 мкс
Сравнение с эталонным решением: точное соответствие
Решение "оч":
длительность: 2181 мс и 634 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Ним":
длительность: 2539 мс и 9 мкс
Сравнение с эталонным решением: точное соответствие
Решение "notbad":
длительность: 2675 мс и 362 мкс
Сравнение с эталонным решением: точное соответствие

================================================== ========

количество элементов: 1e + 07
размер целочисленного типа: 4

Эталонное решение: Гонки Легкости на Орбите

Решение "notbad":
длительность: 33425 мс и 423 мкс
Сравнение с эталонным решением: точное соответствие
Решение "оч":
длительность: 26000 мс и 398 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Эрик Постпищил":
длительность: 56206 мс и 359 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Гонки Легкости на Орбите":
длительность: 658540 мс и 342 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Нярлатхотеп":
длительность: 187064 мс и 518 мкс
Сравнение с эталонным решением: обнаружено несоответствие
Решение "Ним":
длительность: 30519 мс и 227 мкс
Сравнение с эталонным решением: точное соответствие
Решение "Дип":
длительность: 2624 мс и 644 мкс
Сравнение с эталонным решением: точное соответствие

Алгоритмы должны быть структурированы с помощью шаблонов операторов вызова функций, которые поддерживают интерфейс:

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";
}
}
}

Современные алгоритмы; Заметьте, я заменил счетчики цифр и pow-of-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);
}
};

Я полагаю, что следующее работает как функция сравнения сортировки для натуральных чисел, при условии, что используемый тип целого числа существенно уже, чем 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 возвращает что-то вроде 4.99999 … когда он должен был вернуться 5.

Преимущество этого метода заключается в том, что он не использует циклы или деление (что отнимает много времени на многих процессорах).

Задание звучит как естественная подгонка для MSD-варианта Radix Sort с отступом ( http://en.wikipedia.org/wiki/Radix_sort ).

Зависит от того, сколько кода вы хотите добавить в него. Простой код, как показывают другие, — сложность O (log n), тогда как полностью оптимизированная сортировка по основанию будет O (kn).

Компактное решение, если все ваши числа неотрицательны и они достаточно малы, так что умножение их на 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;
}

Вы можете попробовать использовать оператор%, чтобы дать вам доступ к каждой отдельной цифре, например, 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;
}

Пусть количество цифр в max равно n.
После этого откройте цикл for в формате
для (int i = 1; i < п; я ++)

затем вы можете просмотреть и использовать «data [i]% (10 ^ (n-i))», чтобы получить доступ к первой цифре.
Сортируйте это и затем на следующей итерации вы получите доступ ко второй цифре. Я не знаю, как вы их отсортируете.

Он не будет работать для отрицательных чисел, и вам придется обойти данные [i]% (10 ^ (n-i)), возвращая себя для чисел с меньшим количеством цифр, чем макс.