Gibt es einen "binären Sortier" -Algorithmus?

Question

Gibt es einen Sortieralgorithmus namens "binary sort"? Wie merge sort, selection sort oder die anderen Arten der Sortierung existiert eine binäre Sortierung?

Answer 1

Es gibt this und es gibt binary insertion sort. Die beiden sind ziemlich ähnlich. Sie sind beide quadratische (O(n^2)) Zeitalgorithmen.

Beide Algorithmen tun O(n log n) Anzahl der Vergleiche, aber in der Praxis müssten Sie auch Elemente bewegen, die den gesamten Algorithmus quadratisch machen würde.

Answer 2

Es gibt einige Arten, die das Teilen in zwei Peices beinhalten (merge sort), aber ich glaube nicht, dass es eine Sorte gibt, die genau "binary sort" genannt wird.

Answer 3

Wir haben keinen binären Sortieralgorithmus, aber wir haben eine binäre Suche in einem sortierten Array.

Answer 4

Nicht sicher, wonach Sie suchen, aber wenn Sie nach einem geeigneten binären Sortieralgorithmus suchen, dann sollten Sie sich Ihrer Anforderungen bewusst sein. Jeder Algorithmus hat seine eigenen Stärken und Schwächen. Suchen Sie beispielsweise nach einem Algorithmus, der die schnellste durchschnittliche Leistung (z. B. die Heap-Suche) oder die schnellste Leistung im schlechtesten Fall (langsamste Operation) liefert (z. B. balancierter Binärbaum). Einige sind langsam, wenn Sie auch von einem Element zum nächsten iterieren müssen. Wenn Sie viele zufällige Operationen ausführen, sind Sie wahrscheinlich eher an der durchschnittlichen Leistung interessiert. Wenn Sie jedoch sicherstellen müssen, dass jede Operation schneller als X Millisekunden ist, sollten Sie einen anderen Algorithmus verwenden. Einige können langsam sein, wenn Sie immer Einzelteile am Ende der Auflistung hinzufügen usw.

haben also eine Google nach Schlüsselwörtern wie:

• Red schwarz Baum
• Haufen Suche
• ausgeglichene Bäume, z.B. http://www.codeproject.com/KB/recipes/redblackcs.aspx?msg=931557

Es kommt alles auf was Sie brauchen.

Answer 5

Eine binäre Sortierung ist ein sehr schneller Algorithmus, der Bit-Tests beinhaltet. Es hat einen einzigen Durchlauf für jedes Bit in dem sortierbaren Gegenstand. Wenn das Bit gesetzt ist, wird das sortierbare Element an jedem Ende des Puffers gestapelt. Wenn das Bit nicht gesetzt ist, wird das Element am anderen Ende des Puffers gestapelt. Das Starten der Sortierung mit dem niedrigstwertigen Bit und das Behandeln der nächsten Bits in aufsteigender Reihenfolge ergibt die sortierte Liste. Ich schrieb eines davon Anfang 8086 im Jahre 1983 für das Scottish Education Department. Steve Pitts

Answer 6

Das JDK verwendet eine "binäre Sortierung" für Arrays < Größe 32 innerhalb seiner Arrays.sort() -Methode. Hier ist der Code von 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 7

Es kann eine binäre Art sein, aber die tatsächliche Anordnung sollte in entgegengesetzter Richtung sortiert werden. (Dh Sagen Sie ein Array von ganzen Zahlen in aufsteigender Reihenfolge sortiert werden sollen ... für die , müssen Sie das tatsächliche Array in absteigender Reihenfolge haben.)

Answer 8

Heap Sortierung ist ein Sortieralgorithmus durch die Konzeption eines binären Baumes und tun, sieben und dann sieben auf sie. Es kann an Ort und Stelle erfolgen.