Я пытаюсь понять, как работает разделение QuickSelect, и есть несколько вещей, которые я не получаю, я попытаюсь объяснить, как я это вижу (обратите внимание, что я переименовал переменные и сделал свои комментарии, чтобы попытатьсяпоймите это, поэтому, возможно, некоторые переименования или комментирования неправильны):
- Во-первых, значение pivot - это значение индекса, в котором находится pivot, что имеет смысл.
- Теперь мы поменяем шарнир на конец массива, почему?
- У нас есть первый указатель, который начинается слева, потому что первый указатель, конечно, должен начинаться с начала.
- В цикле for у нас есть второй указатель, который также начинается слева, почему? .Разве это не должно начинаться на другом конце?
- Если мы находимся меньше, чем значение поворота, меняем их местами, чтобы мы получили меньшие элементы слева.
- В концепоменяйте местами опору (это приводит к тому, что мой кулак «почему»).
- В конце мы возвращаем первый указатель, который, как я полагаю, потому, что это единственный элемент, оставшийся в массиве?
Я видел различные виды реализаций, и я обнаружил, что большинство, если не все, делают это.
// Partitioning.
private static int quickSelectPartition(int[] array, int left, int right, int pivotIndex) {
// The value of the pivot depends on the value at the random index that we got.
int pivotValue = array[pivotIndex];
// Move the pivot to the end.
swapLeftWithRight(array, pivotIndex, right);
// First pointer starts from left.
int firstPointer = left;
// Second pointer starts from left.
for(int secondPointer = left; secondPointer < right; secondPointer++) {
// If the value at the second pointer is less than pivot value, swap it to where the first pointer is.
if(array[secondPointer] < pivotValue) {
// Swap.
swapLeftWithRight(array, firstPointer, secondPointer);
// Move the first pointer forward.
firstPointer++;
}
}
// When done with this partitioning, swap the pivot back to its original position.
swapLeftWithRight(array, right, firstPointer);
return firstPointer;
}