Geschriebene Interviews umfassen häufig verschiedene Algorithmen. In diesem Artikel wird kurz einige häufig verwendete Algorithmen vorgestellt und sie in JavaScript implementiert.
1. Sortieren einfügen
1) Einführung in den Algorithmus
Die Algorithmusbeschreibung von Insertion-Sort ist ein einfacher und intuitiver Sortieralgorithmus. Es erstellt eine geordnete Sequenz, für unortheilte Daten, nach hinten und vorwärts in der sortierten Sequenz nach vorne, die entsprechende Position finden und einfügen. Bei der Implementierung der Insertionssortierung wird normalerweise die Sortierung von Einstellungen verwendet (dh der zusätzliche Raum von O (1) ist erforderlich). Während des Scanprozesses von hinten nach vorne müssen die sortierten Elemente wiederholt nach hinten bewegt werden, um Einfütungsraum für die neuesten Elemente bereitzustellen.
2) Algorithmusbeschreibung und Implementierung
Im Allgemeinen wird die Insertionssortierung in einem Array mit Innenplatzin implementiert. Der spezifische Algorithmus wird wie folgt beschrieben:
Ausgehend vom ersten Element kann das Element als sortiert angesehen werden.
Nehmen Sie das nächste Element heraus und scannen Sie in der bereits sortierten Sequenz von Elementen rückwärts und leiten Sie sie weiter.
Wenn das Element (sortiert) größer ist als das neue Element, bewegen Sie das Element auf die nächste Position.
Wiederholen Sie Schritt 3, bis das sortierte Element gefunden wird, wo das neue Element geringer ist als oder gleich;
Nach dem Einfügen eines neuen Elements in diese Position;
Wiederholen Sie die Schritte 2 bis 5.
Implementierung von JavaScript -Code:
Funktion InsertionsSort (Array) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array') {for (var i = 1; i <array.Length; i ++) {var key = array [i]; var j = i - 1; while (j> = 0 && array [j]> taste) {array [j + 1] = array [j]; J--; } Array [j + 1] = key; } return Array; } else {return 'Array ist kein Array!'; }}3) Algorithmusanalyse
Bester Fall: Eingangsarrays sind in aufsteigender Reihenfolge sortiert. T (n) = o (n)
Schlimmster Fall: Das Eingabestand ist in absteigender Reihenfolge sortiert. T (n) = o (n2)
Durchschnitt: t (n) = o (n2)
Zwei, binäre Insertion -Sortier
1) Einführung in den Algorithmus
Die Sortierung von Binary-Insert-Sorts ist ein Sortieralgorithmus, der geringfügige Änderungen am direkten Sortieralgorithmus für Insertion vornimmt. Der größte Unterschied zwischen IT und dem direkten Insertions -Sortieralgorithmus besteht darin, dass bei der Suche nach Insertionspositionen die binäre Suchmethode verwendet wird, die eine gewisse Geschwindigkeitsverbesserung aufweist.
2) Algorithmusbeschreibung und Implementierung
Im Allgemeinen wird die Insertionssortierung in einem Array mit Innenplatzin implementiert. Der spezifische Algorithmus wird wie folgt beschrieben:
Ausgehend vom ersten Element kann das Element als sortiert angesehen werden.
Nehmen Sie das nächste Element heraus und finden Sie die Position der ersten Zahl größer als in der bereits sortierten Sequenz von Elementen.
Nach dem Einfügen eines neuen Elements in diese Position;
Wiederholen Sie die obigen zwei Schritte.
Implementierung von JavaScript -Code:
Funktion BinaryInsertionsSort (Array) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array') {for (var i = 1; i <array.Length; i ++) {var key = array [i], links = 0, rechts = i - 1; while (links <= rechts) {var Middle = parseInt ((links + rechts) / 2); if (Schlüssel <Array [Mitte]) {rechts = Mitte - 1; } else {links = Middle + 1; }} für (var j = i-1; j> = links; j--) {Array [j + 1] = array [j]; } Array [links] = Schlüssel; } return Array; } else {return 'Array ist kein Array!'; }}3) Algorithmusanalyse
Bester Fall: t (n) = o (nLogn)
Schlimmster Fall: t (n) = o (n2)
Durchschnitt: t (n) = o (n2)
3. Wählen Sie Sortieren
1) Einführung in den Algorithmus
Die Selektionssort ist ein einfacher und intuitiver Sortieralgorithmus. Wie es funktioniert: Finden Sie zuerst das kleinste (große) Element in der ungeortierten Sequenz, speichern Sie es an der Startposition der sortierten Sequenz, suchen Sie dann weiter nach dem kleinsten (großen) Element aus den verbleibenden, ungedeckten Elementen und platzieren Sie es dann am Ende der sortierten Sequenz. Und so weiter, bis alle Elemente sortiert sind.
2) Algorithmusbeschreibung und Implementierung
Die direkte Auswahl von N-Datensätzen kann über N-1-Pässe erhalten werden, um sie direkt auszuwählen und zu sortieren. Der spezifische Algorithmus wird wie folgt beschrieben:
Anfangszustand: Der ungeordnete Bereich ist R [1..N] und der geordnete Bereich ist leer;
Wenn die I-te Order (i = 1,2,3 ... n-1) beginnt, sind die aktuell geordneten und ungeordneten Bereiche r [1..i-1] bzw. r (i..n). Diese Bestellung wählt den Datensatz R [k] mit dem kleinsten Schlüsselwort aus dem aktuellen nicht ordnungsgemäßen Bereich aus und wechselt es mit dem ersten Datensatz R des nicht ordneten Bereichs, so dass R [1..] und R [i+1..n) zu einer neuen geordneten Fläche werden, wobei eine Erhöhung der Anzahl der Aufzeichnungen und eine neue, ungeordnete Fläche mit einer Abnahme der Anzahl der Aufzeichnungen wird.
Die N-1-Reise endet und das Array wird bestellt.
Implementierung von JavaScript -Code:
Funktion SelectionsOrt (Array) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array') {var len = array.length, temp; für (var i = 0; i <len - 1; i ++) {var min = array [i]; für (var j = i+1; j <len; j ++) {if (Array [j] <min) {temp = min; min = Array [j]; Array [j] = temp; }} Array [i] = min; } return Array; } else {return 'Array ist kein Array!'; }}3) Algorithmusanalyse
Bester Fall: t (n) = o (n2)
Schlimmster Fall: t (n) = o (n2)
Durchschnitt: t (n) = o (n2)
4. Blasensortierung
1) Einführung in den Algorithmus
Bubble -Sortierung ist ein einfacher Sortieralgorithmus. Es besucht wiederholt die zu sortierenden Sequenzen, vergleicht zwei Elemente gleichzeitig und tauscht sie aus, wenn sie falsch sind. Die Arbeit zum Besuch der Sequenz wird wiederholt, bis kein Austausch benötigt wird, dh die Sequenz wurde sortiert. Der Ursprung dieses Algorithmus liegt daran, dass je kleiner das Element über den Austausch langsam "schwimmt".
2) Algorithmusbeschreibung und Implementierung
Der spezifische Algorithmus wird wie folgt beschrieben:
Vergleichen Sie benachbarte Elemente. Wenn der erste größer als der zweite ist, tauschen Sie zwei von ihnen aus;
Führen Sie das gleiche Werk für jedes Paar benachbarte Elemente von Anfang des ersten Paares bis zum Ende des letzten Paares aus, damit das letzte Element die größte Zahl sein sollte.
Wiederholen Sie die obigen Schritte für alle Elemente mit Ausnahme des letzten;
Wiederholen Sie die Schritte 1 bis 3, bis die Sortierung abgeschlossen ist.
Implementierung von JavaScript -Code:
Funktion Bubblesort (Array) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array') {var len = array.length, temp; für (var i = 0; i <len - 1; i ++) {für (var j = len - 1; j> = i; j--) {if (array [j] <array [j - 1]) {temp = array [j]; Array [j] = Array [j - 1]; Array [j - 1] = temp; }}} return Array; } else {return 'Array ist kein Array!'; }}3) Algorithmusanalyse
Bester Fall: t (n) = o (n)
Schlimmster Fall: t (n) = o (n2)
Durchschnitt: t (n) = o (n2)
5. Schnelle Sorte
1) Einführung in den Algorithmus
Die Grundidee der schnellen Sortierung: Teilen Sie die Datensätze, die in zwei unabhängigen Teilen sortiert werden sollen, durch eine Bestellung, und die Schlüsselwörter einiger Datensätze sind kleiner als die des anderen Teils. Dann können die beiden Datensätze weiter sortieren, um die Reihenfolge der gesamten Sequenz zu erreichen.
2) Algorithmusbeschreibung und Implementierung
Schnellsortieren verwendet die Trennmethode, um eine Zeichenfolge in zwei Unterlisten zu unterteilen. Der spezifische Algorithmus wird wie folgt beschrieben:
Ein Element aus der Sequenz zu wählen, wird als "Prinzip" bezeichnet (Pivot);
Nachdenken Sie die Sequenz, alle Elemente mit kleinerem als den Referenzwert werden vor der Referenz platziert, und alle Elemente mit größerem Referenzwert werden hinter der Referenz platziert (dieselbe Zahl kann auf beiden Seiten platziert werden). Nachdem diese Partition beendet ist, befindet sich die Referenz in der Mitte der Sequenz. Dies wird als Partitionoperation bezeichnet;
Sortieren Sie die Teilsequenzen rekursiv kleiner als das Referenzelement und die Teilsequenzen größer als das Referenzelement.
Implementierung von JavaScript -Code:
// Methode One Function QuickSort (Array, links, rechts) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array' && typof links === 'number' && typeof rechts == 'Nummer') {if (links <rechts) {var x = array [rechts], i = links - 1, temp; temp; für (var j = links; j <= rechts; j ++) {if (Array [j] <= x) {i ++; temp = array [i]; Array [i] = Array [j]; Array [j] = temp; }} QuickSort (Array, links, i - 1); QuickSort (Array, i + 1, rechts); }; } else {return 'Array ist kein Array oder links oder rechts ist keine Nummer!'; }} var aaa = [3, 5, 2, 9, 1]; QuickSort (AAA, 0, AAA.Length - 1); console.log (aaa); // Methode 2 var quicksort = function (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var links = []; var rechts = []; für (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {links.push (arr [i]); } else {rechts.push (arr [i]); }} return QuickSort (links) .Concat ([Pivot], QuickSort (rechts)); };3) Algorithmusanalyse
Bester Fall: t (n) = o (nLogn)
Schlimmster Fall: t (n) = o (n2)
Durchschnitt: t (n) = o (nLogn)
6. Heapsortierung
1) Einführung in den Algorithmus
Die Heap -Sortierung bezieht sich auf einen Sortieralgorithmus, der unter Verwendung der Heap -Datenstruktur entwickelt wurde. Das Stapeln ist eine Struktur, die ungefähr vollständig binärer Baum ist und die Eigenschaften des Stapelns erfüllt: Das heißt, der Schlüsselwert oder der Index eines untergeordneten Knotens ist immer kleiner als der übergeordnete Knoten.
2) Algorithmusbeschreibung und Implementierung
Der spezifische Algorithmus wird wie folgt beschrieben:
Die anfängliche Abfolge der zu sortierenden Schlüsselwörter (R1, R2 ... RN) ist in einen großen oberen Haufen konstruiert, was der anfängliche ungeordnete Bereich ist.
Tauschen Sie das Heap-Top-Element R [1] mit dem letzten Element R [n] aus, und zu diesem Zeitpunkt werden eine neue nicht ordnungsgemäße Region (R1, R2, ... RN-1) und eine neue geordnete Region (RN) erhalten, und R [1,2 ... n-1] <= R [N] ist zufrieden;
Da der neue Heap-Top R [1] nach dem Austausch gegen die Eigenschaften des Haufens verstoßen kann, ist es notwendig, den aktuellen ungeordneten Bereich (R1, R2, ... RN-1) an den neuen Haufen anzupassen und dann R [1] mit dem letzten Element des nicht ordneten Gebiets auszutauschen, um einen neuen, ungeordneten Bereich (R1, R2, Rn-2) und ein neuer ordnungsgester Bereich (RN-1, RN) zu erhalten. (RN-1, RN). Wiederholen Sie diesen Vorgang, bis die Anzahl der Elemente im geordneten Bereich N-1 ist und der gesamte Sortiervorgang abgeschlossen ist.
Implementierung von JavaScript -Code:
/*Methode Beschreibung: Heap -sortieren @param Array -Array Sortiert*/Funktion Heapsort (Array) {if (Object.Prototype.toString.call (Array) .Slice (8, -1) === 'Array') {// Heap var heapsize = Array.Length, temp; für (var i = math.floor (heapsize / 2); i> = 0; i--) {heapify (Array, i, heapsize); } // Heap-Sortierung für (var j = heapsize-1; j> = 1; j-) {temp = array [0]; Array [0] = Array [j]; Array [j] = temp; heapify (Array, 0, -heapsize); }} else {return 'Array ist kein Array!'; }}/ * Methode Beschreibung: Behalten Sie die Eigenschaften des heap @param arr array @param x array subscript @param len heapgröße */function heapify (arr, x, len) {if (Object.Prototype + 1, großste = x, temp; if (l <len && arr [l]> arr [größte]) {größte = l; } if (r <len && arr [r]> arr [größte]) {größte = r; } if (größte! = x) {temp = arr [x]; arr [x] = arr [größte]; arr [größte] = temp; heapifizieren (arr, groß, len); }} else {return 'arr ist kein Array oder x ist keine Nummer!'; }}3) Algorithmusanalyse
Bester Fall: t (n) = o (nLogn)
Schlimmster Fall: t (n) = o (nLogn)
Durchschnitt: t (n) = o (nLogn)
7. Bestellung
1) Einführung in den Algorithmus
Die Zusammenführungssortierung ist ein effektiver Sortieralgorithmus, der auf dem Zusammenführungsbetrieb basiert. Dieser Algorithmus ist eine sehr typische Anwendung von Kluft und Eroberung. Zusammenführungssortierung ist eine stabile Sortiermethode. Zusammenführen Sie die geordneten Untersequenzen, um eine vollständig geordnete Sequenz zu erhalten; das heißt, machen Sie jede Subsequenz erster Ordnung und dann die Subsequence -Segmente. Wenn zwei bestellte Tische in eine bestellte Tabelle verschmolzen werden, wird dieser 2-Wege-Zusammenschluss bezeichnet.
2) Algorithmusbeschreibung und Implementierung
Der spezifische Algorithmus wird wie folgt beschrieben:
Teilen Sie die Eingangssequenz der Länge n in zwei Untersequenzen der Länge n/2;
Diese beiden Untersequenzen werden getrennt zusammengeführt;
Zusammenführen die beiden sortierten Untersequenzen in eine endgültige sortierte Sequenz.
Implementierung von JavaScript -Code:
Funktion mergesort (Array, p, r) {if (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, p, q); mergesort (Array, q + 1, r); merge (Array, p, q, r); }} Funktion merge (Array, p, q, r) {var n1 = q - p + 1, n2 = r - q, links = [], rechts = [], m = n = 0; für (var i = 0; i <n1; i ++) {links [i] = array [p+i]; } für (var j = 0; j <n2; j ++) {rechts [j] = array [q + 1 + j]; } links [n1] = rechts [n2] = number.max_value; für (var k = p; k <= r; k ++) {if (links [m] <= rechts [n]) {Array [k] = links [m]; M ++; } else {Array [k] = rechts [n]; n ++; }}}3) Algorithmusanalyse
Bester Fall: t (n) = o (n)
Schlimmster Fall: t (n) = o (nLogn)
Durchschnitt: t (n) = o (nLogn)
8. Eimersortierung
1) Einführung in den Algorithmus
Das Prinzip der Bucket -Sortierung: Unter der Annahme, dass die Eingabedaten einheitlich verteilt sind, werden die Daten in eine begrenzte Anzahl von Eimer unterteilt, und jeder Eimer wird separat sortiert (es ist möglich, andere Sortieralgorithmen zu verwenden oder weiterhin eine rekursive Weise zu verwenden).
2) Algorithmusbeschreibung und Implementierung
Der spezifische Algorithmus wird wie folgt beschrieben:
Stellen Sie ein quantitatives Array als leerer Eimer ein;
Durch die Eingabedaten iterieren und die Daten nacheinander in den entsprechenden Eimer einfügen;
Sortieren Sie jeden Eimer, der nicht leer ist;
Spleißen Sie die sortierten Daten aus einem leeren Eimer.
Implementierung von JavaScript -Code:
/*Methode Beschreibung: Bucket sort @param Array Array @param num num numnnummer } var len = array.length, Buckets = [], result = [], min = max = array [0], regex = '/^[1-9]+[0-9]*$/', Space, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); für (var i = 1; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; } space = (max - min + 1) / num; für (var j = 0; j <len; j ++) {var index = math.floor ((Array [j] - min) / Raum); if (buckets [index]) {// nicht leerer Bucket, sortieren var k = buckets [index] .Length - 1; while (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = buckets [index] [k]; k--; } Buckets [Index] [k + 1] = Array [j]; } else {// leerer Bucket, initialisieren Sie Eimer [index] = []; Buckets [Index] .push (Array [j]); }} while (n <num) {result = result.concat (Buckets [n]); n ++; } Rückgabeergebnis; }3) Algorithmusanalyse
Im besten Fall der Bucket -Sortierung hängt die lineare Zeit O (n) von der zeitlichen Komplexität der Bucket -Sortierung von der Zeitkomplexität der Sortierung von Daten zwischen Eimer ab, da die zeitliche Komplexität anderer Teile O (n) beträgt. Je kleiner der Eimer geteilt ist, desto weniger Daten sind der Eimer, desto weniger Zeit benötigt es, um ihn zu sortieren. Der entsprechende Raumverbrauch wird jedoch zunehmen.
9. Sortierung zählen
1) Einführung in den Algorithmus
Die Zählsart ist ein stabiler Sortieralgorithmus. Die Zählsortierung verwendet ein zusätzliches Array C, wobei das i-te Element die Anzahl der Elemente mit einem Wert ist, der I im Array A sortiert wird. Laut Array C sind die Elemente in A an die richtige Position angeordnet. Es kann nur Ganzzahlen sortieren.
2) Algorithmusbeschreibung und Implementierung
Der spezifische Algorithmus wird wie folgt beschrieben:
Finden Sie die größten und kleinsten Elemente im Array, die sortiert werden sollen.
Zählen Sie die Anzahl der Male jedes Elements mit einem Wert von i im Array und speichern Sie es in das I-te-Array-Gegenstand C;
Ansammeln Sie alle Zählungen (ab dem ersten Element in C werden jedes Element und das vorherige Element hinzugefügt);
Umgekehrter Ziel -Ziel -Array: Stellen Sie jedes Element I in das C (i) -TH -Element des Neuarrays ein und subtrahieren Sie C (i) für jedes Element um 1.
Implementierung von JavaScript -Code:
Funktion countingsort (array) {var len = array.length, b = [], c = [], min = max = array [0]; für (var i = 0; i <len; i ++) {min = min <= array [i]? Min: Array [i]; max = max> = array [i]? Max: Array [i]; C [Array [i]] = C [Array [i]]? C [Array [i]] + 1: 1; } für (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } für (var k = len - 1; k> = 0; k--) {b [c [Array [k]] - 1] = Array [k]; C [Array [k]]-; } return b; }3) Algorithmusanalyse
Wenn das Eingangselement zwischen 0 und k Ganze ist, ist seine Laufzeit O (N + K). Die Sortierung des Zählers ist keine Vergleichssortierung, und die Sortiergeschwindigkeit ist schneller als jeder Vergleichssortieralgorithmus. Da die zum Zählen verwendete Länge des Arrays C vom Datenbereich im zu sortierten Array abhängt (gleich der Differenz zwischen den maximalen und minimalen Werten des Arrays, die sortiert werden sollen, plus 1), erfordert dies eine Menge Zeit und Speicher für Arrays mit einem großen Datenbereich.