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

Используйте любой алгоритм сортировки, который вам нравится, но сравнивайте числа как строки, а не как числа. Это в основном лексиографическая сортировка обычных чисел. Вот пример сортировки gnome в C:

#include <stdlib.h>
#include <string.h>

void sort(int* array, int length) {
    int* iter = array;
    char buf1[12], buf2[12];
    while(iter++ < array+length) {
        if(iter == array || (strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0) {
            iter++;
        } else {
            *iter ^= *(iter+1);
            *(iter+1) ^= *iter;
            *iter ^= *(iter+1);
            iter--;
        }
    }
}

Конечно, для этого необходимо, чтобы нестандартная функция itoa присутствовала в stdlib.h. Более стандартной альтернативой было бы использование sprintf, но это делает код немного более загроможденным. Возможно, вам лучше сначала преобразовать весь массив в строки, затем отсортировать, а затем преобразовать его обратно.

Редактировать. Для справки, соответствующий бит здесь — strcmp(itoa(*iter, &buf1, 10), itoa(*(iter-1), &buf2, 10) >= 0, который заменяет *iter >= *(iter-1).

У меня есть решение, но не совсем алгоритм. Все, что вам нужно сделать, это преобразовать все числа в строки и отсортировать их как строки.

Вот как это можно сделать с помощью рекурсивной функции (код на Java):

void doOperation(List<Integer> list, int prefix, int minimum, int maximum) {
    for (int i = 0; i <= 9; i++) {
        int newNumber = prefix * 10 + i;
        if (newNumber >= minimum && newNumber <= maximum) {
            list.add(newNumber);
        }
        if (newNumber > 0 && newNumber <= maximum) {
            doOperation(list, newNumber, minimum, maximum);
        }
    }
}

Вы называете это так:

List<Integer> numberList = new ArrayList<Integer>();
int min=1, max =100;
doOperation(numberList, 0, min, max);
System.out.println(numberList.toString());

РЕДАКТИРОВАТЬ:

Я перевел свой код на C++ здесь:

#include <stdio.h> 

void doOperation(int list[], int &index, int prefix, int minimum, int maximum) {
    for (int i = 0; i <= 9; i++) {
        int newNumber = prefix * 10 + i;
        if (newNumber >= minimum && newNumber <= maximum) {
            list[index++] = newNumber;
        }
        if (newNumber > 0 && newNumber <= maximum) {
            doOperation(list, index, newNumber, minimum, maximum);
        }
    }
}

int main(void) { 
        int min=1, max =100;
        int* numberList = new int[max-min+1];
        int index = 0;
        doOperation(numberList, index, 0, min, max);
        printf("["); 
        for(int i=0; i<max-min+1; i++) {
                printf("%d ", numberList[i]); 
        }
        printf("]"); 
        return 0; 
}

По сути, идея такова: для каждой цифры (0-9) я добавляю ее в массив, если она находится между minimum и maximum. Затем я вызываю ту же функцию с этой цифрой в качестве префикса. Он делает то же самое: для каждой цифры добавляет ее к префиксу (prefix * 10 + i) и, если она находится между пределами, добавляет ее в массив. Он останавливается, когда newNumber больше максимума.

я думаю, что если вы преобразуете числа в строку, вы можете использовать сравнение строк для их сортировки. вы можете использовать для этого алгоритм сортировки anny.

"1" < "10" < "100" < "11" ...

Оптимизируйте способ хранения чисел: используйте двоично-десятичный код (BCD), который дает простой доступ к определенной цифре. Затем вы можете использовать свой текущий алгоритм, который Стив Джессоп правильно определил как сортировка по основанию с наиболее значимой цифрой.

Я попытался сохранить все цифры в каждом числе в виде связанного списка для более быстрой работы, но это приводит к большой пространственной сложности.

Хранение каждой цифры в связанном списке занимает место по двум причинам:

1. Для хранения цифры (0-9) требуется всего 4 бита памяти, но вы, вероятно, используете от 8 до 64 бит. Тип char или short занимает 8 бит, а int может занимать до 64 бит. Это использует от 2 до 16 раз больше памяти, чем оптимальное решение!
2. Связанные списки добавляют дополнительные ненужные накладные расходы памяти. Для каждой цифры вам потребуется дополнительно от 32 до 64 бит для хранения адреса памяти следующей ссылки. Опять же, это увеличивает объем памяти, необходимый для каждой цифры, в 8-16 раз.

Более эффективное использование памяти позволяет хранить в памяти цифры BCD непрерывно: