Существует ли алгоритм «двоичной сортировки»?

Question

Есть ли алгоритм сортировки, который называется "двоичная сортировка"? Как сортировка слиянием, сортировка выбора или другие виды сортировки, существует ли двоичная сортировка?

Answer 1

Это , это и есть двоичная сортировка вставок. Два очень похожи. Они оба квадратичные (O(n^2)) алгоритмы времени.

Оба алгоритма выполняют O(n log n) количество сравнений, но на практике вам также придется перемещать элементы, что сделает весь алгоритм квадратичным.

Answer 2

JDK использует "двоичную сортировку" для массивов <размер 32 в своем методе <code>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's 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;
    }
}

Answer 3

Бинарная сортировка - это очень быстрый алгоритм, который включает битовое тестирование.Он имеет один проход для каждого бита в сортируемом элементе.Для каждого прохода, если бит установлен, сортируемый элемент укладывается в один конец буфера.Если бит не установлен, то элемент укладывается на другом конце буфера.Начиная сортировку с младшего значащего бита и обрабатывая следующие биты в порядке возрастания, вы получите отсортированный список.Я написал один из них в начале 8086 года в 1983 году для шотландского департамента образования.Стив Питтс

Answer 4

Сортировка кучи - это алгоритм сортировки путем концептуализации бинарного дерева и выполнения его увеличения и уменьшения.Это можно сделать на месте.

Answer 5

Может быть двоичная сортировка, но фактический отсортированный массив должен быть в противоположном смысле (т. Е. Скажем, вы хотите отсортировать массив целых чисел в порядке возрастания ... для этого у вас должен быть фактический массив в порядке убывания.)

Answer 6

Не уверен, что вы ищете, но если вы ищете подходящий алгоритм двоичной сортировки, то вы хотите знать о ваших требованиях.Каждый алгоритм имеет свои сильные и слабые стороны.

Например, вы ищете алгоритм, который дает быструю среднюю производительность (например, поиск в куче) или производительность в наихудшем случае (самая медленная операция) (например, сбалансированное двоичное дерево).Некоторые из них медленные, если вам также нужно переходить от одного элемента к другому.Если вы выполняете много случайных операций, вы, вероятно, больше заинтересованы в средней производительности, но если вам необходимо убедиться, что любая операция выполняется быстрее, чем X миллисекунд, то вам может потребоваться другой алгоритм.Некоторые из них могут быть медленными, если вы всегда добавляете элементы в конец коллекции и т. Д.

Поэтому используйте Google для таких ключевых слов, как:

• Красно-черное дерево
• кучапоиск
• сбалансированных деревьев, например http://www.codeproject.com/KB/recipes/redblackcs.aspx?msg=931557

Все сводится к тому, что вам нужно.

Answer 7

У нас нет алгоритма двоичной сортировки, но у нас есть двоичный поиск по отсортированному массиву.

Answer 8

Существуют некоторые виды, которые включают разбиение на две части (сортировка слиянием), но я не верю, что существует сортировка, называемая именно "двоичная сортировка".