Есть ли алгоритм сортировки, который называется "двоичная сортировка"? Как сортировка слияния, сортировка выбора или другие виды сортировки, существует ли двоичная сортировка?
Здесь this и двоичная сортировка вставки. Оба довольно похожи. Они являются квадратными (O(n^2)) алгоритмами времени.
Оба алгоритма делают O(n log n) количество сравнений, но на практике вам также придется перемещать элементы вокруг, что сделало бы весь алгоритм квадратичным.
Двоичный сортировка - очень быстрый алгоритм, который включает в себя тестирование бит. Он имеет один проход для каждого бита в сортируемом элементе. Для каждого прохода, если бит установлен, сортируемый элемент укладывается на один конец буфера. Если бит не установлен, элемент складывается на другом конце буфера. Запуск сортировки по наименее значащему биту и обращение к следующим битам в порядке возрастания приведет к сортированному списку. Я написал один из них в начале 8086 года в 1983 году для Шотландского отдела образования. Стив Питтс
JDK использует "двоичную сортировку" для массивов < размер 32 в своем методе Arrays.sort(). Вот код от JDK7
private static void binarySort(Object[] a, int lo, int hi, int start) {
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
@SuppressWarnings("unchecked")
Comparable<Object> pivot = (Comparable) a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
*/
while (left < right) {
int mid = (left + right) >>> 1;
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that why this sort is stable.
* Slide elements over to make room for pivot.
*/
int n = start - left; // The number of elements to move
// Switch is just an optimization for arraycopy in default case
switch (n) {
case 2: a[left + 2] = a[left + 1];
case 1: a[left + 1] = a[left];
break;
default: System.arraycopy(a, left, a, left + 1, n);
}
a[left] = pivot;
}
}
Есть какой-то вид, который включает разделение на два сегмента (сортировка слияния), но я не верю, что существует сортировка, называемая точно "двоичная сортировка".
У нас нет двоичного алгоритма сортировки, но у нас есть бинарный поиск в отсортированном массиве.
Не уверен, что вы ищете, но если вы ищете подходящий алгоритм сортировки двоичных файлов, тогда вы хотите знать свои требования. У каждого алгоритма есть свои сильные и слабые стороны.
Например, вы ищете алгоритм, обеспечивающий самую быструю среднюю производительность (например, поиск кучи) или работу с наихудшим сроком работы (наименьшая работа) (например, сбалансированное двоичное дерево). Некоторые из них медленны, если вам также нужно перебирать один элемент на другой. Если вы делаете много случайных операций, вы, вероятно, больше заинтересованы в средней производительности, но если вам нужно обеспечить, чтобы любая операция была быстрее, чем X миллисекунд, тогда вам может понадобиться другой алгоритм. Некоторые могут быть медленными, если вы всегда добавляете элементы в конце коллекции и т.д.
Так что у вас есть такие ключевые слова, как:
Все сводится к тому, что вам нужно.
Может быть двоичный вид, но фактический отсортированный массив должен быть в противоположном смысле. (т.е. Скажем, вы хотите отсортировать массив целых чисел в порядке возрастания... для этого у вас должен быть фактический массив в порядке убывания.)
Сортировка кучи - это алгоритм сортировки путем концептуализации бинарного дерева и просеивания, а затем просачивания на него. Это можно сделать на месте.