1 00:00:00,000 --> 00:00:03,360 >> [Мусиц плаиинг] 2 00:00:03,360 --> 00:00:04,522 3 00:00:04,522 --> 00:00:06,730 Даг Ллоид: У реду, балон врста је алгоритам 4 00:00:06,730 --> 00:00:08,730 можете користити за сортирање скуп елемената. 5 00:00:08,730 --> 00:00:10,850 Хајде да погледамо како се то ради. 6 00:00:10,850 --> 00:00:13,240 >> Дакле, основна идеја балон врста је ово. 7 00:00:13,240 --> 00:00:17,340 Ми генерално желите да преместите више вреднује елементи углавном десно, 8 00:00:17,340 --> 00:00:20,340 и смањити углавном у вредности елемената са леве стране, као што смо очекивали. 9 00:00:20,340 --> 00:00:23,256 Желимо ниже ствари буду на почетак, и више ствари 10 00:00:23,256 --> 00:00:24,970 бити на крају. 11 00:00:24,970 --> 00:00:26,130 >> Како ми то радимо? 12 00:00:26,130 --> 00:00:28,040 Па у Псеудокод код, можемо рећи, хајдемо 13 00:00:28,040 --> 00:00:30,320 сет свап цоунтер то нон-нула вредности. 14 00:00:30,320 --> 00:00:32,570 Видећемо зашто то чинимо у секунди. 15 00:00:32,570 --> 00:00:36,090 И онда поновити сљедеће Процес док Свап бројач је 0, 16 00:00:36,090 --> 00:00:39,910 или док не правимо свопови уопште. 17 00:00:39,910 --> 00:00:43,170 >> Ресет свап цоунтер то 0 ако већ није 0. 18 00:00:43,170 --> 00:00:46,420 Онда погледате сваки суседни пар елемената. 19 00:00:46,420 --> 00:00:49,550 Ако та два елемента су Не би, замените их, 20 00:00:49,550 --> 00:00:51,620 и додаје 1 свап шалтеру. 21 00:00:51,620 --> 00:00:53,870 Ако размишљате о ово пре него што га замишљали, 22 00:00:53,870 --> 00:00:57,471 Приметићете да ће овај потез ниже цењеним елементи за лево 23 00:00:57,471 --> 00:01:00,720 и више вреднује елементе десно, ефикасно раде оно што желимо да урадимо, 24 00:01:00,720 --> 00:01:03,940 која је померите те групе елемената на тај начин. 25 00:01:03,940 --> 00:01:07,035 Хајде да визуализовати како је могу изгледати користећи наш низ 26 00:01:07,035 --> 00:01:10,504 који смо користили за тестирање од ових алгоритама. 27 00:01:10,504 --> 00:01:13,420 Имамо низ УНСОРТЕД опет овде, указују све елементе 28 00:01:13,420 --> 00:01:14,840 бити у црвено. 29 00:01:14,840 --> 00:01:17,970 И сет ми свап цоунтер до нуле вредности. 30 00:01:17,970 --> 00:01:20,610 Ја произвољно одабрао негативна 1-- није 0. 31 00:01:20,610 --> 00:01:23,840 Желимо да поновимо овај процес док свап шалтеру је 0. 32 00:01:23,840 --> 00:01:26,540 То је разлог зашто сам поставио свој свап супротности са неким не-нула вредности, 33 00:01:26,540 --> 00:01:29,400 јер у противном Свап бројач ће бити 0. 34 00:01:29,400 --> 00:01:31,610 Не би ни отпочне процес алгоритма. 35 00:01:31,610 --> 00:01:33,610 Дакле, опет, кораци су-- ресет свап цоунтер 36 00:01:33,610 --> 00:01:37,900 0, онда погледајте сваки суседни пар, и ако су у реду, 37 00:01:37,900 --> 00:01:40,514 свап их и додајте 1 на свап шалтеру. 38 00:01:40,514 --> 00:01:41,680 Дакле, хајде да почнемо овај процес. 39 00:01:41,680 --> 00:01:44,430 Дакле, прва ствар коју радимо је поставили смо свап бројач на 0, 40 00:01:44,430 --> 00:01:46,660 и онда почни на сваком суседном пару. 41 00:01:46,660 --> 00:01:49,140 >> Зато смо прво почети гледајући 5 и 2. 42 00:01:49,140 --> 00:01:52,410 Видимо да су из нареди па смо их заменимо. 43 00:01:52,410 --> 00:01:53,830 И додамо 1 до свап шалтеру. 44 00:01:53,830 --> 00:01:57,860 Дакле, сада наш Свап бројач је 1, и 2. и 5 су пребачене. 45 00:01:57,860 --> 00:01:59,370 Сада поновите поступак поново. 46 00:01:59,370 --> 00:02:03,540 >> Гледамо на следећем суседном пару, 5 и 1-- су такође ван функције, 47 00:02:03,540 --> 00:02:06,960 тако да их мењате и додајте 1 уз своп шалтеру. 48 00:02:06,960 --> 00:02:08,900 Онда погледамо 5 и 3. 49 00:02:08,900 --> 00:02:13,830 Они су од реда, па смо свап их и додамо 1 до свап шалтеру. 50 00:02:13,830 --> 00:02:15,550 Онда погледамо 5. и 6.. 51 00:02:15,550 --> 00:02:18,630 Они су у реду, тако да заправо не треба да замени било шта овај пут. 52 00:02:18,630 --> 00:02:20,250 Онда погледамо 6 и 4. 53 00:02:20,250 --> 00:02:24,920 Такође су од реда, па смо свап их и додамо 1 до свап шалтеру. 54 00:02:24,920 --> 00:02:26,230 >> Сада погледајмо шта се догодило. 55 00:02:26,230 --> 00:02:29,514 Ми смо преселили 6 скроз до краја. 56 00:02:29,514 --> 00:02:32,180 Дакле, у избор врсте, ако сте види тај видео, оно што смо урадили је 57 00:02:32,180 --> 00:02:35,290 смо завршили померање Најмањи елементи у згради 58 00:02:35,290 --> 00:02:39,640 сортиран низ суштински од лева на десно, најмањег до највећег. 59 00:02:39,640 --> 00:02:43,200 У случају балон врсте, ако смо Следећи овом алгоритма, 60 00:02:43,200 --> 00:02:46,720 ћемо заправо да се гради сортиран низ од десне стране 61 00:02:46,720 --> 00:02:49,100 на лево, највећег ка најмањем. 62 00:02:49,100 --> 00:02:53,840 Ми смо ефикасно у мехурићима 6, Највећа вредност, све до краја. 63 00:02:53,840 --> 00:02:56,165 >> И тако сада можемо прогласити да је се разврстава, 64 00:02:56,165 --> 00:02:59,130 и у будућности итератионс-- пролази кроз низ Поново: 65 00:02:59,130 --> 00:03:01,280 не морамо више да размотри 6. 66 00:03:01,280 --> 00:03:03,850 Ми само морамо да размотримо Унсортед су елементи 67 00:03:03,850 --> 00:03:06,299 када гледамо суседних парова. 68 00:03:06,299 --> 00:03:08,340 Тако смо завршили један пролазе кроз буббле врсте. 69 00:03:08,340 --> 00:03:11,941 Дакле, сада се вратимо на питање, поновите поступак док се Свап бројач је 0. 70 00:03:11,941 --> 00:03:13,690 Па за свап бројач је 4, тако да идемо 71 00:03:13,690 --> 00:03:15,410 да би понављам овај процес. 72 00:03:15,410 --> 00:03:19,180 >> Идемо за ресетовање свап цоунтер 0, и погледате сваки суседни пар. 73 00:03:19,180 --> 00:03:21,890 Дакле, да почнемо са 2 и 1-- су из реда, па смо их заменимо 74 00:03:21,890 --> 00:03:23,620 и додамо 1 до свап шалтеру. 75 00:03:23,620 --> 00:03:25,490 2 и 3, они су у реду. 76 00:03:25,490 --> 00:03:27,060 Не треба ништа да радите. 77 00:03:27,060 --> 00:03:28,420 3 и 5 су у реду. 78 00:03:28,420 --> 00:03:30,150 Не треба ништа да раде тамо. 79 00:03:30,150 --> 00:03:32,515 >> 5 и 4, оне нису реда, па смо 80 00:03:32,515 --> 00:03:35,130 треба да их замене и додајте 1 уз своп шалтеру. 81 00:03:35,130 --> 00:03:38,880 И сада смо преселили 5, следећи највећи елеменат, 82 00:03:38,880 --> 00:03:40,920 до краја неразврстан дела. 83 00:03:40,920 --> 00:03:44,360 Дакле, сада можемо назвати део сортирана дела. 84 00:03:44,360 --> 00:03:47,180 >> Сада гледате екран и вероватно може рећи, 85 00:03:47,180 --> 00:03:50,130 Као што сам, да је низа се разврстава сада. 86 00:03:50,130 --> 00:03:51,820 Али, не можемо да докажемо још. 87 00:03:51,820 --> 00:03:54,359 Ми немамо гаранцију да је то решено. 88 00:03:54,359 --> 00:03:56,900 Али ово је место где замена бројач ће да ступи на сцену. 89 00:03:56,900 --> 00:03:59,060 >> Тако смо завршили пас. 90 00:03:59,060 --> 00:04:00,357 Свап бројач је 2. 91 00:04:00,357 --> 00:04:02,190 Тако ћемо поновити опет овај процес, 92 00:04:02,190 --> 00:04:04,290 поновите поступак док се Свап бројач је 0. 93 00:04:04,290 --> 00:04:05,550 Ресет свап бројач на 0. 94 00:04:05,550 --> 00:04:06,820 Дакле, ми ћемо га вратите. 95 00:04:06,820 --> 00:04:09,810 >> Сада погледате сваки суседни пар. 96 00:04:09,810 --> 00:04:11,880 То је како, 1 и 2. 97 00:04:11,880 --> 00:04:13,590 2 и 3 су у реду. 98 00:04:13,590 --> 00:04:15,010 3 и 4 су у реду. 99 00:04:15,010 --> 00:04:19,250 Дакле, у овом тренутку, приметио смо завршили гледа на сваком суседном пару, 100 00:04:19,250 --> 00:04:22,530 али Свап бројач је и даље 0. 101 00:04:22,530 --> 00:04:25,520 >> Ако не морате да се пребацујете било елемената, онда 102 00:04:25,520 --> 00:04:28,340 морају бити у поретка, врлина овог процеса. 103 00:04:28,340 --> 00:04:32,000 И тако да се ефикасност врста, да смо компјутерски научници лове, 104 00:04:32,000 --> 00:04:35,560 се сада можемо прогласити цео низ мора 105 00:04:35,560 --> 00:04:38,160 се сортирају, јер нисмо треба да замени све елементе. 106 00:04:38,160 --> 00:04:40,380 То је лепо. 107 00:04:40,380 --> 00:04:43,260 >> Дакле, оно што је најгори случај сценарио са буббле врстом? 108 00:04:43,260 --> 00:04:46,240 У најгорем случају низ је у потпуно обрнутим редом, 109 00:04:46,240 --> 00:04:49,870 па морамо да сваки мехур великих елемената све 110 00:04:49,870 --> 00:04:51,780 пут преко низа. 111 00:04:51,780 --> 00:04:55,350 И ми ефективно такође морати да мехур све мале елемената назад 112 00:04:55,350 --> 00:04:57,050 скроз преко низа, превише. 113 00:04:57,050 --> 00:05:01,950 Тако сваки од н елемената мора да се креће кроз свим другим н елемената. 114 00:05:01,950 --> 00:05:04,102 Дакле, то је најгори сценарио. 115 00:05:04,102 --> 00:05:05,810 У најбољем случају сценарио ипак, ово је 116 00:05:05,810 --> 00:05:07,880 мало разликује од селекције врсте. 117 00:05:07,880 --> 00:05:10,040 Низ је већ поредани кад одемо у. 118 00:05:10,040 --> 00:05:12,550 Не морамо да сваки свап на првом пролазу. 119 00:05:12,550 --> 00:05:14,940 Дакле, можемо да погледамо на мање елемената, зар не? 120 00:05:14,940 --> 00:05:18,580 Не морамо да поновимо ово обради више пута током. 121 00:05:18,580 --> 00:05:19,540 >> Дакле, шта то значи? 122 00:05:19,540 --> 00:05:22,390 Дакле, оно што је најгори сценарио за буббле сорт, и шта је 123 00:05:22,390 --> 00:05:25,330 најбољи сценарио за буббле сорт? 124 00:05:25,330 --> 00:05:27,770 Да ли сте погодили ово? 125 00:05:27,770 --> 00:05:32,420 У најгорем случају морате поновити у свим н елемената н пута. 126 00:05:32,420 --> 00:05:34,220 Дакле, у најгорем случају је н квадрат. 127 00:05:34,220 --> 00:05:36,550 >> Ако је низ савршено сортиран ипак, само ти 128 00:05:36,550 --> 00:05:38,580 да погледам сваки елемената једанпут. 129 00:05:38,580 --> 00:05:42,670 А ако је замена бројач је и даље 0, можете рећи низ сортира. 130 00:05:42,670 --> 00:05:45,780 И тако у најбољем случају, ово је заправо бољи од селекције 131 00:05:45,780 --> 00:05:49,230 сорт-- је омега н. 132 00:05:49,230 --> 00:05:50,270 >> Ја сам Доуг Лојд. 133 00:05:50,270 --> 00:05:52,140 Ово је ЦС50. 134 00:05:52,140 --> 00:05:54,382