[Powered by Google Translate] TOMMY: Нека да разгледаме избора на вид, алгоритъм
списък на телефонните номера и ги сортира.
Алгоритъм, не забравяйте, е просто стъпка по стъпка
процедура за изпълнение на дадена задача.
Основната идея зад избора Сортиране е да се разделят
нашия списък в две части -
подредени част и несортиран част.
На всяка стъпка на алгоритъма, броят ще бъде преместен от
несортирани част на сортират част, докато в крайна сметка
целия списък е сортиран.
Така че тук е списък от шест числа -
23, 42, 4, 16, 8 и 15.
Точно сега целия списък се счита несортирани.
Въпреки че редица като 16 вече може да се правилното му
, нашият алгоритъм няма как да знае, че до
целия списък е сортиран.
Така че ние ще разгледаме всеки номер да се несортирани докато не сортирате
сами.
Ние знаем, че искаме списъка, за да бъде във възходящ ред.
Така че ние ще искаме да изградим подредени част от нашия списък
от ляво на дясно, най-малките до най-големите.
За да направите това, ние ще трябва да намерим минималната несортирани елемент
и го сложи в края на сортират част.
Тъй като този списък не е сортиран, единственият начин да направите това е да се
разгледаме всеки елемент в несортиран част, спомняйки
кой елемент е най-ниската и сравняване
всеки елемент на това.
Така че ние първо ще изглежда на 23.
Това е първият елемент, който съм виждал, така че ние ще си спомните
като минимум.
След това ще разгледаме 42.
42 е по-голям от 23, така че 23 все още е минимален.
След това е 4, което е по-малко от 23, така че ние ще си спомните 4
като новото минимално.
След това е 16, който е по-голям от 4, 4
все още е минимален.
8 е по-голяма от 4 и 15 е по-голяма от 4, така че 4 трябва да бъде
най-малката несортирани елемент.
Така че дори и ние като хора може веднага да види, че 4 е
минимален елемент, трябва да погледнете нашия алгоритъм
всеки несортирани елемент, дори и след като ние открихме 4 -
минималния елемент.
Така че сега сме намерили минималния елемент, 4, ще искаме
да го преместите в сортират част на списъка.
Тъй като това е първата стъпка, това означава, че искаме да вложим 4 в
началото на списъка.
В момента 23 е в началото на списъка, така че
да сменяте 4 и 23.
Така че сега нашия списък изглежда така.
Ние знаем, че 4 трябва да бъде в неговата крайна дестинация, защото е
най-малкия елемент и елемент в началото
на списъка.
Така че това означава, че ние никога не трябва да се движат отново.
Така че нека да повторите този процес, за да добавите още един елемент на
подредени част на списъка.
Ние знаем, че не е нужно да търсите в четири, защото това е
вече сортирани.
Така че ние може да започне в 42, което ще се запомни като
минималния елемент.
Така че следващия ние ще разгледаме 23, което е по-малко от 42, така че ние
не забравяйте, 23 е новото минимално.
След това виждаме 16, което е по-малко от 23, така че
16 е новото минимално.
Сега търсим в 8, което е по-малко от 16, така че
8 е новата минимум.
И накрая 8 е по-малко от 15, така че ние знаем, че 8 е минимално
несортирани елемент.
Така че това означава, че ние трябва да добавите 8 до сортират
част на списъка.
В момента 4 е само подредени елемент, така че ние искаме да се постави
8 до 4.
От 42 е първият елемент в несортиран част от
списък, ще искате да сменяте 42 и 8.
Така че сега нашия списък изглежда така.
4 и 8 представляват подредени част на списъка, и
останалите числа представляват несортирани
част на списъка.
Така че нека да продължим с друга итерация.
Започваме с 23 този път, тъй като ние не трябва да се търси в
4 и 8 повече, защото те
вече са сортирани.
16 е по-малко от 23, така че ние ще си спомните
16 като нов минимум.
16 е по-малко от 42, но 15 е по-малко от 16, така че 15 трябва да бъде
минималната несортирани елемент.
Така че сега ние искаме да размените 15 и от 23 до
да ни даде този списък.
Подредени част от списъка се състои от 4, 8 и 15, и
тези елементи са все още несортирани.
Но просто така се случва, че следващата несортирани елемент, 16,
вече е сортиран.
Въпреки това, няма начин за нашия алгоритъм, за да се знае, че 16
вече е в правилното си местоположение, така че ние все още трябва да
повтаря точно един и същ процес.
Така виждаме, че 16 е по-малко от 42 и 16 е по-малко от 23, така че
16 трябва да бъде елемент на минимална.
Това е невъзможно да се разменят този елемент със себе си, така че можем
просто да го оставите на това място.
Така че имаме нужда от още един пропуск на нашия алгоритъм.
42 е по-голяма от 23, така че 23 трябва да бъде
минимум несортирани елемент.
След като размените 23 и 42, ние завършваме с окончателното ни
сортиран списък -
4, 8, 15, 16, 23, 42.
Знаем, че 42 трябва да са на правилното място, тъй като това е
единственият елемент, наляво, и това е избор на вид.
Нека сега официално нашия алгоритъм с някои
pseudocode.
На първа линия, можем да видим, че ние трябва да се интегрират над
всеки елемент от списъка.
С изключение на последния елемент, тъй като един елемент
списък вече е сортиран.
На втора линия, смятаме, че първият елемент на несортиран
част от списъка, за да бъде минимално, както направихме с нашите
Например, така че ние имаме нещо, което да се сравни с.
Третия ред започва втора линия, в която обхождане
всяка несортирани елемент.
Ние знаем, че след като повторения, подредени част
от нашия списък трябва да има елементи в нея, тъй като всяка стъпка
видове един елемент.
Така че първо несортирани елемент трябва да бъде в позиция плюс един.
На линия четири, сравнение на текущия елемент до минимум
елемент, който сме виждали досега.
Ако текущия елемент е по-малък от минималния
елемент, тогава ние помним текущия елемент като нов
минимум он-лайн пет.
И накрая, по линии, шест и седем, ние сменяте минимум
елемент с първото несортирани елемент, като по този начин
добавяйки, че да сортират част от списъка.
След като имаме алгоритъм, който е важен въпрос, на който
себе си като програмисти е колко време отнеме?
Ще първо да си зададем въпроса колко време е необходимо за това
алгоритъм, за да се движи в най-лошия случай?
Спомням ние представляваме това бягане
време с голям нотация O.
За да се определи минималната несортирани елемент,
по същество трябваше да сравни всеки елемент в списъка, за да
всеки друг елемент в списъка.
Интуитивно, това звучи като квадрат операция О Н.
Търсите в нашия pseudocode, ние също имаме една линия, вплетена в
друга верига, която наистина звучи като O
на н квадрат работа.
Все пак, не забравяйте, че ние не трябва да гледаме през
целия списък при определяне на минималната несортирани елемент?
След като ние знаехме, че 4 е сортиран, например, ние не
трябва да я погледне отново.
Същото прави и тази по-ниска време на работа?
За нашия списък с дължина 6, ние трябваше да правят пет
сравнения за първия елемент, четири сравнения за
Вторият елемент, и така нататък.
Това означава, че общият брой на стъпките е сумата от
числа от 1 до дължината на списъка минус 1.
Ние може да представлява това с сумиране.
Ние няма да отидат в summations тук.
Но се оказва, че това сумиране е равна пъти н
N минус 1 над 2.
Или еквивалентно, N квадрат над 2 минус N над 2.
Когато говорим за асимптотичната по време на работа, това н квадрат мандат
ще да доминират тази н мандат.
Подбор вид е O N квадрат.
Спомнете си, че в нашия пример, подбор вид все още трябва да
проверите дали даден номер, който вече е бил сортиран
е необходимо да бъдат преместени.
Така че това означава, че ако ние се завтече избора Сортиране вече
сортиран списък, тя ще изисква същия брой стъпки, тъй като
би, когато работи над напълно несортиран списък.
Така избор вид има най-добрия случай изпълнението на N на квадрат,
, които ние представляваме с омега-н квадрат.
И това е за избор на вид.
Само един от многото алгоритми можем
използвате, за да сортирате списъка.
Моето име е Томи, и това е cs50.