DOUG LLOYD: Więc w CS50 dowiedzieliśmy się o różnych sortowania i wyszukiwania algorytmy. A czasami może to być trochę trudne do utrzymania utwór z tego, co algorytm co robi. Mamy naprawdę tylko odtłuszczonego powierzchnię zbyt, istnieje wiele innych wyszukiwanie i algorytmów sortowania. Więc w tym filmie niech po prostu wziąć kilka minut spróbować i destylować każdy algorytm do jej podstawowych elementów tak można zapamiętać najbardziej Ważne informacje o nich i być w stanie artykułować różnice, jeśli to konieczne. 

Pierwszym z nich jest wybór rodzaju. Podstawową ideą wyboru rodzaju jest znaleźć najmniejszą niesegregowanych elementu w tablicy i zamień go z Pierwszy nieposortowane elementem tej tablicy. Powiedzieliśmy, że najgorszy uruchomić czas, który został n do kwadratu. A jeśli chcesz przypomnieć sobie, dlaczego się Spojrzenie na wideo wyboru sortowania. Czas pracy najlepszym przypadku jest również n do kwadratu. 

Sortowanie bąbelkowe, idea, że jeden jest, aby zamienić parę sąsiednich. Więc to jest klucz, który pomaga pamiętam różnicę tutaj. Wybór rodzaju jest, jak dotąd, znaleźć smallest-- bańki Sortowanie zamienić parę sąsiednich. Możemy zamienić parę sąsiednich elementów, jeśli są w porządku, co skutecznie pęcherzyki większe elementy do prawej, i w tym samym czasie również zaczyna przenieść mniejsze elementy do lewej strony. Najgorszy czas przypadku uruchomienia bubble rodzaju jest n do kwadratu. Czas pracy najlepszym przypadku bubble sort jest n. Ponieważ w tej sytuacji nie actually-- możemy nie muszą dokonywać żadnych swapów w ogóle. Mamy tylko do jednego przejść przez wszystkie n elementów. 

W wstawiania sortowanie, Podstawowym założeniem jest tu przeniesienie. To jest kluczowe dla Sortowanie przez wstawianie. Jedziemy do kroku raz przez tablica z lewej do prawej. A jak my jesteśmy zamiar przenieść elementy widzieliśmy już, aby zrobić miejsce dla mniejsze, które muszą zmieścić gdzieś sortowane się w tej części. Więc budujemy posortowaną tablicę jednym Element w czasie, od lewej do prawej, i przesuwać rzeczy, aby pokój. Najgorszy czas pracy Sortowanie przez wstawianie jest n do kwadratu. Najbardziej przypadku czas pracy jest n. 

Scalanie sort-- słowo kluczowe tutaj jest dzielenia i łączenia. Podzieliliśmy całą tablicę, czy jest to sześć elementów, osiem elementów, 10000 elements-- podzieliliśmy go w dół o połowę, o połowę, o połowę dopóki mamy pod tablicę n jednego elementu macierzy. Zestaw tablic n jednego elementu. Więc zaczęliśmy z jednym Tablica 1000 elementów, i dostać się do punktu, w którym mają jeden 1000 tablic elementów. Potem zaczynają się łączyć te tablice sub powrotem w prawidłowej kolejności. Więc bierzemy dwie tablice jednego elementu i stworzyć tablicę dwóch elementów. Bierzemy dwie tablice dwóch elementów i stworzyć tablicę czterech elementów i tak dalej i tak dalej, dopóki nie przebudowany jeden n element tablicy. 

Najgorszy czas pracy sortowanie przez scalanie znaczy n razy log n. Mamy n elementów, ale ten proces rekombinacji trwa log n kroków, aby uzyskać powrót do pełnej tablicy. Najlepszy przypadek czas pracy jest również n log n, ponieważ proces ten naprawdę nie ma obchodzi, czy tablica była sortowane, czy nie zacząć. Proces jest taki sam, to jest nie sposób krótkich rzeczy obwodów. Więc n log n w najgorszym przypadku, n log n w najlepszym przypadku. 

Rozmawialiśmy o dwóch poszukiwania algorytmów. Więc przeszukiwanie liniowe jest o iteracji. Wychodzimy naprzeciwko tablicy raz, od lewej do prawej, starając się znaleźć numer że szukamy. Najgorszy czas pracy jest duże O n. To może nas iteracji poprzek każdego elementu znaleźć element szukamy na, albo w ostatniej pozycji, lub wcale. Ale nie możemy potwierdzić, że do poznaliśmy już wszystko. M najlepszym razie możemy znaleźć natychmiast. Najbardziej przypadku czas pracy przeszukiwanie liniowe jest omega 1. 

Wreszcie, nie było przeszukiwanie binarne, która wymaga wyśmienitymi tablicę. Pamiętaj, że to bardzo istotnym czynnikiem podczas pracy z wyszukiwaniem binarnym. Jest to niezbędny warunek do korzystania it-- tablica, że ​​jesteś patrząc przez muszą być sortowane. W przeciwnym razie, słowo kluczowe jest dziel i rządź. Podzielić tablicę na pół, a wyeliminować pół elementów za każdym razem, jak przejść przez. Z powodu tej dziel i rządź i rzeczy, dzielenie na pół podejścia, czas pracy najgorszy od wyszukiwania binarnego log n, która jest zasadniczo lepiej niż liniowej wyszukiwania w n. Najbardziej przypadku czas pracy jest jeszcze jeden. 

Możemy go znaleźć natychmiast Pierwszy raz dokonać podziału, ale, ponownie, należy pamiętać, że choć wyszukiwania binarnego znacznie lepiej niż wyszukiwania liniowego dzięki temu, że w porównaniu do n log n, może trzeba przejść przez pracę sortowania swoją tablicę pierwszym, który może uczynić go mniej skuteczne w zależności o wielkości iteracji sortowane. 

Jestem Doug Lloyd, to CS50.