Алгоритм быстрой сортировки неправильно назначает точку опоры

Мне пришлось избавиться от раздела, потому что вам нужны и i, и j. Это должно выглядеть так:

public void quickSort(int[] a, int left, int right) {

    int i = left; // Was -1 
    int j = right; // Was +1
    int pivot = a[left + (right - left) / 2]; // Pivot is the value of the middle index, not the index itself
    while (i <= j) { // Changed terminating condition
        //   i++;  Not needed
        while (a[i] < pivot) { 
            i++;
        }
        //    j++; Not needed
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {  // Changed terminating condition
            swap(a, i, j);
            i++;  // You need to progress the indexes after the swap
            j--;
        }
    }

    System.out.println(Arrays.toString(a));
    if (left < j) {  // Changed condition
        quickSort(a, left, j);
    }
    if (i < right) { 
        quickSort(a, i, right); // was i + 1
    }
}

Выход:

[4, 5, 1, 2, 3, 7, 6, 8]
[1, 5, 4, 2, 3, 7, 6, 8]
[1, 3, 2, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 7, 6, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

хорошо, очевидно, что вы получили принятый ответ. однако я хотел бы упомянуть, что логика вашего раздела может быть реализована проще, только с одним циклом for (или while), без цикла гнезда:

int partition(final int[] a, final int left, final int right) {
        // set the last element as pivot
        final int pivot = a[right];
        int i = left - 1, j = left;
        for (; j < right; j++) 
            if (a[j] < pivot) {
                i++;
                swap(a, i, j);
            }       
        // swap a[i+1] and pivot
        swap(a, i + 1, right);
        return i + 1;
    }

и в вашем методе quickSort:

if (left < index)
  quickSort(a, left, index-1);
if (index < right)
  quickSort(a, index + 1, right);

Надеюсь, поможет

int pivot = a[0];

должно быть

int pivot = a[left];

Что, с заменой swap (a, i, j); на swap (a, i--, j++); и все работает нормально.

Почему вышеуказанное изменение:

Сводка должна быть первым элементом в диапазоне, а не первым элементом.

И не должно быть в этой середине, как здесь:

int pivot = a[(left + right) / 2];

Неважно, какой элемент вы хотите сделать опорным, проще всего всегда менять местами выбранный элемент с первым элементом и продолжать как обычно. Могут быть и другие способы сделать что-то, но они, вероятно, будут более сложными.

Итак, вы можете сказать:

swap(left, (left + right) / 2);
int pivot = a[left];

который очень похож на приведенный выше (не идентичен), просто с ним намного проще иметь дело.

Я думаю, что метод partition должен возвращать j вместо i.

Еще одна проблема в вашем коде - ваши условия остановки:

вместо двух отдельных условий я бы изменил его на одно условие:

if (left < right)  {

  do partition & recursive calls

}

Полный код:

public void quickSort(int[] a, int left, int right) {
    if (left < right) {
      int index = partition(a, left, right);
      quickSort(a, left, index);
      quickSort(a, index + 1, right);
    }
}

private int partition (int[] a, int left, int right) {
    int i = left - 1;
    int j = right + 1;
    int pivot = a[(left+right)/2];

    while (i < j) {

        i++;

        while (a[i] < pivot)
            i++;

        j--;

        while (a[j] > pivot)
            j--;

        if (i < j)
            swap (a, i, j);
    }
    return j;
}   

private void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}