Вид N числа в порядке цифры

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

Вот как это можно сделать с помощью рекурсивной функции (код находится на 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());

EDIT:

Я перевел свой код на 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) я добавляю ее в массив, если она находится между минимумом и максимум . Затем я вызываю ту же функцию с этой цифрой в качестве префикса. Он делает то же самое: для каждой цифры он добавляет ее к префиксу ( prefix * 10 + i ), и, если он находится между пределами, добавляет его в массив. Он останавливается, когда newNumber больше максимального.

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

«1» <«10» <«100» <«11» ...

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

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

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

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

В более эффективном для памяти решении BCD цифр непрерывно хранятся в памяти:

1. BCD использует только 4 бита на цифру.
2. Сохраните цифры в непрерывном блоке памяти, например в массиве. Это избавляет от необходимости хранить адреса памяти. Вам не нужна возможность связанных списков легко вставлять / удалять из середины. Если вам нужна возможность увеличивать числа до неизвестной длины, существуют другие абстрактные типы данных, которые позволяют это с гораздо меньшими накладными расходами. Например, вектор .

Один из вариантов, если другие операции, такие как сложение / умножение, не важны, - это выделить достаточно памяти для хранения каждой цифры BCD плюс один терминатор BCD. Терминатор BCD может быть любой комбинацией 4 битов, которая не используется для представления цифры BCD (например, двоичный 1111 ). Однако при хранении таким образом другие операции, такие как сложение и умножение, будут более сложными.

Обратите внимание, что это очень похоже на идею преобразования в строки и лексикографической сортировки этих строк. Целые числа внутренне хранятся в компьютере как двоичные (основание 2). Хранение в BCD больше похоже на основание 10 (на самом деле основание 16, но 6 комбинаций игнорируются), а строки похожи на базу 256. Строки будут использовать примерно вдвое больше памяти, но уже есть эффективные функции, написанные для сортировки строк. BCD, вероятно, потребует разработки пользовательского типа BCD для ваших нужд.

Если вы не хотите преобразовывать их в строки, но у вас достаточно места для хранения дополнительной копии списка, я бы хранил наибольшую степень десяти меньше, чем элемент в копии. Это, вероятно, проще всего сделать с помощью цикла. Теперь назовем ваш исходный массив x и силы десяти y.

int findPower(int x) {
   int y = 1;
   while (y * 10 < x) {
      y = y * 10;
   }
   return y;
}

Вы также можете вычислить их напрямую

y = exp10(floor(log10(x)));

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

Чтобы сравнить ith и jth элементы

bool compare(int i, int j) {
  if (y[i] < y[j]) {
    int ti = x[i] * (y[j] / y[i]);
    if (ti == x[j]) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (ti < x[j]);
    }
  } else if (y[i] > y[j]) {
    int tj = x[j] * (y[i] / y[j]);
    if (x[i] == tj) {
      return (y[i] < y[j]);  // the compiler will optimize this
    } else {
      return (x[i] < tj);
    }
  } else {
     return (x[i] < x[j];
  }
}

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

Если у вас нет места для хранения массивов y, вы можете вычислять их при каждом сравнении.

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

Edit: I missed that it's a contiguous range. Таким образом, все ответы, в которых говорится о сортировке массива, неверны (включая вашу идею, изложенную в вопросе, что это похоже на радиксную сортировку), а ответ True Soft правильный.

так же, как Radix Sort, но только цифры сортируются в обратном порядке

Хорошо подмечено :-) Если вы действительно делаете это таким образом, то, как ни смешно, это называется MSD radix sort.

http://en.wikipedia.org/wiki/Radix_sort#Most_significant_digit_radix_sorts

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

Конечно, необязательно реализовывать это как радиксную сортировку: можно использовать алгоритм сортировки сравнением с соответствующим компаратором. Например, на языке C для использования с qsort подходит следующее (если я ничего не напутал):

int lex_compare(void *a, void *b) {
    char a_str[12];  // assuming 32bit int
    char b_str[12];
    sprintf(a_str, "%d", *(int*)a);
    sprintf(b_str, "%d", *(int*)b);
    return strcmp(a_str,b_str);
}

Не очень эффективно, поскольку выполняет много повторяющейся работы, но просто.

Используйте любой алгоритм сортировки, который вам нравится, но сравнивайте числа как строки , а не как числа. По сути, это лексиографическая сортировка обычных чисел. Вот пример сортировки 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) .