Existe-t-il un algorithme de "tri binaire"?

Est-il un algorithme de tri qui est nommé "tri binaire"? Comme la fusion de tri, de sélection, de tri, ou les autres types de tri, on fait un tri binaire qui existent?

source d'informationauteur user355002

  1. 11

    Il y a cette et il y a des binaires le tri par insertion. Les deux sont assez similaires. Ils sont à la fois quadratique (O(n^2)) algorithmes temps.

    Les deux algorithmes ne O(n log n) nombre de comparaisons, mais dans la pratique, vous devez également avoir à déplacer les éléments autour, ce qui rendrait l'ensemble de l'algorithme quadratique.

  2. 4

    La JDK utilise un "tri binaire" pour les tableaux < taille 32, dans son Arrays.sort() méthode. Voici le code de 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;
    }
}
  3. 3

    Un tri binaire est un très algorithme rapide qui implique peu de tests. Il a un passe unique pour chaque bit dans la sortable élément. Pour chaque passage, si le bit est définie, alors la sortable élément est placé à une extrémité de la mémoire tampon. Si le bit n'est pas définie, alors l'élément est placé à l'autre extrémité de la mémoire tampon. Le démarrage de la sorte au bit le moins significatif et de traiter avec le prochain bits dans l'ordre croissant entraînera dans la liste triée. J'ai écrit un de ces sur un début de 8086 en 1983 pour les Écossais Département de l'Éducation.
    Steve Pitts

  4. 0

    Il y a une sorte de qui impliquent diviser en deux morceaux (merge sort) mais je ne crois qu'il y a une sorte appelle exactement "tri binaire".

  5. 0

    Nous n'avons pas de binaire algorithme de tri, mais nous avons une recherche binaire sur un tableau trié.

  6. 0

    Pas sûr de ce que vous cherchez, mais si votre recherche d'un binaire algorithme de tri ensuite, vous voulez être conscient de vos exigences. Chaque algorithme a ses propres forces et faiblesses.

    Par exemple, vous cherchez un algorithme qui donne le plus rapide des performances dans la moyenne (par exemple, tas de recherche) ou à jeun pire des cas (le plus lent de l'opération) la performance (par exemple équilibré arbre binaire). Certains sont lents, si vous aussi vous avez besoin pour effectuer une itération à partir d'un élément à l'autre. Si vous faites de nombreux aléatoire des opérations, vous êtes probablement plus intéressés dans la moyenne des performances, mais si vous avez un besoin pour s'assurer que toute l'opération est plus rapide que les X millisecondes, alors vous voudrez peut-être un algorithme différent. Certains peut être lent si vous avez toujours de l'ajout d'éléments à la fin de la collection etc.

    Ont donc un google pour des mots clés comme:

    Tout se résume à ce que vous avez besoin.

  7. 0

    Il peut y avoir un tri binaire, mais le tableau trié devrait être dans l'autre sens.(c'est à dire, Dites que vous voulez trier un tableau d'entiers dans l'ordre croissant...pour cela, vous devez avoir le tableau réel dans l'ordre décroissant.)

  8. 0

    Tas de tri est un algorithme de tri par la conceptualisation d'un arbre binaire et de faire des eipd et ensuite se déverser sur elle. Il peut être fait en place.