[Играет музыка] 

ДАГ Lloyd: Так вставки сортировки другой Алгоритм можно использовать для сортировки массива. Идея этого алгоритма это, чтобы построить свой отсортированный массив в месте, переминаясь элементы из способ, как вы идете, чтобы освободить место. Это немного отличается от выбора рода или пузыря рода, например, где мы регулировки местоположения, где мы делаем свопы. 

В этом случае то, что мы на самом деле делаете раздвижные элементы более, из пути. Как это алгоритм работать в псевдокоде? Ну давайте просто произвольно сказать, что Первый элемент массива сортируется. Мы строим ее на месте. 

Мы собираемся идти один элемент, в то время, и строить и поэтому первое, что мы видим, это массив один элемент. И по определению, один элемент массива сортируется. 

Тогда мы будем повторять этот процесс until-- мы будем повторять следующую процедуру пока все элементы не сортируются. Посмотрите на следующий несортированным элемента и вставьте его в отсортированном части, путем сдвига необходимое количество элементов из пути. Надеюсь, эта визуализация поможет вам увидеть именно то, что происходит с вставки рода. 

Итак, еще раз, вот наш Весь массив несортированный, все элементы отображаются в красном цвете. И давайте следовать шаги нашего псевдокоде. Первое, что мы делаем, является мы называем Первый элемент массива, отсортировать. Так что мы просто собираюсь говорить пять, вы теперь сортируются. 

Затем мы рассмотрим на следующем несортированный элемент массива и мы хотим, чтобы вставить, что в части отсортировано, сдвигая элементы старше. Так два это следующий несортированный элемент массива. Очевидно, он принадлежит до пять, так что мы собираемся сделать является своего рода проведет два в сторону на секунду, переложить пять над, а затем вставьте два до пяти, где должны идти. И теперь мы можем сказать, что два сортируется. 

Итак, как вы видите, мы только пока посмотрел на двух элементов массива. Мы не смотрели на отдых на всех, но мы получил эти два элемента сортируются по Способ механизма переключения. 

Таким образом, мы повторяем процесс снова. Посмотрите на следующий несортированный элемент, что одна. Давайте считать, что в сторону на секунду, переложить все закончилось, и положить один где она должна идти. 

Опять же, до сих пор, мы только когда-либо посмотрел на один, два и пять. Мы не знаем, что еще идет, но мы сортируются эти три элемента. 

Следующая несортированный элемент три, так что мы будем устанавливать его в сторону. Мы постепенно смещать то, что мы нужно, который, на этот раз это еще не все, как и в предыдущем два случая, это просто пять. И тогда мы будем придерживаться три в, между двумя и пятью. 

Шесть является следующим несортированный элемент к массиву. И в самом деле шести больше пяти, так мы даже не нужно делать какие-либо замены. Мы можем просто лавировать шесть право на конец отсортированного части. 

Наконец, четыре является Последнее несортированный элемент. Таким образом, мы будем устанавливать его в сторону, перейти по элементы, которые мы должны перенести в течение, а затем положить четыре, где она принадлежит. А теперь посмотрите, мы вроде из всех элементов. Обратите внимание, с введением сортировать, у нас не было чтобы идти вперед и назад через массив. Мы только пошли через массив одно время, и мы перешли вещи что мы уже сталкивались в порядок чтобы освободить место для новых элементов. 

Так что в худшем случае Сценарий с вставки рода? В худшем случае, массив в обратном порядке. Вы должны перейти каждого из п элементов до н позиций, каждый раз, когда мы сделать вставку. Это много меняется. 

В лучшем случае, Массив прекрасно отсортированы. И вроде как то, что произошло с пятью и шестью в примере, где мы могли бы просто лавировать ее на без того, чтобы сделать любой сдвиг, мы, по существу, что делать. 

Если представить, что наши Массив был один через шесть, мы бы начать с заявив, один сортируется. Два приходит после одного, чтобы мы могли просто говорят, хорошо, хорошо один и два сортируются. Три приходит после двух, так, хорошо, один и два, и три сортируются. 

Мы не делаем никаких свопы, мы просто перемещение эту произвольную линию между сортируются и несортированный, как мы идем. Как эффективно, как мы это делали в примере, поворачивая элементы синий, как мы дальше. Так что в худшем случае выполнения, то? Помните, что если у нас есть переложить каждый из русские элементы, возможно, N позиций, мы надеемся, что дает вам идея, что в худшем случае выполнения является Большой О п квадрате. 

Если массив прекрасно сортировать, все, что мы должны сделать, это посмотреть на каждого элемента один раз, а затем мы сделали. Таким образом, в лучшем случае, это омега п. 

Я Дуг Ллойд. Это CS50.