вопрос о сортировке строк

Question

У меня вопрос от программирования жемчуга

проблема следующая

показать, как использовать схему разбиения Lomuto для сортировки битовых строк различной длины во времени, пропорциональном сумме их длины

и алгоритм следующий

каждая запись в x [0..n-1] имеет целочисленную длину и указатель на бит массива [0..length-1] код

void bsort(l,u,depth)
{
  if (l>=u) return;

  for (int i=l;i<u;i++)
    if (x[i].length<depth)
      swap(i,l++);

  m=l;
  if (x[i].bit[depth] == 0) swap(i,m++);
  bsort(l,m-1,depth+1);
  bsort(m,u,depth+1);
}

Мне нужны следующие вещи:

1. как работает этот алгоритм
2. как реализовать в Java?

Answer 1

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