Ich bin verschiedenen Algorithmus -Grundlagen ausgesetzt, seit ich die Datenstruktur gelernt habe, aber ich habe sie nie geübt, seit ich die Prüfung abgeschlossen habe. Als ich mich entwickelte, überprüfte ich auch, als ich es benutzte. Jetzt lerne ich JavaScript. Ich werde diese Zeit nehmen, um verschiedene grundlegende Algorithmen zu organisieren und Code in JS- bzw. PHP -Syntax zu schreiben.
1. Blasensortierung
Prinzip: Vergleichen Sie die angrenzenden Zahlen paarweise und tauschen Sie sie aus, um von klein bis groß oder groß nach klein zu sein. Nach einer Reise wird die größte oder kleinste Zahl in die letzte Ziffer ausgetauscht und dann von Anfang an bis zum zweiten bis zur letzten Ziffer vergleichen und austauschen.
Zeitkomplexität: Durchschnittlicher Fall: O (N2) Bester Fall: O (n) Worst -Fall: O (N2)
Raumkomplexität: o (1)
Stabilität: Stabil
// JavaScript Syntax var array = [23,0,32,45,56,75,43,0,34]; für (var i = 0; i <array.length; i ++) {var issort = true; für (var j = 0; j <array.length - 1 - i; j ++) {if (Array [j]> Array [j+1]) {issort = false; var temp = array [j]; Array [j] = Array [j + 1]; Array [j + 1] = temp; }} if (issort) {break; }} console.log (Array); <? php $ array = [23,0,32,45,56,75,43,0,34]; für ($ i = 0; $ i <count ($ array); $ i ++) {$ issort = true; für ($ j = 0; $ j <count ($ array) - 1; $ j ++) {if ($ array [$ j]> $ array [$ j+1]) {$ issort = false; $ temp = $ array [$ j]; $ array [$ j] = $ array [$ j + 1]; $ array [$ j + 1] = $ temp; }} if ($ issort) {break; }} var_dump ($ array);?>2. Einfache Auswahlsortierung
Prinzip: Wählen Sie durch Vergleich von NI-Schlüsselwörtern den Datensatz mit dem kleinsten Schlüsselwort aus N-I+1-Datensätzen und tauschen Sie ihn mit i (1 <= i <= n) th Records aus. Die Leistung der einfachen Sortierung der Selektion ist etwas besser als Blasensortierung.
Zeitkomplexität: Durchschnittlicher Fall: O (N2) Bester Fall: O (n) Worst -Fall: O (N2)
Raumkomplexität: o (1)
Stabilität: instabil
// JavaScript var array = [23,0,32,45,56,75,43,0,34]; für (var i = 0; i <array.length - 1; i ++) {var pos = i; für (var j = i+1; j <array.length; j ++) {if (Array [j] <array [pos]) {pos = j; }} var temp = array [i]; Array [i] = Array [pos]; Array [pos] = temp; } console.log (Array); <? php $ array = [23,0,32,45,56,75,43,0,34]; für ($ i = 0; $ i <count ($ array); $ i ++) {$ pos = $ i; für ($ j = $ i+1; $ j <count ($ array); $ j ++) {if ($ array [$ j] <$ array [$ pos]) {$ pos = $ j; }} $ temp = $ array [$ i]; $ array [$ i] = $ array [$ pos]; $ array [$ pos] = $ temp; } var_dump ($ array);?>3.. Fügen Sie die Sortierung direkt ein
Prinzip: Fügen Sie einen Datensatz in die sortierte geordnete Tabelle ein, wodurch eine neue geordnete Tabelle mit 1 Inkrementen von Datensätzen erhalten wird. Das heißt, behandeln Sie zuerst den ersten Datensatz der Sequenz als geordnete Subsequenz und fügen Sie sie dann einzeln aus dem zweiten Datensatz ein, bis die gesamte Sequenz geordnet ist. Bessere Leistung als Blasenmethode und Sortierung der Selektion
Zeitkomplexität: Durchschnittlicher Fall: O (N2) Bester Fall: O (n) Worst -Fall: O (N2)
Raumkomplexität: o (1)
Stabilität: Stabil
// JavaScript var array = [23,0,32,45,56,75,43,0,34]; für (var j = 0; j <array.length; j ++) {var key = array [j]; var i = j - 1; while (i> -1 && array [i]> taste) {array [i + 1] = array [i]; i = i - 1; } Array [i + 1] = Schlüssel; } console.log (Array); <? Php // direkt Sortieren $ array = [23,0,32,45,56,75,43,0,34] einfügen; für ($ i = 0; $ i <count ($ array); $ i ++) {$ key = $ array [$ i]; $ j = $ i - 1; while ($ j> -1 && $ array [$ j]> $ key) {$ array [$ j +1] = $ array [$ j]; $ j = $ j - 1; } $ array [$ j + 1] = $ key; } var_dump ($ array);?>4. Schnelle Sortierung
Prinzip: Durch eine Sortierung sind die zu sortierten Daten in zwei unabhängige Teile unterteilt, und alle Daten sind teilweise kleiner als alle Daten im anderen Teil, und dann werden die beiden Teile der Daten schnell nach dieser Methode sortiert. Der gesamte Sortierprozess kann rekursiv durchgeführt werden, um die gesamten Daten zu einer geordneten Sequenz zu erreichen.
Zeitkomplexität: Durchschnittlicher Fall: O (Nlog2n) Bester Fall: O (Nlog2n) Worst -Fall: O (N2)
Raumkomplexität: O (NLOG2N)
Stabilität: instabil
// JavaScript Quick Sort Var Array = [23,0,32,45,56,75,43,0,34]; var quicksort = function (arr) {if (arr.length <= 1) {return arr; } // Überprüfen Sie die Anzahl der Elemente im Array, wenn es kleiner oder gleich 1 ist, wird es zurückgegeben. var pivotIndex = math.floor (arr.length/2); // var pivot = arr.splice (pivotIndex, 1) [0]; // Wählen Sie "Benchmark" (Pivot) und trennen Sie es von dem ursprünglichen Array, var links = []; // zwei leere Arrays, um zwei Untersets von links zu speichern, und ein rechts rechts und ein rechts rechts. für (var i = 0; i <arr.length; i ++) // transweep das Array, geben Sie Elemente kleiner als der "Benchmark" in die Untergruppe links und Elemente, die größer als der Benchmark in die Teilmenge rechts sind. {if (arr [i] <pivot) {links.push (arr [i]); } else {rechts.push (arr [i]); }} return QuickSort (links) .Concat ([Pivot], QuickSort (rechts)); // Wiederholen Sie diesen Vorgang kontinuierlich, um das sortierte Array zu erhalten. }; var newArray = quicksort (Array); console.log (newArray); <? php $ array = [23,0,32,45,56,75,43,0,34]; Funktion Quick_Sort ($ arr) {// Bestimmen Sie zuerst, ob Sie $ length = count ($ arr) fortsetzen müssen; if ($ länge <= 1) {return $ arr; } $ base_num = arr [0]; // Wählen Sie ein Lineal aus, um das erste Element auszuwählen // zwei Arrays $ links_array = array (); // $ right_array weniger als der luler = array (); // für ($ i = 1; $ i <$ Länge; $ arr [$ i]) {// in das linke Array eingeben $ links_array [] = arr [$ i]; } else {// in die richtige $ right_array [] = $ arr [$ i]; }} // dann dieselbe Sortiermethode für die linken bzw. rechten Arrays // diese Funktion rekursiv aufrufen und das Ergebnis aufzeichnen $ links_array = Quick_Sort ($ links_array); $ Right_array = Quick_Sort ($ right_array); // Das linke Lineal mit dem rechten Rückgabearray_Merge ($ links_array, Array ($ Base_num), $ right_array) zusammenführen; } $ newArray = Quick_Sort ($ Array); var_dump ($ newArray);?>5. Hill Sort
Prinzip: Teilen Sie zunächst die gesamte Datensatzsequenz, die in mehrere Teilsequenzen sortiert werden soll, um direktes Einfügen und Sortieren zu sortieren. Wenn die Datensätze in der gesamten Sequenz "grundsätzlich bestellt" sind, fügen Sie die gesamten Datensätze nacheinander ein und sortieren Sie sie nacheinander. .
Zeitkomplexität: Durchschnittlicher Fall: O (N√n) Bester Fall: O (NLOG2N) Worst -Fall: O (N2)
Raumkomplexität: o (1)
Stabilität: instabil
// JavaScript Hill Sort Var Array = [23,0,32,45,56,75,43,0,34]; var Shellsort = Funktion (arr) {var length = arr.length; var H = 1; while (H <Länge/3) {H = 3*H+1; // Intervall} festlegen (h> = 1) {für (var i = h; i <Länge; i ++) {für (var j = i; j> = h && arr [j] <jh]; j- = h) {var temp = arr [jh]; arr [jh] = arr [j]; arr [j] = temp; }} H = (H-1)/3; } return arr; } var newarray = ShellSort (Array); console.log (newArray); <? Php // Hill Sort $ array = [23,0,32,45,56,75,43,0,34]; Funktion ShellSort ($ arr) {$ length = count ($ arr); $ H = 1; while ($ H <$ Länge/3) {$ H = 3*$ H+1; // INTIVAL SET} while ($ h> = 1) {für ($ i = $ H; $ i <$ länge; $ i ++) {für ($ j = $ I; $ arr [$ j- $ h] = $ arr [$ j]; $ arr [$ j] = $ temp; }} $ H = ($ H-1)/3; } $ arr; } $ newArray = ShellSort ($ Array); var_dump ($ newArray)?>6. Bestellung
Prinzip: Unter der Annahme, dass die anfängliche Sequenz N -Datensätze enthält, kann sie als N -geordnete Untersequenzen angesehen werden. Jede Untersequenz hat eine Länge von 1 und fusioniert dann zu paarweise (die kleinste ganze Zahl, die nicht weniger als n/2) mit einer Länge von 2 oder 1 wiederholt wird, bis ein geordnetes Subsequenz mit einer gewonnenen Länge zusammengesetzt ist.
Zeitkomplexität: Durchschnittlicher Fall: O (Nlog2n) Bester Fall: O (Nlog2n) Worst -Fall: O (Nlog2n)
Raumkomplexität: o (1)
Stabilität: Stabil
// JavaScript Merge -Sortierfunktion IsArray1 (arr) {if (Object.Prototype.toString.call (arr) == '[Objektarray]') {return true; } else {return false; }} Funktion merge (links, rechts) {var result = []; if (! isarray1 (links)) {links = [links]; } if (! isArray1 (rechts)) {rechts = [rechts]; } while (links.length> 0 && rechts.length> 0) {if (links [0] <rechts [0]) {result.push (links.Shift ()); } else {result.push (right.shift ()); }} return result.concat (links) .Concat (rechts); } Funktion mergesort (arr) {var len = arr.length; var lim, work = []; var i, j, k; if (len == 1) {return arr; } für (i = 0; i <len; i ++) {Work.push (arr [i]); } Work.push ([]); für (lim = len; lim> 1;) {// lim ist die Gruppierungslänge für (j = 0, k = 0; k <lim; j ++, k = k+2) {Arbeit [j] = merge (Arbeit [k], Arbeit [k+1]); } Arbeit [j] = []; lim = math.floor ((lim+1)/2); } Rückgabearbeit [0]; } var array = [23,0,32,45,56,75,43,0,34]; console.log (mergesort (array)); <? php // Sortierfunktion Mergesort (& $ arr) {$ len = count ($ arr); // das Array Länge-multiort ($ arr, 0, $ len-1) finden; } // Das Programm, das tatsächlich die Ferge -Sortierfunktion (& $ arr, $ links, $ rechts) implementiert, {if ($ links <$ rechts) {// Geben Sie an, dass es 1 zusätzliches Element in der Subquenz gibt, dann ist es notwendig, sich zu teilen, separat zu sortieren, merken // die geteilte Position, Länge /2 Gehen Sie zum gesamten $ center = floor ($ links) ($ links) / /2). // Rekursive Anruf sortiert die linke Seite erneut: mutesort ($ arr, $ links, $ center); // rekursiv anrufen, um die rechte Seite erneut zu sortieren ($ arr, $ center+1, $ rechts); // Die Sortierergebnisse mergearray zusammenführen ($ arr, $ links, $ center, $ rechts); }} // Kombinieren Sie zwei bestellte Nummern in eine bestellte Array -Funktion mergearray (& $ arr, $ links, $ center, $ rechts) {// Zwei Startposition Marke $ a_i = $ links; $ b_i = $ center+1; while ($ a_i <= $ center && $ b_i <= $ rechts) {// Wenn weder Array A noch Array B die Grenze überschreitet, if ($ arr [$ a_i] <$ arr [$ b_i]) {$ temp [] = $ arr [$ a_i ++]; } else {$ temp [] = $ arr [$ b_i ++]; }} // Beurteilen Sie, ob alle Elemente in Array A aufgebraucht sind. Wenn nicht, fügen Sie alle Elemente in Array C ein: while ($ a_i <= $ center) {$ temp [] = $ arr [$ a_i ++]; } // Beurteilen Sie, ob alle Elemente in Array B aufgebraucht sind. Wenn nicht, fügen Sie alle Elemente in Array C: while ($ b_i <= $ rechts) {$ temp [] = $ arr [$ b_i ++] ein; } // Schreiben Sie den sortierten Teil in $ arrc in $ arr: für ($ i = 0, $ len = count ($ temp); $ i <$ len; $ i ++) {$ arr [$ links+$ i] = $ temp [$ i]; }} $ arr = Array (23,0,32,45,56,75,43,0,34); mergesort ($ arr); var_dump ($ arr);?>7. Heapsortierung
Prinzip: Heapsortierung ist eine Sortiermethode mit dem Haufen. Die Grundidee besteht darin, die Sequenz zu konstruieren, die in einen großen oberen Haufen sortiert werden soll. Zu diesem Zeitpunkt ist der Maximalwert der gesamten Sequenz der Wurzelknoten der Oberseite des Haufens. Entfernen Sie es (in der Tat soll es mit dem Endelement des Heap-Arrays austauschen, und das Endelement ist der Maximalwert) und dann die verbleibenden N-1-Sequenzen in einen Haufen zu rekonstruieren, damit der Submaximum-Wert von N-Elementen erhalten wird. Dies führt zu einer wiederholten Ausführung und eine geordnete Sequenz kann erhalten werden.
Zeitkomplexität: Durchschnittlicher Fall: O (Nlog2n) Bester Fall: O (Nlog2n) Worst -Fall: O (Nlog2n)
Raumkomplexität: o (1)
Stabilität: instabil
// JavaScript Heap Sort Var Array = [23,0,32,45,56,75,43,0,34]; Funktion Heapsort (Array) {for (var i = math.floor (Array.Length / 2); i> = 0; i--) {Heapadjust (Array, i, Array.length-1); // Array-Array in einen großen oberen Heap} für (i = array.length-1; i> = 0; i--) {/*den Stammknoten*/var temp = array [i] auszutauschen; Array [i] = Array [0]; Array [0] = temp; /*Das verbleibende Array wird weiterhin in einen großen oberen Haufen integriert*/ heapadjust (Array, 0, i - 1); } return Array; } function Heapadjust (Array, Start, max) {var temp = array [start]; // temp ist der Wert des Root -Knotens für (var j = 2 * start; j <max; j * = 2) {if (j <max && array [j] <j+1]) {// das SubsScript von älteren Kindern ++ J; } if (temp> = array [j]) break; Array [Start] = Array [j]; start = j; } Array [start] = temp; } var newArray = heapsort (Array); console.log (newArray); <? Php // Heap -Sortierfunktion Heapsort (& $ arr) {#initheap ($ arr, 0, count ($ arr) - 1); #Starten Sie die Kopf- und Heckknoten aus und reduzieren Sie jeweils einen Endknoten und passen Sie den Haufen an, bis ein Element für ($ end = count ($ arr)-1; $ end> 0; $ End--) {$ temp = $ arr [0]; $ arr [0] = $ arr [$ end]; $ arr [$ end] = $ temp; ajustnodes ($ arr, 0, $ end - 1); }} #Initialisieren Sie den maximalen Heap, starten Sie vom letzten Nicht-Blattknoten, und der letzte Nicht-Blattknoten wird als Array-Länge/2-Runden-Funktion nummeriert, um initHeap (& $ arr) {$ len = count ($ arr); für ($ start = floor ($ len / 2) - 1; $ start> = 0; $ start--) {austnodes ($ arr, $ start, $ len - 1); }}#Ordnennodes#@param $ arr array anpassen#@param $ starten Sie die Koordinaten des übergeordneten Knotens an#@param $ beenden die Koordinaten des Endknotens an die anpassende Funktion ajustnode (& $ arr, $ start, $ end) {$ maxinx = $ start; $ len = $ End + 1; #Die Länge des zu angepassten Teils $ linkSchildinx = ($ start + 1) * 2 - 1; #Left Child Coordinate $ rightchildinx = ($ start + 1) * 2; #Right Child Coordinate #Wenn das zu angepasste Teil ein linkes Kind hat, wenn ($ linkSchildinx + 1 <= $ len) {#GET Die minimale Knotenkoordinate if ($ arr [$ maxinx] <$ arr [$ linksInx]) {$ maxinx = $ linkchildinx; } #Wenn der zu angepasste Teil hat einen richtigen untergeordneten Knoten if ($ rightchildinx + 1 <= $ len) {if ($ arr [$ maxinx] <$ arr [$ rightchildinx]) {$ maxinx = $ rightchildinx; }}} #Swap Parent Node und Maximum Node if ($ start! = $ Maxinx) {$ temp = $ arr [$ start]; $ arr [$ start] = $ arr [$ maxinx]; $ arr [$ maxinx] = $ temp; #Wenn der untergeordnete Knoten nach dem Austausch untergeordnete Knoten hat, passen Sie weiter an, wenn ($ maxinx + 1) * 2 <= $ len) {austnodes ($ arr, $ maxinx, $ end); }}} $ arr = array (23,0,32,45,56,75,43,0,34); Haufen ($ arr); var_dump ($ arr);?>8. Kardinalitätssortierung
Prinzip: Schneiden Sie Ganzzahlen nach Ziffern in verschiedene Zahlen und vergleichen Sie sie dann separat mit jeder Ziffer. Da Ganzzahlen auch Zeichenfolgen (wie Namen oder Daten) und Schwimmpunktzahlen in bestimmten Formaten ausdrücken können, wird die Radix-Sortierung nicht nur für Ganzzahlen verwendet.
Zeitkomplexität: Durchschnittlicher Fall: o (d (r+n)) Bester Fall: O (D (N+RD)) Worst -Fall: O (D (R+N)) R: Kardinalität der Schlüsselwörter D: Länge N: Anzahl der Schlüsselwörter
Raumkomplexität: O (Rd+N)
Stabilität: Stabil
<Php #blassorting, hier sind nur positive Ganzzahlen sortiert. In Bezug auf negative Zahlen und schwimmende Punktzahlen ist eine Komplement erforderlich. Sie sind daran interessiert, #counting sort #@param $ arr Array zu studieren #@@param $ digit_num sortiert gemäß der Anzahl der Funktionen der Funktion counting_sort (& $ arr, $ digit_num = false) {if ($ digit_num! count ($ arr); }} else {$ arr_temp = $ arr; } $ max = max ($ arr); $ time_arr = array (); #Storage -Array von Elementen Vorkommen#Initialisieren Sie das Vorkommen Array für ($ i = 0; $ i <= $ max; $ i ++) {$ time_arr [$ i] = 0; } #Statisieren Sie die Vorkommen jedes Elements für ($ i = 0; $ i <count ($ arr_temp); $ i ++) {$ time_arr [$ arr_temp); $ i ++) {$ time_arr [$ arr_temp [$ i]] ++; } #Statifizieren Sie die Vorkommen jedes Elements, das kleiner oder gleich ist für ($ i = 0; $ i <count ($ time_arr) - 1; $ i ++) {$ time_arr [$ i +1] += $ time_arr [$ i]; } #Sort Das Array unter Verwendung der Anzahl der Vorkommen für ($ i = count ($ arr) - 1; $ i> = 0; $ time_arr [$ arr_temp [$ i]]-; } $ arr = $ sorted_arr; KSORT ($ arr); #IGNORE Der Effizienzverlust der Schlüsselsortierung dieses Mals} #Calculate die Anzahl der Bits einer bestimmten Zahl -Funktion get_digit ($ number) {$ i = 1; while ($ number> = pow (10, $ i)) {$ i ++; } return $ i; } #GET Die I -Th -Ziffernnummer einer Nummer aus der einstelligen Funktion get_specific_digit ($ num, $ i) {if ($ num <pow (10, $ i - 1)) {return 0; } return floor ($ num % pow (10, $ i) / pow (10, $ i - 1)); } #Black sortieren, zählen sortieren als sortierprozessfunktion radix_sort (& $ arr) {#First finden Sie die größte Ziffer im Array $ max = max ($ arr); $ max_digit = get_digit ($ max); für ($ i = 1; $ i <= $ max_digit; $ i ++) {counting_sort ($ arr, $ i); }} $ arr = Array (23,0,32,45,56,75,43,0,34); radix_sort ($ arr); var_dump ($ arr);?>Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.