Algorithmusgymnastik 9

Quick Sort

Erläuterung

Die schnelle Sortierung ist ein Algorithmus, der den berühmten Sortieralgorithmus "Teilen und Erobern" verwendet. Es ist so berühmt, dass, wenn Sie nicht gehört haben, was Quick Sort ist, hier als Referenz.

Solution

Runtime Complexity O（nlogn) Wenn Sie Pivot ganz links im Array auswählen

1. Das Array ist bereits in derselben Reihenfolge sortiert
2. Das Array ist bereits in umgekehrter Reihenfolge sortiert
3. Alle Elemente sind gleich Mit Ausnahme der drei Bedingungen ist es O (nlogn), aber wenn Sie zufällig auf diese Bedingung stoßen, ist es O (n ^ 2).

Memory Complexity O(logn) Sortieren Sie die rechte und die linke Seite getrennt vom Drehpunkt. Zu diesem Zeitpunkt wird da eine rekursive Funktion verwendet Es ist O (logn), weil es Speicher auf dem Stapel verbraucht.

Grober Algorithmusfluss

1. Wählen Sie ein Pivot-Element aus dem Array aus. Wählen Sie das erste Element des Arrays als Pivot aus.
2. Tauschen Sie so, dass sich Werte kleiner als Pivot auf der linken Seite von Pivot und Werte größer als Pivot auf der rechten Seite von Pivot befinden.
3. Sie können die rechten und linken Subarrays von Pivot rekursiv neu anordnen.

Implementierung

quickSort.java

class quickSort{

  public int partition(int[] arr, int low, int high) {

    int pivot_value = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
      while( i <= high && arr[i] <= pivot_value) i++;
      while(arr[j] > pivot_value) j--;

      if (i < j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    
    arr[low] = arr[j];
    arr[j] = pivot_value;

    return j;
  }
  
  public void quick_sort_recursive(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      quick_sort_recursive(arr, low, pivot - 1);
      quick_sort_recursive(arr, pivot + 1, high);
    }
  }

  public void quick_sort(int[] arr) {
    quick_sort_recursive(arr, 0, arr.length - 1);
  }
}