Введение
QuickSort - это алгоритм сортировки, основанный на методе "разделяй и властвуй". Он работает путём выбора "основа" (pivot) из массива и разделения других элементов на два подмассива в зависимости от того, меньше или больше они, чем "основа". Затем подмассивы сортируются рекурсивно. Средняя сложность QuickSort составляет O(n log n). Следует отметить, что QuickSort не является стабильной сортировкой, то есть относительные позиции равных элементов при сортировке могут быть нарушены.
Импортировать класс Arrays
В этом шаге вам нужно импортировать класс java.util.Arrays. Этот класс содержит несколько методов для манипуляций с массивами, которые будут использоваться для преобразования массивов int в String.
import java.util.Arrays;
Определить метод partition()
Определите вспомогательный метод под названием partition(). Метод partition() будет принимать на вход массив arr, начальный индекс low и конечный индекс high. Метод partition() будет выбирать элемент в качестве опорного и разделять элементы так, чтобы все элементы, меньшие опорного элемента, были слева от опоры, а все элементы, большие опоры, были справа от опоры. Опорный элемент будет помещён в свою правильную позицию.
Метод partition() вернёт индекс разделённого элемента. Разделённым элементом является позиция, где находится опорный элемент.
public static int partition(int[] arr, int low, int high) {
// Select the pivot element
int pivot = arr[high];
int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i + 1] and arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the partition index
}
Определить метод quicksort()
Определите метод сортировки под названием quicksort(). Метод quicksort() будет принимать на вход массив arr, начальный индекс low и конечный индекс high. Метод quicksort() будет рекурсивно сортировать массив arr[].
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now
// at right place
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Создать и присвоить целочисленный массив
Создайте и присвойте целочисленные массивы для сортировки полю arr.
int[] arr = {7, 9, 1, 2, 10, 15, 6};
Реализовать Быстрая сортировку
Вызовите метод quickSort(), передав в него поле arr в качестве входных данных, а также начальный и конечный индексы массива. Отсортируйте и выведите массив с использованием метода Arrays.toString(arr).
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
Тестировать с помощью нескольких массивов
Тестируйте свою реализацию QuickSort с использованием массивов с различными характеристиками.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
Случайным образом выбрать опорный элемент
В этом шаге нам нужно случайным образом выбирать опорный элемент на каждой итерации, чтобы избежать худшего случая. Для этого мы обновим метод partition() и заменим следующую строку:
int pivot = arr[high];
на эту строку:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
Тестировать с использованием случайного опорного элемента
Тестируйте свою реализацию QuickSort с использованием случайных опорных элементов.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
Обрабатывать особые случаи
В этом шаге мы рассмотрим граничные случаи, которые может обработать QuickSort. Определите эти граничные случаи в виде массивов целых чисел.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
Полный код
Ниже представлен полный код QuickSort на Java.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
Резюме
В этом лабе был представлен пошаговый гайд по реализации алгоритма QuickSort на Java. Мы узнали, что выбор опорного элемента является важным этапом в QuickSort, и что разные методы выбора опорного элемента могут повлиять на производительность алгоритма. QuickSort лучше всего подходит для сортировки больших объемов данных. Худшая временная сложность QuickSort составляет O(N^2), в то время как средняя и лучшая временная сложность равна O(NLogN).
