Doug LLOYD: Entón, nós aprenden sobre CS50 unha variedade de clasificación e investigación algoritmos. E ás veces isto pode ser un pouco complicado para manter ao tanto do que algoritmo fai o que. Temos realmente só desnatado a superficie tamén, hai moitos outros investigación e algoritmos de ordenación. Polo tanto, neste vídeo, imos só levar uns minutos para tratar e destilar cada algoritmo abaixo aos seus elementos centrais para que poida lembrar o máis información importante sobre eles e ser capaz de articular a diferenzas, se fose necesario. 

A primeira é a selección de clasificación. A idea básica por tras de selección tipo é atopar o menor elemento sen clasificar nunha matriz e troca-lo co primeiro elemento non ordenado dese array. Nós dixemos que o peor caso tempo de execución que se n ao cadrado. E se queres lembrar por que razón, tomar un ollar para o vídeo selección de clasificación. O tempo de execución do mellor caso é tamén n ao cadrado. 

Bubble sort, a idea detrás diso un é cambiar os pares adxacentes. Entón, esa é a clave que axuda Teña en conta que a diferenza aquí. Selección tipo é, ata agora, atopar o bubble smallest-- Sort é cambiar os pares adxacentes. Nós trocar pares adxacentes de elementos se están fóra de orde, o que efectivamente Burbullas de elementos máis grandes para a dereita, e, á vez que tamén comeza para mover elementos menores á esquerda. O peor caso de tempo caso de execución de bubble sort é n ao cadrado. O tempo de execución do mellor caso de bubble sort é n. Porque nesa situación non actually-- que quizais non sexa necesario facer os swaps en todo. Nós só ten que facer unha pasar por todos os elementos n. 

Na ordenación por inserción, o idea básica aquí está cambiando. Esa é a palabra clave para a inserción de clasificación. Nós imos para a etapa a través dunha vez a matriz de esquerda a dereita. E como nós facemos, nós somos cambiará elementos vimos para dar lugar a os menores que necesitan un lugar para caber de volta en que parte clasificada. Entón, nós construímos a matriz clasificada unha elemento de cada vez, para a esquerda a dereita, e cambiamos cousas que facer o cuarto. O tempo de execución do peor caso de ordenación por inserción é n ao cadrado. O mellor caso o tempo de execución é n. 

Mesturar sort-- a palabra chave aquí é dividir e mesturar. Podemos dividir o conxunto completo, se é seis elementos, oito elementos, 10.000 elements-- nós división lo abaixo á metade, á metade, á metade, ata que teñamos baixo matriz n dun elemento de matrices. Un conxunto de matrices n un elemento. Entón comezamos cunha 1000-elemento da matriz, e chegamos ao punto en que 1.000 matrices ten un único elemento. Entón comezamos a mesturar estas sub matrices xuntos na orde correcta. Entón, tomamos dúas matrices dun elemento e crear unha matriz de dous elementos. Tomamos dúas matrices de dous elementos e crear unha matriz de catro elementos e así por diante e así por diante ata que teñamos novamente reconstruída unha matriz elemento n. 

O tempo de execución do peor caso de merge sort é n veces rexistro n. Temos n elementos, pero este proceso de recombinación colle no rexistro n pasos para obter de volta a un conxunto completo. O mellor caso o tempo de execución tamén é log n N porque este proceso non realmente importan a matriz foi clasificadas ou non para comezar. O proceso é o mesmo, non hai ningunha forma de curtos circuítos cousas. Entón n log n, no peor caso, n log n no mellor dos casos. 

Falamos sobre dous busca algoritmos. Así, busca linear é sobre iteración. Continuar en toda a gama xa que, a partir de esquerda a dereita, intentando atopar o número que estamos a procurar. O tempo de peor caso executar é grande O n. Pode levar a iteración a través de cada elemento para atopar o elemento que estamos a buscar para, tanto na última posición, ou non en todos. Pero non podemos confirmar que ata nós miramos todo. son o mellor caso, atopamos inmediatamente. O tempo de execución do mellor caso busca linear é omega de 1. 

Para rematar, non había investigación binaria, que require gama variada. Lembre que é moi consideración importante cando se traballa con pescuda binária. É unha condición previa para utilizar ele-- a matriz que está a buscar a través debe ser clasificado. Se non, a palabra chave é dividir e conquistar. Dividir a matriz en metade e eliminar a metade dos elementos cada vez que a medida que avanzar a través. Debido a iso dividir e conquistar e as cousas dividindo á metade visión, o tempo de execución do peor caso de busca binaria é log n, que é substancialmente mellor que de busca linear n. O mellor caso o tempo de execución aínda é un. 

Podemos atopalo inmediatamente a primeira vez que facemos unha división, pero, de novo, lembre que aínda busca binaria é substancialmente mellor que a investigación lineal en virtude de ser log n contra n, pode ter que ir a través do traballo de clasificar a matriz primeiro, que pode facelo menos eficaz en función sobre o tamaño da iteración clasificados. 

Eu son Doug Lloyd, este é CS50.