Сортировка чисел в порядке цифр

Question

Я знаю, что когда числа вводятся как строки и сортируются нормально, я получаю правильный вывод. Но может кто-нибудь объяснить, как/почему это происходит?

Пример тест:

Вход:

100 1 10 2 21 20 

Выход:

1 10 100 2 20 21 

Answer 1

Digits, когда рассматриваются как символы, обрабатываются так же, как алфавитный персонажи. (т.е. они имеют относительный лексикографический порядок, который совпадает с порядком их размещения на основе возрастающего значения)

Фактически, когда вы обрабатываете целые числа в виде строки, вы можете рассматривать цифры 0,1,2,3, 4,5,6,7,8,9 - буквы a, b, c, d, e, f, 'J'. Следовательно, сортировку ввода можно рассматривать как сортировку строк.

Ваш первоначальный вход;

100 1 10 2 21 20 

можно затем рассматривать как;

baa b ba c cb ca 

, для которого будет надлежащим образом оформлен заказ;

b ba baa c ca cb 

Если вы вернете значения, вы можете увидеть, что это результат, который вы предоставили в своем вопросе, а именно:

1 10 100 2 20 21 

Answer 2

Именно так и по умолчанию lexicographical string comparison работает.

То, что вы, вероятно, ищете называется natural sort:

Естественный порядок означает сортировку строк так, что встроенные числа рассматриваются как числа. Это означает, что если вы используете естественный порядок сортировки вы получите это:

1 one 
2 two 
3 three 
10 ten 

Вместо поведения сортировки по умолчанию:

1 one 
10 ten 
2 two 
3 three 

Answer 3

Чтение списка номеров, сортировка их, а затем распечатывать их в чрезвычайно легко в C++, как только вы знаете, «секрет».

«Секрет» заключается в использовании функциональных возможностей, существующих в стандартной библиотеке. В этом случае (чтение номеров, их сортировка, их распечатка) вы должны знать о std::vector, std::istream_iterator, std::sort, std::copy и std::ostream_iterator.

Тогда вы могли бы сделать что-то вроде

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <algorithm> 

int main() 
{ 
    // Create a vector containing numbers read from std::cin 
    std::vector<int> number(std::istream_iterator<int>(std::cin), 
          std::istream_iterator<int>()); 

    // Sort the numbers 
    std::sort(begin(numbers), end(numbers)); 

    // Print all the numbers in the vector to std::cout 
    std::copy(begin(numbers), end(numbers), 
       std::ostream_iterator<int>(std::cout, " ")); 
}