DOUG LLOYD: Então, nós aprendemos sobre CS50 uma variedade de classificação e pesquisa algoritmos. E às vezes isso pode ser um pouco complicado para manter a par do que algoritmo faz o quê. Nós temos realmente apenas desnatado a superfície também, existem muitos outros pesquisa e algoritmos de ordenação. Portanto, neste vídeo, vamos apenas levar alguns minutos para tentar e destilar cada algoritmo para baixo a seus elementos centrais para que você possa lembrar o mais informações importantes sobre eles e ser capaz de articular a diferenças, se necessário. 

O primeiro é a seleção de classificação. A idéia básica por trás de seleção tipo é encontrar o menor elemento não triados em uma matriz e trocá-lo com o primeiro elemento não ordenado desse array. Nós dissemos que o pior caso tempo de execução do que foi n ao quadrado. E se você quiser recordar por que razão, tomar um olhar para o vídeo selecção de classificação. O tempo de execução do melhor caso é também n ao quadrado. 

Bubble sort, a idéia por trás disso um é trocar os pares adjacentes. Então, essa é a chave que ajuda você lembre-se a diferença aqui. Seleção tipo é, até agora, encontrar o bubble smallest-- Sort é trocar os pares adjacentes. Nós trocar pares adjacentes de elementos se estão fora de ordem, o que efetivamente Bolhas de elementos maiores para a direita, e, ao mesmo tempo que também começa para mover elementos menores para a esquerda. O pior caso de tempo caso de execução de bubble sort é n ao quadrado. O tempo de execução do melhor caso de bubble sort é n. Porque nessa situação nós não actually-- que talvez não seja necessário fazer quaisquer swaps em tudo. Nós só tem de fazer uma passar por todos os elementos n. 

Na ordenação por inserção, o idéia básica aqui está mudando. Essa é a palavra-chave para a inserção de classificação. Nós vamos para a etapa através de uma vez a matriz da esquerda para a direita. E como nós fazemos, nós somos vai mudar elementos já vimos para dar lugar a os menores que necessitam de um lugar para caber de volta em que parcela classificada. Então, nós construímos a matriz classificada uma elemento de cada vez, para a esquerda para a direita, e mudamos coisas para fazer o quarto. O tempo de execução do pior caso de ordenação por inserção é n ao quadrado. O melhor caso o tempo de execução é n. 

Mesclar sort-- a palavra-chave aqui é dividir e mesclar. Podemos dividir o conjunto completo, se é seis elementos, oito elementos, 10.000 elements-- nós dividi-lo para baixo pela metade, pela metade, pela metade, até que tenhamos sob matriz n de um elemento de matrizes. Um conjunto de matrizes n um elemento. Então começamos com uma 1000-elemento da matriz, e chegarmos ao ponto em que 1.000 matrizes tem um único elemento. Então começamos a mesclar essas sub matrizes juntos novamente na ordem correta. Então, tomamos duas matrizes de um elemento e criar uma matriz de dois elementos. Tomamos duas matrizes de dois elementos e criar uma matriz de quatro elementos e assim por diante e assim por diante até que tenhamos novamente reconstruída uma matriz elemento n. 

O tempo de execução do pior caso de merge sort é n vezes log n. Temos n elementos, mas este processo de recombinação pega no registo n passos para obter de volta para um conjunto completo. O melhor caso o tempo de execução também é log n N porque este processo não realmente importam se a matriz foi classificadas ou não para começar. O processo é o mesmo, não há nenhuma maneira de curtos circuitos coisas. Então n log n, no pior caso, n log n na melhor das hipóteses. 

Falamos sobre dois busca algoritmos. Assim, busca linear é sobre iteração. Prosseguimos em toda a gama uma vez que, a partir da esquerda para a direita, tentando encontrar o número que estamos procurando. O tempo de pior caso executar é grande O de n. Ele pode nos levar a iteração através de cada elemento para encontrar o elemento que estamos procurando para, quer na última posição, ou não em todos. Mas não podemos confirmar que até nós olhamos tudo. sou o melhor caso, encontramos imediatamente. O tempo de execução do melhor caso de busca linear é omega de 1. 

Por último, não havia pesquisa binária, que requer gama variada. Lembre-se que é muito consideração importante quando se trabalha com pesquisa binária. É um pré-requisito para utilizar ele-- a matriz que você está procurando através deve ser classificado. Caso contrário, a palavra-chave é dividir e conquistar. Dividir a matriz em metade e eliminar metade dos elementos cada vez que à medida que avançar através. Devido a isso dividir e conquistar e as coisas dividindo pela metade abordagem, o tempo de execução do pior caso de busca binária é log n, que é substancialmente melhor do que de busca linear n. O melhor caso o tempo de execução ainda é um. 

Podemos encontrá-lo imediatamente a primeira vez que fazemos uma divisão, mas, novamente, lembre-se que embora busca binária é substancialmente melhor do que a pesquisa linear em virtude de ser log n contra n, você pode ter que ir através do trabalho de classificar a matriz primeiro, que pode torná-lo menos eficaz, dependendo sobre o tamanho da iteração classificados. 

Eu sou Doug Lloyd, este é CS50.