Алгоритм быстрой сортировки, признанный одним из 10 лучших алгоритмов 20-го века, является, пожалуй, наиболее эффективным из имеющихся алгоритмов сортировки. От его приложений в информатике до инженерии, астрономии, геометрии и т. Д. Алгоритм быстрой сортировки заслужил место как один из самых важных алгоритмов сортировки, о котором должен знать каждый инженер-программист.
В этой статье мы рассмотрим алгоритм быстрой сортировки в три раза.
1. Логика алгоритма
2. Его реализация
3. Его применение
1. Логика алгоритма быстрой сортировки
Алгоритм быстрой сортировки основан на подходе к решению проблем «разделяй и властвуй», когда проблема разбивается на несколько подзадач, затем каждая из этих отдельных подзадач решается, а конечный результат - это совокупность решений каждой подзадачи.
Разделение:
Учитывая несортированный массив размера N, алгоритм быстрой сортировки разделяет массив на две части, используя элемент K, в массиве в качестве точки поворота, сохраняя при этом ограничение, что все элементы в массиве слева от K меньше K, и все элементы в массиве справа от K больше K.
Пример: 2 1 3 0 5 10 7
На рисунке выше 5 это поворотный элемент K, который разделяет массив на две части.
Завоеватель:
После первоначального разделения несортированного массива на две части, быстрая сортировка возвращает ключевой элемент K, а затем снова разделяет каждую из двух разделенных частей. Он делает это постоянно, пока несортированный массив не будет разделен на подмассив размером 1, а затем объединит все элементы, чтобы получить отсортированный массив.
2. Реализация быстрой сортировки
Логика «разделяй и властвуй» может быть реализована программно с использованием концепции рекурсии.
Рекурсия - это просто процесс, при котором функция продолжает вызывать себя до тех пор, пока не будет выполнено базовое условие.
Реализацию алгоритма быстрой сортировки можно разделить на два простых шага.
1. Разбейте массив на разделы.
2. Сортировка массива рекурсивно.
Шаг 1. Разделите массив
Цель здесь состоит в том, чтобы разделить массив вокруг определенного элемента в массиве, при этом при делении массива мы должны поддерживать два ограничения
- Все элементы слева от элемента разделения меньше элемента разделения.
- Все элементы справа от элемента разделения больше элемента разделения.
Мы можем добиться разделения массива, выполнив следующие шаги
- Инициализируйте два указателя I и J, один указатель для начала массива и другой указатель для конца массива.
- Возьмите первый элемент в качестве элемента разделения, а затем манипулируйте всеми элементами в массиве вокруг выбранного элемента разделения.
- Начните с указателя I, если элемент массива в i меньше, чем элемент разделения, продолжайте увеличивать I, иначе остановитесь.
- Затем перейдите к указателю J, если элемент массива в J больше, чем элемент разделения, продолжайте увеличивать J, иначе остановитесь.
- если я указываю на элемент, больший, чем разделяющий элемент, а J указывает на элемент, меньший, чем разделяющий элемент, поменяйте местами элементы в I и J.
- Продолжайте выполнять указанные выше действия, пока пути указателей I и J не пересекутся, а затем прервитесь.
- Замените элемент, используемый для разделения, на элемент в позиции указателя J.
- Вернуть Дж.
Приведенный выше метод разделения обеспечивает наилучшее эффективное по времени решение O (log n) для решения ужасного вопроса собеседования по кодированию, заключающегося в нахождении K-го по величине элемента в данном массиве.
Шаг 2. Рекурсивно отсортируйте массив
Большая часть работы по реализации алгоритма быстрой сортировки заключается в разделении массива, сортировка затем может выполняться рекурсивно или итеративно. Здесь мы будем рекурсивно отсортировать массив.
Действия по сортировке массива
- Разбейте массив на разделы.
- Отсортируйте половину массива.
- Отсортируйте вторую половину массива.
- Рекурсивно продолжайте с шагов 1–3, пока не будет отсортирован весь массив.
3. Приложения быстрой сортировки.
Вот некоторые из немногих применений алгоритма быстрой сортировки.
- Используется метод сортировки внутренних массивов различных языков программирования, например метод сортировки основной системы Javascript Array.sort, метод сортировки коллекций Java и т. Д.
- Спортивные результаты упорядочены с помощью быстрой сортировки на основе соотношения побед и поражений.
- Алгоритм быстрой сортировки используется во многих научных симуляторах.
- Алгоритм быстрой сортировки также часто используется в коммерческих вычислениях.
- Используется в комбинаторическом поиске и т. Д.
Заключение
В этой статье мы изучили логику алгоритма быстрой сортировки, реализовали различные компоненты алгоритма, а также рассмотрели несколько его приложений.
Полный код реализации алгоритма быстрой сортировки можно найти здесь.
