Голландский раздела


Проблема голландской секции. Раздел данного массива с помощью pivotIndex на группы с элементами меньше, чем стержень, равна pivot и больше, чем центровые.

public static void partition(int[] inputArray, int pivotIndex){
    int smaller = 0, equal = 0, larger = inputArray.length-1;
    int pivot = inputArray[pivotIndex];
    while(equal <= larger){
      if(inputArray[equal] < pivot){
        swap(inputArray, smaller, equal);
        smaller++;
        equal++;
      } else if(inputArray[equal] == pivot){
        equal++;
      } else {
        swap(inputArray, equal, larger--);
      }
    }
  }

private static void swap(int[] inputArray, int firstIndex, int secondIndex){
    int temp = inputArray[firstIndex];
    inputArray[firstIndex] = inputArray[secondIndex];
    inputArray[secondIndex] = temp;
  }


122
3
задан 28 марта 2018 в 03:03 Источник Поделиться
Комментарии
2 ответа


int smaller = 0, equal = 0, larger = inputArray.length-1;

Я рекомендую ставить каждое объявление переменной в отдельной строке. (сказал, lmus это уже его ответ, но я найти его гораздо важнее.)

int smaller = 0;
int equal = 0;
int larger = inputArray.length - 1;

Это делает его гораздо более читаемым. Особенно, когда вы ищете объявления переменной, вы найдете его гораздо быстрее.


Я не думаю, что вышеперечисленные имена переменных, особенно хорошо подобраны. Эти имена имеют логические имена. Я не знаю алгоритм достаточно хорошо, чтобы предложить лучшего названия (в Википедии статья для алгоритма, который использует отдельные буквы, которые уж точно не лучше), но я не знаю, что smaller или larger или equal значит, так я думаю, что может быть лучше имена.

Также название inputArray является избыточным, поскольку тип переменной не должны быть в названии. numbers может быть лучше, потому что он говорит вам, что он содержит, а также не важно, является ли их ввода (в смысле пользователя) или нет. В случае, если вы имеете в виду вход алгоритма, то это понятно по его параметра. Так как это своего рода алгоритм сортировки, numbersToSort может быть хорошим и более явной. Последнее также делает более ясным, что числа сортируются в месте, пока inputArray может обмануть абонента забывать, что это тоже выходной массив.



int pivot = inputArray[pivotIndex];

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

Поскольку вам доступ inputArray[equal] с индексом так же, я бы просто удалить выше переменную и заменить

if(inputArray[equal] < pivot){

с

if (inputArray[equal] < inputArray[pivotIndex])


Использование пространства является необоснованной. Например, у вас есть пробел после else перед этой скобкой, но не после else if. Я обычно ставлю пробел перед каждой открывающей скобкой, а также после каждого if, else, while и т. д., как это делает код выглядеть менее прижаты друг к другу, но самое главное-это быть последовательным.


swap(inputArray, smaller, equal);
smaller++;
equal++;

и

swap(inputArray, equal, larger--);

одно несоответствие. Вы можете либо сделать swap(inputArray, smaller++, equal++); чтобы быть последовательным, или больше, более четкой, а также согласованный вариант замены второй с

swap(inputArray, equal, larger);
larger--;

Я предпочту второе, более явный вариант.

3
ответ дан 28 марта 2018 в 08:03 Источник Поделиться

Не много, чтобы добавить здесь. В Кодексе ясно написано. Почти нет вопросов стиля. (Это обычно лучше, чтобы объявлять переменные в отдельных строках, но достаточно ясно, чтобы не быть реальной проблемой).

Единственная небольшая вещь, которую я хотел бы изменить это переименование equal для current, но это также может быть предпочтений. В current лучше, чтобы указать, какой элемент мы сейчас работаем с а equal очевидно, что есть средний блок элементов, которые равны пивот.

Молодец.

0
ответ дан 28 марта 2018 в 07:03 Источник Поделиться