Dichotome Suche implementieren
Die binäre Suchmethode erfordert eine geordnete Sequenz im Array. Binäre Suche ist mehr als lineare Suche: Je mehr Elemente das Array ist, desto offensichtlicher ist die Effizienz. Die Effizienz der binären Suche wird ausgedrückt: O (log2n) n befindet sich im M -Leistungsbereich von 2, sodass die maximale Anzahl von Suchvorgängen M. log2n bedeutet, dass die M -Leistung von 2 gleich N ist, die Konstante auslässt und als O (logn) abgekürzt wird (logn) abkürzt.
Wenn es ein geordnetes Array von 200 Elementen gibt, dann die maximale Anzahl binärer Suchanfragen:
2^7 = 128, 2^8 = 256, es ist ersichtlich, dass die Leistung von 7 nicht 200 und die Leistung von 8 enthält, sodass die maximale Anzahl von Suchvorgängen gleich 8 ist
// Schleife, binäre Suche statische int Binarysearch (int [] Array, int data) {int start = 0; int End = array.length - 1; int Mid = -1; while (start <= end) {System.out.println ("Anzahl der Suchvorgänge"); Mid = (Start + Ende) >>> 1; if (Array [Mid] <data) {start = Mid + 1; } else if (Array [Mid]> Daten) {end = Mid - 1; } else {return Mid; } System.out.println ("start ="+start+", end ="+end+", Mid ="+Mid); } return -1; } // rekursive binäre Suche initial start = 0, end = array.length - 1 statische int binarysearch4Recursion (int [] array, int data, int start, int End) {int Mid = -1; System.out.println ("Anzahl der Suchanfragen"); if (start> Ende) {return Mid; } Mid = (Start + Ende) >>> 1; if (Array [Mid] <data) {return binarySearch4Recursion (Array, Daten, Mid + 1, Ende); } else if (Array [Mid]> Daten) {return binarySearch4Recursion (Array, Daten, Start, Mid - 1); } else {return Mid; }}Dichotome Insertion -Sortierung
Es gibt eine Sequenz a [0], a [1] ... a [n]; Wo ein [I-1] bereits vor ihm bestellt ist. Verwenden Sie beim Einfügen A [i] Dichotomie, um nach der Position einer [i] Insertionseffizienz zu suchen: O (n^2). Bei anfänglichen im Grunde genommen geordneten Sequenzen ist die Effizienz nicht so gut wie die direkte Sortierung der direkten Einfügung. Bei zufälligen und ungeordneten Sequenzen ist die Effizienz höher als die direkte Sortierung der direkten Einfügung.
/** Bipartit (gefaltet und halb) Insertionssortier* a Sequenz a [0], a [1] ... a [n]; Wo ein [I-1] bereits vor ihm bestellt ist. Wenn ein [i] eingefügt wird, verwenden Sie Dichotomie, um nach der Position einer [i] Insertion*/ öffentliche Klasse BinaryInsertSort {public static void Main (String [] args) {int len = 10; int [] ary = new int [len]; Random random = new random (); für (int j = 0; j <len; j ++) {ary [j] = random.nextint (1000); } binaryInsert (ary); / * * Komplexitätsanalyse: Im besten Fall müssen alle sortiert wurden, es besteht keine Notwendigkeit, sich richtig zu bewegen. Zu diesem Zeitpunkt lautet die Zeitkomplexität: O (n lg n) Der schlimmste Fall ist alle umgekehrten Reihenfolge, und zu diesem Zeitpunkt ist die Komplexität o (n^2) * Die Komplexität des schlimmsten Falls kann nicht verbessert werden auf o (n | logn). */ // Das Array PrintArray (Ary) drucken; } / *** sortieren* @param ary* / private static void binaryInsert (int [] ary) {int setvalueCount = 0; // Sortieren aus dem zweiten Element des Arrays, da das erste Element selbst nach (int j = 1; j <ary.length; j ++) {// Komplexität n // den aktuellen Wert int key = ary [j] speichern muss; // ∆ Use binary search to locate the insertion position// int index = binarySearchAsc(ary, ary[j], 0, j - 1);// Complexity: O(logn) // int index = binarySearchDesc(ary, ary[j], 0, j - 1);// Complexity: O(logn) int index = binarySearchDesc2(ary, ary[j], 0, j - 1); // Komplexität: o (logn) printArray (ary); System.out.println ("" +j +"-Indexes, die an der Position eingefügt werden sollen:" +Index); // das Ziel in die Position einfügen und das Element rechts von der Zielposition gleichzeitig nach (int i = j; i> index; i--) {// Komplexität, schlimmster Fall: (n-1)+(n-2)+...+n/2 = O (n^2) Ary [i] = ary [i-1] verschieben; // I-1 <==> Index setValueCount ++; } ary [index] = key; setvalueCount ++; } System.out.println ("/n Anzahl der Werte (setValuecount) =====>" + setValueCount); } / *** Binärsuche aufsteigende Rekursion** @param a ary* Angesichts des sortierten Array, das nachschlagen soll {int range = to - von; // Wenn der Bereich größer als 0 ist, dh es gibt mehr als zwei Elemente, teilen Sie weiter, wenn (Bereich> 0) {// das Zwischenbit int Mid = (bis + von) / 2 auswählen; // Wenn das kritische Bit nicht erfüllt ist, suchen Sie weiterhin binär, wenn (Ary [Mid]> Ziel) {/ * * MID> Target, aufsteigende Regel, das Ziel ist kleiner und die Position sollte ausgetauscht werden, dh, das Ziel wird an der mittleren Position positioniert. } else { / * * Mid <Ziel, aufsteigende Regel, Ziel ist groß und es werden keine Positionen ausgetauscht. Die Startposition für die Suche nach dem Vergleich sollte Mid + 1 */ Return BinarySearchasc (Ary, Target, Mid + 1, to) sein; }} else {if (ary [from]> target) {// Zum Beispiel 5,4, der eins -Einfügen ist 4 zurück; } else {return von + 1; }}} / *** Binärer Suche absteigender Reihenfolge, rekursiv* / private statische int -binarysearchDesc (int [] ary, int target, int von, int to) {int range = to - von; if (Bereich> 0) {int Mid = (von + bis) >>> 1; if (ary [Mid]> Ziel) {return binarySearchDesc (ary, target, Mid + 1, to); } else {return binarySearchDesc (Ary, Ziel, von, Mitte - 1); }} else {if (ary [von]> Ziel) {// Zum Beispiel 5,4, was eingefügt werden soll, ist 4 Return ab + 1; } else {return from; }}} / *** Binärer Suche absteigender Reihenfolge, nicht recursive* / private statische intarysearchDesc2 (int [] ary, int target, int von, int to) {// while (von <nach) {für (; von <von <bis;) {int Mid = (von + bis) >>>> 1; if (ary [Mid]> Ziel) {from = Mid + 1; } else {to = Mid -1; }} // von <==> bis; if (ary [from]> target) {// if 5,4, der eins zum Einfügen ist 4 Return von + 1; } else {return from; }} private static void printArray (int [] ary) {für (int i: ary) {System.out.print (i + ""); }}}918 562 442 531 210 216 931 706 333 132 Die Position der Insertion des Elements am ersten Index beträgt: 1 918 562 442 531 210 216 931 706 333 132 Die Position des Insertion des Elements am zweiten Index ist: 2 918 562 442 442 442 531 531 210 216 93133 32 442 442 531 531 531 210 216 93133 32 32 442 442 531 531 210 210 216 933 32 32 32 442 442 531 531 210 210 216 933 32 32 32 442 442 531 531 210 210 216 933 32 32 32 442 442 531 531 210 210 216 933 32 32 32 442 442 531 531 210 216 Die Einfügung des Elements in den dritten Index ist: 2 918 562 531 442 210 216 931 706 333 132 Die Position der Insertion des Elements am vierten Index ist: 4 918 562 531 442 210 216 931 706 333 132 Die Position des Insertion des Elements auf dem fünften Index. 931 706 333 132 Die Position der Insertion des Elements im sechsten Index beträgt: 0 931 918 562 531 442 216 210 706 333 132 Die Position der Insertion des Elements im siebten Index ist: 2 931 918 706 531 442 216 3333333333333333332 Die Position der Position des E -16 210 333333332 132 Die Position der Position des E -16 -INDECT -INS -INSERTUME auf dem E -216 -INDECT. 931 918 706 562 531 442 333 216 210 132 Der Ort, an dem das Element am 9. Index eingefügt werden soll, ist: 9: 9
SetvalueCount =====> 24
931 918 706 562 531 442 333 216 210 132