Быстрая сортировка в Java: алгоритм, примеры кода и лучшие практики

Быстрая сортировка (quicksort) - это один из наиболее эффективных алгоритмов сортировки в общем случае. Он относится к категории алгоритмов "разделяй и властвуй" и работает по принципу выбора опорного элемента, разделения массива на две части - элементы, меньшие опорного, и элементы, большие опорного, и рекурсивной сортировки этих двух частей.

Вот пример кода реализации быстрой сортировки на языке Java:

java
public class QuickSort {
  
  public static void main(String[] args) {
    int[] array = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
    System.out.println("Исходный массив: " + Arrays.toString(array));
    quickSort(array, 0, array.length - 1);
    System.out.println("Отсортированный массив: " + Arrays.toString(array));
  }
  
  public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
      int pivotIndex = partition(array, low, high);
      quickSort(array, low, pivotIndex - 1);
      quickSort(array, pivotIndex + 1, high);
    }
  }
  
  public static int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
      if (array[j] < pivot) {
        i++;
        swap(array, i, j);
      }
    }
    swap(array, i + 1, high);
    return i + 1;
  }
  
  public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

В этом примере мы используем метод `quickSort`, который принимает массив и границы для сортировки. Если `low < high`, то он выбирает опорный элемент (в данном случае, последний элемент) и делит массив на две части в методе `partition`. Затем он вызывает `quickSort` рекурсивно для двух полученных частей. Метод `partition` выполняет фактическое разделение массива, перемещая элементы меньше опорного слева от него, а элементы больше опорного - справа от него.

Приведенный код сортирует исходный массив {9, 7, 5, 11, 12, 2, 14, 3, 10, 6}. После выполнения быстрой сортировки, выводится отсортированный массив {2, 3, 5, 6, 7, 9, 10, 11, 12, 14}.

Быстрая сортировка в лучшем и среднем случае имеет сложность O(n log n), где n - количество элементов в массиве. В худшем случае, когда выбирается плохой опорный элемент, сложность может быть O(n^2), но вероятность его возникновения невысока.