Дан массив целых чисел. Отсортируйте массив методом быстрой сортировки.
Пример:
Input: array = [1,2,12,2,34,45,65,76,78,98,89] Output: [1,2,2,12,34,45,65,76,78,89,98]
БЫСТРАЯ СОРТИРОВКА
Анализ сложности:
- Временная сложность:
Лучшая временная сложность — O(logN)
Худшая временная сложность — O(n²)
- Пространственная сложность: O(1).
Дополнительное пространство не требуется, поэтому объемная сложность постоянна.
РЕШЕНИЕ :
function partition(arr, startIndex, endIndex) { const pivotVal = arr[endIndex];
// the pivot element let index = startIndex;
// begin iterate and swap for (let i = index; i < endIndex; i++) { if (arr[i] < pivotVal) { [arr[i], arr[index]] = [arr[index], arr[i]]; index += 1; } } // move `pivotVal` to the middle index and return middle index [arr[index], arr[endIndex]] = [arr[endIndex], arr[index]]; return index; } function quickSort(arr, startIndex, endIndex) { // Base case or terminating case if (startIndex >= endIndex) { return; } // Returns midIndex / pivot index let midIndex = partition(arr, startIndex, endIndex); // Recursively apply the same logic to the left and right subarrays quickSort(arr, startIndex, midIndex - 1); quickSort(arr, midIndex + 1, endIndex); } let arr = [-2, 4, 6, 3, 7, 2]; quickSort(arr, 0, arr.length - 1); console.log(arr); // [-2, 2, 3, 4, 6, 7]
Алгоритм:
Быстрая сортировка – это алгоритм сортировки, основанный на принципе разделяй и властвуй.
- Массив делится на подмассивы путем выбора основного элемента (элемента, выбранного из массива).
- При делении массива опорный элемент должен располагаться таким образом, чтобы элементы, меньшие опорной точки, оставались с левой стороны, а элементы, превышающие опорную, находились справа от опорной точки.
- Левый и правый подмассивы также разделяются с использованием того же подхода. Этот процесс продолжается до тех пор, пока каждый подмассив не будет содержать один элемент.
- На данный момент элементы уже отсортированы. Наконец, элементы объединяются в отсортированный массив.
Сложность быстрой сортировки
1. Сложности со временем
- Сложность в наихудшем случае [Big-O]:
O(n2)
Это происходит, когда выбранный опорный элемент является либо самым большим, либо самым маленьким элементом. - Это условие приводит к тому, что опорный элемент находится в крайнем конце отсортированного массива. Один подмассив всегда пуст, а другой подмассив содержит
n - 1
элементов. Таким образом, быстрая сортировка вызывается только для этого подмассива. - Однако алгоритм быстрой сортировки имеет лучшую производительность для разбросанных опорных точек.
- Сложность в лучшем случае [Big-omega]:
O(n*log n)
Это происходит, когда опорный элемент всегда является средним элементом или рядом со средним элементом. - Средняя сложность дела [Big-theta]:
O(n*log n)
Это происходит, когда вышеуказанные условия не выполняются.
2. космическая сложность
Сложность пространства для быстрой сортировки составляет O(log n)
.
Быстрая сортировка приложений
Алгоритм быстрой сортировки используется, когда
- язык программирования хорош для рекурсии
- сложность времени имеет значение
- сложность пространства имеет значение