Концептуально понимает быструю сортировку

Я пытаюсь визуализировать работу Quick Sort. В основном, я пытаюсь понять часть раздела. Я отправлю код ниже:

public int paritionIt(int left, int right, long pivot){
 leftPtr = left - 1;
 rightPtr = right + 1;

 while (true) {
 while (leftPtr < right && Array[++leftPtr] < pivot);
 while (rightPtr > left && Array[--rightPtr] > pivot);
 if (leftPtr <= rightPtr)
 break;
 else
 swap(leftPtr, rightPtr);
 } //end while loop
 return leftPtr;
}

Мой последний вопрос: почему мы возвращаем leftPtr? Я чувствую, что это было бы неправильно... В алгоритме быстрой сортировки используется рекурсия:

public void recQuicksort(int left, int right){
 if(left - right <= 0)
 return 0;
 else{
 long pivot = array[right];
 int partition = partitionIt(left, right, pivot);
 recQuicksort(left, partition -1);
 recQuicksort(partition + 1, right);
 }
}

У меня просто трудное время, пытаясь концептуализировать это.

2 ответа

Задача этой конкретной версии раздела состоит в том, чтобы переупорядочить список, чтобы все элементы, не превышающие опорную точку, отображались перед всеми элементами не меньше, чем точка поворота. (Это означает, что элементы, равные оси вращения, могут быть разбросаны в любом месте, а также должны возвращать индекс начала второго под-списка.

Многие заказы могут удовлетворить это требование. Для одного заказа может быть допустимо более одного возвращаемого значения. Это не мешает правильной работе Quicksort, поэтому не стоит беспокоиться.

Для ваших данных примера (3,9,4,7) первый проход будет останавливаться с левым = 1, справа = 3, и поэтому он будет заменять 7 и 9 для создания (3,7,4,9). Затем он остановится с левым = 3 и правым = 2, что приведет к перерыву в другом цикле. Возвращаемое значение равно 3. Это правильно, потому что это на один шаг ниже конца начального подмассива, который теперь полностью меньше или равен оси.

Однако с этой версией раздела у quicksort есть ошибка. Должен быть:

public void recQuicksort(int left, int right) {
 if (left < right) {
 long pivot = array[right];
 int partition = partitionIt(left, right, pivot);
 recQuicksort(left, partition - 1);
 recQuicksort(partition, right);
 }
}


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

Чтобы показать, как быстро сортировать данные по набору данных (1,2,3,4,5), просто введите 1 2 3 4 5 и нажмите enter.Чтобы показать наилучший случай, введите b5, цифра 5 означает глубину повторного использования. Чтобы показать средний случай, введите r1..10, r означает случайный, 1..10 означает случайный набор данных перестановок 1 2 3 4 5 6 7 8 9 10.

Вот лучший пример:

худший случай:

средний случай:

licensed under cc by-sa 3.0 with attribution.