Невозможно прекрасно реализовать QuickSort

Question

Я пытаюсь написать простой метод в java, который будет выполнять quicksort по int [], но я получаю одно значение, которое неуместно в моих результатах.

Любая помощь, чтобы понять, куда я иду, будет оценена по достоинству. Ниже приведен мой код:

public static void quickSort(int[] arr, int left, int right){ 
    if (left < right){ 
     int p = partition(arr, left, right); 
     quickSort(arr, left, p-1); 
     quickSort(arr, p+1, right); 
    } 
} 

public static int partition(int[] arr, int left, int right){ 
    int pivot = arr[left]; 
    int l = left+1; 
    int r = right; 
    while (l < r){ 
     while (l<right && arr[l] < pivot){ 
      l++; 
     } 
     while (r>left && arr[r] > pivot){ 
      r--; 
     } 
     if (l < r){ 
      int temp = arr[l]; 
      arr[l] = arr[r]; 
      arr[r] = temp; 
     } 
    } 
    arr[left] = arr[r]; 
    arr[r] = pivot;   
    return r; 
} 

Answer 1

Ваш код идеален, но не забудьте указать правильные значения методу quickSort.

 int[] arr = .....; 
     int left = 0; 
     int right = arr.length - 1; 

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

Answer 2

Эти две линии с подозрением:

quickSort(arr, p+1, right);

и

int l = left+1;

Принимая правую боковую перегородку, вы пропуская первый элемент массива? Некоторые примеры тестовых примеров и их выход были бы полезны для добавления.

Answer 3

Я изменил ваш метод разделения. Я стараюсь делать незначительные изменения, в основном для разрыва цикла.

public static int partition(int[] arr, int left, int right) { 
    int pivot = arr[left]; 
    int l = left ; 
    int r = right+1; 
    while (true) { 
     while (arr[++l] < pivot) { 
      if (l >= right) 
       break; 
     } 
     while (arr[--r] > pivot) { 
      if (r <= left) 
       break; 
     } 
     if (l >= r) 
      break; 
     int temp = arr[l]; 
     arr[l] = arr[r]; 
     arr[r] = temp; 
    } 
    arr[left] = arr[r]; 
    arr[r] = pivot; 
    return r; 
} 

Я тестировал ниже сценарии и работает.

int[] arr = { 9, 5, 10, 8, 2, 3, 4, 7, 6, 1 }; 
int[] arr = { 9, 5, 10, 8, 2, 9, 5, 10, 8, 2 }; 
quickSort(arr, 0, arr.length - 1); 
System.out.println(Arrays.toString(arr)); 

Answer 4

Схема разделения Hoare использует p и p + 1 в вызовах быстрой сортировки. Я преобразовал рабочую программу на Java. Я переключил ось вращения в середину, поэтому отсортированные или обратные отсортированные массивы не являются худшим случаем.

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

public static int partition(int[] arr, int left, int right){ 
    int pivot = arr[(left+right)/2]; 
    int l = left-1; 
    int r = right+1; 
    while (true){ 
     while (arr[++l] < pivot); 
     while (arr[--r] > pivot); 
     if (l >= r) 
      break; 
     int temp = arr[l]; 
     arr[l] = arr[r]; 
     arr[r] = temp; 
     } 
    } 
    return r; 
}