QuickSort - это алгоритм «разделяй и властвуй». В парадигме проектирования алгоритма Divide & Conquer мы рекурсивно разделяем проблемы на подзадачи, затем решаем подзадачи и, наконец, объединяем решения, чтобы найти окончательный результат. В этой статье мы сосредоточимся на QuickSort In
Следующие указатели будут рассмотрены в этой статье,
Давайте начнем!
При разделении проблем на подзадачи следует иметь в виду, что структура подзадач не меняется по сравнению с исходной проблемой.
Алгоритм Divide & Conquer состоит из 3 шагов:
- Разделить: разбить проблему на подзадачи
- Завоевание: рекурсивное решение подзадач
- Комбинировать: комбинировать решения для получения окончательного результата.
Существуют различные алгоритмы, основанные на парадигме «разделяй и властвуй». Среди них быстрая сортировка и сортировка слиянием.
Хотя наихудшая временная сложность QuickSort составляет O (n2), что больше, чем у многих других алгоритмов сортировки, таких как сортировка слиянием и сортировка кучи, QuickSort на практике работает быстрее, поскольку его внутренний цикл может быть эффективно реализован на большинстве архитектур и в большинстве данные из реального мира.
Поговорим о реализации алгоритма быстрой сортировки. QuickSort алгоритмы принимают шарнирный элемент и перегородки массива вокруг шарнирного elememt. Существует ряд вариантов Quicksot, которые зависят от того, как вы выбираете элемент поворота. Есть несколько способов выбрать опорный элемент:
- Выбор первого элемента
- Выберите последний элемент
- Выбор случайного элемента
- Выбор среднего элемента
Следующая важная вещь, которую нужно понять, - это функция partition () в алгоритме быстрой сортировки. Функция разделения, которая принимает поворотный элемент, помещает его в правильное положение, перемещает все элементы, меньшие, чем поворотный элемент, влево и все элементы больше вправо. Для быстрой сортировки требуется линейное время.
Затем массив делится на две части от основного элемента (т.е. элементы меньше, чем точка поворота, и элементы больше, чем точка поворота), и оба массива рекурсивно сортируются с использованием алгоритма быстрой сортировки.
Теперь, когда мы понимаем, как работает алгоритм QuickSort. Давайте разберемся, как реализовать алгоритм быстрой сортировки на Java.
QuickSort Функция:
/ * Функция быстрой сортировки требует, чтобы массив был отсортирован с наименьшим и наибольшим индексом * /
void sort (int arr [], int lowIndex, int highIndex) {// Пока lowIndex = highIndex if (lowIndexТеперь давайте посмотрим на код разделения, чтобы понять, как он работает.
Раздел Код
В коде разметки, мы выберем последний элемент в качестве элемента вращения. Мы проходим по всему массиву (то есть с использованием переменной j в нашем случае). Мы отслеживаем последний наименьший элемент в массиве (то есть с использованием переменной i в нашем случае). Если мы находим какой-либо элемент, меньший, чем точка поворота, мы перемещаем текущий элемент a [j] местами на arr [i], в противном случае мы продолжаем перемещение.
int partition (int arr [], int lowIndex, int highIndex) {// Делаем последний элемент как сводный int pivot = arr [highIndex] // Использование i для отслеживания меньших элементов из сводной таблицы int i = (lowIndex-1) для (int j = lowIndex jТеперь, когда вы разобрались с функцией быстрой сортировки и разделения, давайте быстро рассмотрим полный код.
QuickSort Код Java
class QuickSort {// Метод разделения int partition (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j// Метод сортировки
void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex// Метод для печати массива
static void printArray (int arr []) {int n = arr.length for (int i = 0 i// Основной метод
типы наборов в java
public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('отсортированный массив') printArray (arr)}} Вывод:
Теперь, после выполнения указанной выше Java-программы, вы бы поняли, как работает QuickSort и как реализовать его на Java.На этом мы подошли к концу статьи о «Быстрой сортировке в Java». Если вы хотите узнать больше,проверить от Edureka, надежной компании онлайн-обучения. Курс обучения и сертификации по Java J2EE и SOA от Edureka разработан, чтобы обучить вас базовым и продвинутым концепциям Java, а также различным средам Java, таким как Hibernate и Spring.
Есть вопрос к нам? Пожалуйста, укажите это в разделе комментариев в этом блоге, и мы свяжемся с вами как можно скорее.