Я недавно вернулся к быстрой сортировке. Раньше я делал поворот, выбирая последний или первый элемент из списка. Однако другой я наткнулся на этот фрагмент, где ось была выбрана с середины. Я знаю, что то, как рассчитывается пивот, влияет только на производительность алгоритма. Но я просто не могу понять этот алгоритм разделения.
Полагаю, для меня проблема в понимании алгоритма разбиения состоит в том, что, я думал, он должен сделать результирующий массив таким, чтобы все элементы, меньшие, чем сводка, уходили влево, а все элементы, большие, чем сводка, переходили к право. Однако этот алгоритм разделения не всегда достигает этого.
private static void quickSort (int[] array, int left, int right) {
int index = partition(array, left, right);
//Sort left half
if (left < index - 1)
quickSort(array, left, index - 1);
//Sort right half
if (index < right)
quickSort(array, index , right);
}
private static int partition (int array[], int left, int right) {
int pivot = array[(left + right) / 2]; //Pick pivot point
while (left <= right) {
//Find element on left that should be on right
while (array[left] < pivot)
left++;
//Find element on right that should be on left
while (array[right] > pivot)
right--;
//Swap elements and move left and right indices
if (left <= right) {
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
return left;
}
если я задаю алгоритму разбиения массив [1,0,-1,3,5,10,-5], то опорная точка будет 3, но после разбиения массив будет [ 1, 0, -1, -5, 5, 10, 3 ]. Я просто не могу понять это, потому что не похоже, что раздел делает что-то значимое. Он не разделил массив пополам.