DOUG LLOYD: Also in CS50 wir gelernt, eine Vielzahl von Sortieren und Suchen Algorithmen. Und manchmal ist es sein kann, ein wenig schwierig zu halten verfolgen, was Algorithmus tut, was. Wir haben eigentlich nur Mager die Oberfläche zu, es gibt viele andere Such und Sortieralgorithmen. Also in diesem Video lassen nur ein paar Minuten in Anspruch nehmen um zu versuchen und zu destillieren jeder Algorithmus bis auf die Kernelemente so dass Sie die meisten erinnern kann wichtige Informationen über sie und in der Lage, das zu artikulieren Unterschiede, falls erforderlich. 

Die erste ist die Auswahl sortieren. Die Grundidee hinter Auswahl sort ist der kleinste unsortierte Element zu finden in einem Array und tauschen Sie sie mit der zunächst unsortierte Element des Arrays. Wir haben gesagt, dass die Worst-Case- Laufzeit der das war n quadriert. Und wenn Sie sich daran erinnern, warum möchten, nehmen Sie einen Blick auf die Auswahl sort Video. Die Best-Case-Laufzeit wird auch n quadriert. 

Bubble-Sort, die Idee dahinter, dass eine ist es, benachbarte Paare tauschen. Also das ist der Schlüssel, das Ihnen hilft erinnere mich an den Unterschied. Auswahl Sortierung, so weit, finden Sie das smallest-- Blase Sortierung Swap benachbarte Paare. Wir tauschen benachbarte Paare von Elementen, wenn sie sind nicht in Ordnung, die effektiv Blasen größeren Elementen auf der rechten Seite, und zur gleichen Zeit beginnt auch kleinere Elemente links zu bewegen. Das Worst-Case-Fall der Laufzeit der Bubble-Sort ist n quadriert. Die Best-Case-Laufzeit der Bubble-Sort ist n. Da in dieser Situation wir wissen nicht actually-- wir nicht brauchen, um nehmen Sie die Swaps überhaupt. Wir haben nur eine zu machen Pass für alle n-Elemente. 

In Insertion Sort, dem Grundidee dabei verlagert. Das ist das Stichwort für die Insertion sort. Wir werden einmal durch Schritt die Anordnung von links nach rechts. Und wie wir es tun, wir sind gehen, um Elemente zu verschieben Wir haben bereits gesehen, um Platz für kleinere, die irgendwo passen müssen zurück in die sortiert Teil. So bauen wir die sortierten Array ein Element nach dem anderen, von links nach rechts, und wir verschieben die Dinge um Platz zu schaffen. Das Worst-Case-Laufzeit Insertion Sort ist n quadriert. Die Best-Case-Laufzeit ist n. 

Merge sort-- dem Schlüsselwort Hier wird geteilt und zusammenzuführen. Wir teilen Sie die ganze Palette, ob es sechs Elemente, acht Elemente, 10.000 elements-- wir sie aufteilen um die Hälfte, die Hälfte, die Hälfte, bis wir unter Array n ein Element-Arrays. Ein Satz von n ein Element-Arrays. Also mit einem begannen wir 1000-Elementanordnung, und wir an den Punkt gelangen, wo wir haben 1.000 Ein-Element-Arrays. Dann beginnen wir, diese Unterfelder zusammenführen wieder zusammen in der richtigen Reihenfolge. Also nehmen wir zwei Ein-Element-Arrays und erstellen Sie ein Array mit zwei Elementen. Wir nehmen zwei Zwei-Element-Arrays und erstellen Sie ein Vier-Element-Array und so weiter und so weiter, bis wir wieder aufgebaut einer n Elementanordnung. 

Das Worst-Case-Laufzeit Mergesort n mal log n. Wir haben n Elemente, aber Diese Rekombination Prozess nimmt log n Schritten zur Bewertung erhalten zurück auf eine vollständige Palette. Im besten Fall die Laufzeit ist auch n log n, da dieser Prozess nicht wirklich egal, ob die Anordnung war sortiert oder nicht, mit zu beginnen. Das Verfahren ist das gleiche, es ist keine Möglichkeit, Kurzschluss Dinge. SO n log n im schlimmsten Fall, n log n im besten Fall. 

Wir sprachen über zwei Suchalgorithmen. So lineare Suche ist etwa Iteration. Wir gehen über das Array einmal, von links nach rechts, versuchen, die Zahl zu finden dass wir suchen. Das Worst-Case-Laufzeit ist ein großes O n. Es könnte uns zu nehmen Iteration für jedes einzelne Element um das Element wir zu finden für die entweder in der letzten Position, oder gar nicht. Aber wir können nicht bestätigen, dass bis wir haben alles angesehen. m das Best-Case, so finden wir sofort. Die Best-Case-Laufzeit lineare Suche ist Omega von 1. 

Schließlich gab es binäre Suche, was erfordert, sortierten Array. Denken Sie daran, das ist eine sehr wichtige Überlegung bei der Arbeit mit binären Suche. Es ist eine Voraussetzung, um mit es-- das Array, das Sie durch suchen muss sortiert werden. Andernfalls wird das Keyword- ist teile und herrsche. Teilen Sie das Array in der Mitte und beseitigen Hälfte der Elemente jedes Mal, wenn Sie durch gehen. Aufgrund dieser Teile und Herrsche und Spaltung Dinge im Halb Ansatz, das Worst-Case-Laufzeit der binären Suche ist log n, das im wesentlichen besser als lineare Suche von n. Die Best-Case-Laufzeit ist immer noch einer. 

Wir könnten sie sofort das finden Erstmals machen wir eine Sparte, aber, wieder daran erinnern, dass obwohl binäre Suche ist wesentlich besser als lineare Suche aufgrund des Seins log n gegen n, Sie haben könnten, um durch die Arbeit zu gehen Sortier Ihr Array erste, was könnte es weniger wirksam, je von der Größe der Iteration sortiert. 

Ich bin Doug Lloyd, ist dies CS50.