1 00:00:00,000 --> 00:00:11,100 2 00:00:11,100 --> 00:00:12,300 >> 揚聲器1:嗨大家好! 3 00:00:12,300 --> 00:00:13,890 歡迎回到一節。 4 00:00:13,890 --> 00:00:17,480 很高興見到你們這麼多人都在這裡, 大家誰的在線觀看。 5 00:00:17,480 --> 00:00:18,760 6 00:00:18,760 --> 00:00:20,920 所以,像往常一樣,歡迎回來。 7 00:00:20,920 --> 00:00:24,360 我希望大家都度過了一個可愛 週末,得到充分的休息,放鬆。 8 00:00:24,360 --> 00:00:26,026 這是美麗的昨天。 9 00:00:26,026 --> 00:00:27,525 所以,我希望你喜歡戶外活動。 10 00:00:27,525 --> 00:00:28,840 11 00:00:28,840 --> 00:00:30,610 >> 因此,首先一對夫婦公告。 12 00:00:30,610 --> 00:00:31,920 13 00:00:31,920 --> 00:00:32,700 分級。 14 00:00:32,700 --> 00:00:37,350 所以,你最應該得到的 從我的電子郵件你刮的Pset, 15 00:00:37,350 --> 00:00:39,920 以及分級的Pset中1。 16 00:00:39,920 --> 00:00:41,000 17 00:00:41,000 --> 00:00:42,220 所以,只是一對夫婦的事情。 18 00:00:42,220 --> 00:00:45,150 請務必使用check50在style50。 19 00:00:45,150 --> 00:00:47,250 這些都意味著是 資源為你們, 20 00:00:47,250 --> 00:00:50,660 確保你得到 盡可能多的點,你可以 21 00:00:50,660 --> 00:00:52,390 沒有不必要的失去他們。 22 00:00:52,390 --> 00:00:54,407 所以像風格 是非常重要的。 23 00:00:54,407 --> 00:00:55,740 我們要起飛了。 24 00:00:55,740 --> 00:00:58,115 你們有些人可能已經 注意到,從你的pset中。 25 00:00:58,115 --> 00:00:58,920 26 00:00:58,920 --> 00:01:01,450 和check50僅僅是一個 非常簡單的方法,以確保 27 00:01:01,450 --> 00:01:05,050 那我們實際上回歸了什麼 需要被返回給用戶, 28 00:01:05,050 --> 00:01:06,690 而這一切的正常工作。 29 00:01:06,690 --> 00:01:08,690 30 00:01:08,690 --> 00:01:12,040 >> 在第二個音符時,請確保您的 上傳東西到正確的文件夾中。 31 00:01:12,040 --> 00:01:14,470 它使我的生活只是一個 更困難一點 32 00:01:14,470 --> 00:01:18,836 如果你上傳的Pset 2成1的Pset 因為當我下載的東西, 33 00:01:18,836 --> 00:01:20,085 他們不能正確下載。 34 00:01:20,085 --> 00:01:21,690 35 00:01:21,690 --> 00:01:24,560 我知道這是一個有點靠不住 在一個系統中使用的獲得, 36 00:01:24,560 --> 00:01:26,950 但只是超 小心,如果只是對我來說, 37 00:01:26,950 --> 00:01:30,080 所以,當你得到的郵件 在像上午02點我就是分級。 38 00:01:30,080 --> 00:01:33,710 如果沒有引起我要看看 各地為您的Pset。 39 00:01:33,710 --> 00:01:34,440 涼爽。 40 00:01:34,440 --> 00:01:37,270 >> 我知道這是早期的,但我 完全得到起飛後衛 41 00:01:37,270 --> 00:01:40,800 通過一篇短文這是本週五到期,該 我的教授只是喜歡,哦耶。 42 00:01:40,800 --> 00:01:42,550 請記住,你有一個 文章將於週五公佈。 43 00:01:42,550 --> 00:01:45,780 所以,我知道沒有人喜歡 想想期中考試, 44 00:01:45,780 --> 00:01:50,620 但你的第一次測驗是10月15日, 其中10月份這個星期開始。 45 00:01:50,620 --> 00:01:53,290 因此,它可能是遲早 比你預期的是一切。 46 00:01:53,290 --> 00:01:57,510 讓你不扔猝不及防的時候 我提到下週一節哦, 47 00:01:57,510 --> 00:02:00,560 您的測驗接下來的一周,我想 我願意給你一點點 48 00:02:00,560 --> 00:02:01,500 的抬起頭來了。 49 00:02:01,500 --> 00:02:02,970 50 00:02:02,970 --> 00:02:04,660 >> 所以,你的問題集,排名第三。 51 00:02:04,660 --> 00:02:07,070 人如何閱讀 規範的好奇心了呢? 52 00:02:07,070 --> 00:02:08,560 53 00:02:08,560 --> 00:02:09,199 行。 54 00:02:09,199 --> 00:02:10,229 我們有一對夫婦。 55 00:02:10,229 --> 00:02:12,320 那種從上向下 本週不過沒關係。 56 00:02:12,320 --> 00:02:13,650 我知道這是美麗的。 57 00:02:13,650 --> 00:02:15,120 58 00:02:15,120 --> 00:02:16,660 因此爆發。 59 00:02:16,660 --> 00:02:21,010 一定時間後就會完成 今天看了你的天賦,至少 60 00:02:21,010 --> 00:02:25,240 嘗試像下載 發行代碼並運行 61 00:02:25,240 --> 00:02:27,430 像第一初始 他們問你要的東西。 62 00:02:27,430 --> 00:02:28,681 63 00:02:28,681 --> 00:02:32,590 因為我們使用 分配代碼和一個圖書館 64 00:02:32,590 --> 00:02:36,790 我們只是一直在using-- --IT只是 第二次我們已經做到了這一點的Pset, 65 00:02:36,790 --> 00:02:38,650 瘋狂的事情都可能發生 與您的設備, 66 00:02:38,650 --> 00:02:41,370 你想找到 從現在與以後。 67 00:02:41,370 --> 00:02:45,570 >> 因為如果是週四晚上或它的 週三晚上,由於某種原因 68 00:02:45,570 --> 00:02:48,912 您的設備少了點 要與庫運行 69 00:02:48,912 --> 00:02:50,620 或用分配 代碼,這意味著 70 00:02:50,620 --> 00:02:52,309 你甚至不能開始做編碼。 71 00:02:52,309 --> 00:02:54,100 因為你不能檢查 來看看它的工作原理。 72 00:02:54,100 --> 00:02:55,975 你不會是能夠 看它是否編譯。 73 00:02:55,975 --> 00:03:00,500 你想在早期照顧那些 本週,當你仍然可以給我發電子郵件 74 00:03:00,500 --> 00:03:03,100 或其他轉錄因子中的一個, 我們可以得到這些固定的。 75 00:03:03,100 --> 00:03:05,410 因為這些都是問題 這會阻止你 76 00:03:05,410 --> 00:03:07,120 做任何實際進展。 77 00:03:07,120 --> 00:03:10,055 它不象1的bug,那 有種你就跳過。 78 00:03:10,055 --> 00:03:10,712 79 00:03:10,712 --> 00:03:13,420 如果您遇到問題,您 設備或分發代碼, 80 00:03:13,420 --> 00:03:16,211 你真的想要得到所採取的 呵護宜早不宜遲。 81 00:03:16,211 --> 00:03:20,410 所以,即使你不會真正 開始編碼,下載發行 82 00:03:20,410 --> 00:03:24,040 碼,讀取規格,確保 一切都在那裡工作。 83 00:03:24,040 --> 00:03:25,134 行? 84 00:03:25,134 --> 00:03:27,675 如果你可以做到這一點,我 答應你的生活會更容易。 85 00:03:27,675 --> 00:03:28,800 86 00:03:28,800 --> 00:03:31,410 所以你很可能會 要做到這一點,現在好嗎? 87 00:03:31,410 --> 00:03:32,100 行。 88 00:03:32,100 --> 00:03:33,950 那麼,有什麼問題嗎? 89 00:03:33,950 --> 00:03:35,850 任何邏輯的東西呢? 90 00:03:35,850 --> 00:03:36,910 大家的好? 91 00:03:36,910 --> 00:03:38,270 行。 92 00:03:38,270 --> 00:03:41,700 >> 免責聲明對於那些 你在房間裡上網。 93 00:03:41,700 --> 00:03:45,437 我將要嘗試切換 PowerPoint中的裝置之間 94 00:03:45,437 --> 00:03:47,270 因為我們要 是做一些編碼 95 00:03:47,270 --> 00:03:53,630 今天流行的匿名需求 調查建議我送出去的最後一周。 96 00:03:53,630 --> 00:03:55,480 所以,我們會做一些編碼。 97 00:03:55,480 --> 00:03:57,800 所以,如果你們也想 火了你的設備, 98 00:03:57,800 --> 00:04:02,910 你應該已經得到了一封電子郵件, 從我來說,有一個示例文件。 99 00:04:02,910 --> 00:04:04,310 請隨時做。 100 00:04:04,310 --> 00:04:07,340 >> 所以,我們要談 GDB,這是一個調試程序。 101 00:04:07,340 --> 00:04:09,970 這將幫助你 種揣摩出 102 00:04:09,970 --> 00:04:11,860 事情會出錯的代碼。 103 00:04:11,860 --> 00:04:15,370 這真的只是一個方法可以讓你一步 通過你的代碼,它的發生, 104 00:04:15,370 --> 00:04:19,100 並能夠打印出變量 或者看看有什麼實際發生 105 00:04:19,100 --> 00:04:22,980 引擎蓋下的詩句程序 剛運行時,它就像斷層, 106 00:04:22,980 --> 00:04:25,030 和你一樣,不知道 這裡剛剛發生了什麼。 107 00:04:25,030 --> 00:04:26,730 我不知道它沒有在哪一行。 108 00:04:26,730 --> 00:04:29,040 我不知道哪裡出了問題。 109 00:04:29,040 --> 00:04:31,280 因此,GDB會幫助你的。 110 00:04:31,280 --> 00:04:35,240 另外,如果你決定 繼續沒錯,走61, 111 00:04:35,240 --> 00:04:38,430 它真的,真的是你 最好的朋友,因為我可以告訴你 112 00:04:38,430 --> 00:04:40,840 因為我要通過這個類。 113 00:04:40,840 --> 00:04:43,620 >> 我們要看看二進制 搜索,這如果你們還記得 114 00:04:43,620 --> 00:04:47,540 偉大的電話簿例子 眼鏡從類。 115 00:04:47,540 --> 00:04:50,620 我們將實現這一點, 通過多一點點走, 116 00:04:50,620 --> 00:04:54,650 然後我們要通過四個 不同種類的,這是泡沫, 117 00:04:54,650 --> 00:04:56,285 選擇,插入和合併。 118 00:04:56,285 --> 00:04:57,830 119 00:04:57,830 --> 00:04:58,330 涼爽。 120 00:04:58,330 --> 00:05:00,390 所以,GDB正如我所說,是一個調試器。 121 00:05:00,390 --> 00:05:01,400 122 00:05:01,400 --> 00:05:09,370 而這些都是一種大的 的東西,大的功能或命令 123 00:05:09,370 --> 00:05:13,240 您在使用GDB,我會走 你通過它在第二演示。 124 00:05:13,240 --> 00:05:15,360 >> 所以,這不僅是 要留抽象。 125 00:05:15,360 --> 00:05:18,000 我會試著讓它混凝土 盡可能為你們。 126 00:05:18,000 --> 00:05:19,870 因此,突破。 127 00:05:19,870 --> 00:05:22,200 它會要么是突破 象,一些數量,這 128 00:05:22,200 --> 00:05:26,900 代表你的程序行, 或者,你可以命名的功能。 129 00:05:26,900 --> 00:05:30,150 所以,如果你說分手主力, 它會停在主, 130 00:05:30,150 --> 00:05:32,400 並且讓你通過該功能走路。 131 00:05:32,400 --> 00:05:36,350 >> 同樣,如果你​​有一些外部 功能類似於交換或多維數據集, 132 00:05:36,350 --> 00:05:38,450 我們看最後一周。 133 00:05:38,450 --> 00:05:41,780 如果你說破其中的一個, 只要你的程序打了, 134 00:05:41,780 --> 00:05:44,290 就等你來 告訴它要做什麼。 135 00:05:44,290 --> 00:05:47,860 之前,它只會執行,所以你 可以在函數內部實際步驟 136 00:05:47,860 --> 00:05:49,020 看看是怎麼回事。 137 00:05:49,020 --> 00:05:50,370 138 00:05:50,370 --> 00:05:53,515 所以,接下來,就跳過了 下一行,越過功能。 139 00:05:53,515 --> 00:05:54,730 140 00:05:54,730 --> 00:05:55,560 步驟。 141 00:05:55,560 --> 00:05:56,810 這些都是有點抽象。 142 00:05:56,810 --> 00:06:00,530 所以,我只是通過他們的運行, 但你會看到他們在第二次使用。 143 00:06:00,530 --> 00:06:01,810 >> 步入函數。 144 00:06:01,810 --> 00:06:04,170 因此,正如我所說, 像交換,它會 145 00:06:04,170 --> 00:06:07,110 讓你真正的,如果你 就像身體裡面的加強, 146 00:06:07,110 --> 00:06:10,990 你可以亂用這些變量,打印 它們是什麼,看看發生了什麼事情。 147 00:06:10,990 --> 00:06:12,140 148 00:06:12,140 --> 00:06:14,830 名單將字面上只是打印 從周圍的代碼。 149 00:06:14,830 --> 00:06:17,570 所以,如果你種忘了 你在哪裡在你的程序中, 150 00:06:17,570 --> 00:06:19,880 或者你想知道 這是怎麼回事周圍, 151 00:06:19,880 --> 00:06:23,790 這將只打印出一個段 都喜歡它周圍的五六行。 152 00:06:23,790 --> 00:06:26,080 所以,你可以得到導向 關於你在哪裡。 153 00:06:26,080 --> 00:06:27,230 154 00:06:27,230 --> 00:06:28,650 >> 打印一些變量。 155 00:06:28,650 --> 00:06:34,590 所以,如果你有這樣的關鍵 在愷撒,那我們來看看。 156 00:06:34,590 --> 00:06:36,220 你可以說在任何時候打印鍵。 157 00:06:36,220 --> 00:06:40,070 它會告訴你的價值就是如此 這,也許某個地方一路走來, 158 00:06:40,070 --> 00:06:42,070 你重寫你的關鍵。 159 00:06:42,070 --> 00:06:45,495 實際上,你可以告訴大家,因為 你其實可以觀察到的價值。 160 00:06:45,495 --> 00:06:46,500 161 00:06:46,500 --> 00:06:48,780 >> 在當地人,只是版畫 你的局部變量。 162 00:06:48,780 --> 00:06:53,120 所以,任何時候,你是在一個循環中, 而你只是想看看像哦。 163 00:06:53,120 --> 00:06:54,270 什麼是我的嗎? 164 00:06:54,270 --> 00:06:57,020 這是什麼鍵值 我在這裡初始化? 165 00:06:57,020 --> 00:06:58,537 這是在這一點上的信息? 166 00:06:58,537 --> 00:07:00,370 它只是將打印所有 那些的,這樣就 167 00:07:00,370 --> 00:07:04,330 不必單獨地 說,打印一打印信息。 168 00:07:04,330 --> 00:07:04,970 打印鍵。 169 00:07:04,970 --> 00:07:06,190 170 00:07:06,190 --> 00:07:07,700 然後顯示。 171 00:07:07,700 --> 00:07:10,370 這是什麼做的是為你 單步執行程序, 172 00:07:10,370 --> 00:07:13,980 它會只是確保它的 顯示一定的變數 173 00:07:13,980 --> 00:07:14,780 在每一點上。 174 00:07:14,780 --> 00:07:17,160 所以,你also-- --IT是 一種快捷方式,其中的 175 00:07:17,160 --> 00:07:19,530 你沒有堅持下去似的,呵呵。 176 00:07:19,530 --> 00:07:23,150 打印鍵或打印一,這只是 將自動為您代勞。 177 00:07:23,150 --> 00:07:25,959 >> 因此,在這一點,我們要去 怎麼看這樣下去。 178 00:07:25,959 --> 00:07:28,000 我要去嘗試和開關 在我的設備。 179 00:07:28,000 --> 00:07:30,200 180 00:07:30,200 --> 00:07:31,271 看看我能做到這一點。 181 00:07:31,271 --> 00:07:31,770 全部。 182 00:07:31,770 --> 00:07:40,970 183 00:07:40,970 --> 00:07:42,370 我們只是要鏡像。 184 00:07:42,370 --> 00:07:44,530 沒有什麼瘋狂 我的筆記本電腦反正。 185 00:07:44,530 --> 00:07:49,600 186 00:07:49,600 --> 00:07:50,100 行。 187 00:07:50,100 --> 00:07:57,030 188 00:07:57,030 --> 00:08:01,054 這需要這個。 189 00:08:01,054 --> 00:08:01,795 它是如此的渺小。 190 00:08:01,795 --> 00:08:03,730 191 00:08:03,730 --> 00:08:05,120 讓我們來看看,如果我們能做到這一點。 192 00:08:05,120 --> 00:08:09,970 193 00:08:09,970 --> 00:08:10,940 >> 行。 194 00:08:10,940 --> 00:08:15,305 愛麗絲顯然是掙扎 這裡只是一點點, 195 00:08:15,305 --> 00:08:17,995 但我們會讓它在你幾分鐘。 196 00:08:17,995 --> 00:08:20,810 197 00:08:20,810 --> 00:08:22,020 行。 198 00:08:22,020 --> 00:08:25,900 我們只是要增加這一點。 199 00:08:25,900 --> 00:08:28,770 200 00:08:28,770 --> 00:08:29,380 行。 201 00:08:29,380 --> 00:08:31,679 種可大家看到了嗎? 202 00:08:31,679 --> 00:08:32,470 也許一點點? 203 00:08:32,470 --> 00:08:33,594 我知道這是小了點。 204 00:08:33,594 --> 00:08:34,570 205 00:08:34,570 --> 00:08:37,530 你不能完全弄清楚 如何使這個更大。 206 00:08:37,530 --> 00:08:38,350 如果有人知道。 207 00:08:38,350 --> 00:08:40,309 有誰知道如何使它更大? 208 00:08:40,309 --> 00:08:40,932 行。 209 00:08:40,932 --> 00:08:42,140 我們將推出它。 210 00:08:42,140 --> 00:08:45,801 不要緊,反正,因為它只是 這是代碼,你們應該 211 00:08:45,801 --> 00:08:46,300 有。 212 00:08:46,300 --> 00:08:48,310 >> 什麼是更重要的 是這裡的端子。 213 00:08:48,310 --> 00:08:52,840 214 00:08:52,840 --> 00:08:58,690 而我們在這裡為什麼會這麼少呢? 215 00:08:58,690 --> 00:09:02,325 216 00:09:02,325 --> 00:09:02,825 設置。 217 00:09:02,825 --> 00:09:07,920 218 00:09:07,920 --> 00:09:08,420 呵呵。 219 00:09:08,420 --> 00:09:09,500 真正的艾克。 220 00:09:09,500 --> 00:09:10,880 這個怎麼樣? 221 00:09:10,880 --> 00:09:11,770 離開那裡。 222 00:09:11,770 --> 00:09:19,370 223 00:09:19,370 --> 00:09:21,810 是為大家好? 224 00:09:21,810 --> 00:09:22,525 行,。 225 00:09:22,525 --> 00:09:23,025 涼爽。 226 00:09:23,025 --> 00:09:25,830 227 00:09:25,830 --> 00:09:28,220 >> 你知道,當你在CS 一流的技術困難 228 00:09:28,220 --> 00:09:32,971 是善良的the--一部分 所以,讓我們澄清這一點。 229 00:09:32,971 --> 00:09:33,470 行。 230 00:09:33,470 --> 00:09:38,060 所以,這裡的部分, 我們不得不在這裡。 231 00:09:38,060 --> 00:09:40,830 凱撒是一個可執行文件。 232 00:09:40,830 --> 00:09:41,800 所以,我做到了。 233 00:09:41,800 --> 00:09:46,370 所以,有一點要實現與GDB是 它僅適用於可執行文件。 234 00:09:46,370 --> 00:09:48,040 所以,你不能在dotsy運行它。 235 00:09:48,040 --> 00:09:50,532 你要真正使 確保你的代碼編譯, 236 00:09:50,532 --> 00:09:51,865 並且,它可以實際運行。 237 00:09:51,865 --> 00:09:52,970 238 00:09:52,970 --> 00:09:56,186 >> 因此,請相信,如果它不 編譯,得到它的編譯, 239 00:09:56,186 --> 00:09:57,810 這樣就可以通過它種上運行。 240 00:09:57,810 --> 00:10:04,590 因此,要啟動GDB,你所要做的, 凱萊型GDB,然後就在 241 00:10:04,590 --> 00:10:06,250 文件,你想要的。 242 00:10:06,250 --> 00:10:08,240 我總是拼錯撒。 243 00:10:08,240 --> 00:10:11,730 但是你要確保 因為它是一個可執行文件, 244 00:10:11,730 --> 00:10:14,210 TI的圓點閃爍,使 意味著你要 245 00:10:14,210 --> 00:10:19,240 運行CSI你要執行 此文件或者與調試。 246 00:10:19,240 --> 00:10:19,910 行。 247 00:10:19,910 --> 00:10:22,885 所以,你這樣做,你會得到 這種亂碼。 248 00:10:22,885 --> 00:10:24,250 249 00:10:24,250 --> 00:10:25,750 這只是所有關於調試的東西。 250 00:10:25,750 --> 00:10:28,200 你不會真的要 擔心現在。 251 00:10:28,200 --> 00:10:31,460 正如你看到的,我們有這個 開括號,國內生產總值,接近括號, 252 00:10:31,460 --> 00:10:34,690 而那種只是看起來像 我們的命令行,對不對? 253 00:10:34,690 --> 00:10:37,010 >> 所以,我們要do-- - 因此,第一件事 254 00:10:37,010 --> 00:10:39,570 就是我們要選 一個地方打破它。 255 00:10:39,570 --> 00:10:42,332 所以,有一個錯誤 在這個程序凱撒 256 00:10:42,332 --> 00:10:44,290 我介紹一下,這 我們要了解一下。 257 00:10:44,290 --> 00:10:45,330 258 00:10:45,330 --> 00:10:56,350 它是做什麼是需要輸入 Barfoo全部大寫,並由於某種原因 259 00:10:56,350 --> 00:11:01,950 它只是離開它不會改變A. 孤軍奮戰,是一切正確, 260 00:11:01,950 --> 00:11:03,980 但第二個字母 A保持不變。 261 00:11:03,980 --> 00:11:07,120 所以,我們要嘗試 弄清楚這是為什麼。 262 00:11:07,120 --> 00:11:10,440 所以,第一件事情,你通常 想要每次啟動GDB上做 263 00:11:10,440 --> 00:11:12,010 是從哪裡打破它。 264 00:11:12,010 --> 00:11:14,956 >> 因此,凱撒是一個很短的程序。 265 00:11:14,956 --> 00:11:16,330 我們只是有一個功能,對不對? 266 00:11:16,330 --> 00:11:18,520 什麼是我們的凱撒功能? 267 00:11:18,520 --> 00:11:19,590 268 00:11:19,590 --> 00:11:24,350 這裡只有一個功能,主要對不對? 269 00:11:24,350 --> 00:11:26,490 主要是功能 您的所有程序。 270 00:11:26,490 --> 00:11:29,230 如果沒有主,我可能會 是有點擔心,現在, 271 00:11:29,230 --> 00:11:31,000 但我希望你們都在那裡有主。 272 00:11:31,000 --> 00:11:34,150 所以,我們可以做的是,我們可以 剛剛突破主,就這樣。 273 00:11:34,150 --> 00:11:35,190 因此,它說,OK。 274 00:11:35,190 --> 00:11:37,430 我們設置了斷點,一個人也沒有。 275 00:11:37,430 --> 00:11:42,870 >> 所以,現在要記住的是凱撒 需要一個命令行參數的權利 276 00:11:42,870 --> 00:11:45,150 我們還沒有做到這一點還沒有任何地方。 277 00:11:45,150 --> 00:11:47,560 所以,你要做的就是當 你居然去跑 278 00:11:47,560 --> 00:11:51,540 該程序,你是任何程序 在GDB運行需要的命令行 279 00:11:51,540 --> 00:11:55,010 參數,你要輸入 當你第​​一次啟動運行它。 280 00:11:55,010 --> 00:11:59,280 所以,在這種情況下,我們做 與三支一鍵運行。 281 00:11:59,280 --> 00:12:00,770 282 00:12:00,770 --> 00:12:02,040 它會真正開始。 283 00:12:02,040 --> 00:12:08,480 >> 所以,如果你看到這裡,我們有 如果RC不等於2。 284 00:12:08,480 --> 00:12:12,210 所以,如果你們都 我送出了該文件 285 00:12:12,210 --> 00:12:15,100 你會看到,就像 第一行我們的主要功能,對不對? 286 00:12:15,100 --> 00:12:17,890 它的檢查,看看是否有 正確數目的參數。 287 00:12:17,890 --> 00:12:20,620 所以,如果你想知道 如果RC是正確的, 288 00:12:20,620 --> 00:12:23,250 你可以做一些事情,就像打印RC。 289 00:12:23,250 --> 00:12:24,380 290 00:12:24,380 --> 00:12:28,640 RC為2,這是 我們所預期的,對不對? 291 00:12:28,640 --> 00:12:32,010 >> 因此,我們可以去下, 並繼續通過。 292 00:12:32,010 --> 00:12:33,200 因此,我們有一些關鍵的有。 293 00:12:33,200 --> 00:12:34,260 294 00:12:34,260 --> 00:12:37,090 我們可以打印出我們的關鍵 以確保是正確的。 295 00:12:37,090 --> 00:12:38,380 296 00:12:38,380 --> 00:12:39,500 有意思的。 297 00:12:39,500 --> 00:12:41,210 並不完全符合我們的預期。 298 00:12:41,210 --> 00:12:44,810 所以,有一點認識 用GDB也,是 299 00:12:44,810 --> 00:12:49,000 它不是,直到你竟然打 接下來,你剛才看到的行 300 00:12:49,000 --> 00:12:50,720 實際執行。 301 00:12:50,720 --> 00:12:53,870 所以,在這種情況下關鍵 尚未分配愛好。 302 00:12:53,870 --> 00:12:57,050 所以,關鍵是一些垃圾的價值 您在底部有看到。 303 00:12:57,050 --> 00:13:03,680 負$ 120-- --IT堅持一個十億 和一些奇怪的事情吧? 304 00:13:03,680 --> 00:13:05,340 這不是我們所期望的關鍵。 305 00:13:05,340 --> 00:13:10,720 但是,如果我們點擊Next,然後我們 嘗試打印鍵,它是三種。 306 00:13:10,720 --> 00:13:11,710 >> 大家看到了嗎? 307 00:13:11,710 --> 00:13:13,780 所以,如果你得到的東西 那你喜歡,請等待。 308 00:13:13,780 --> 00:13:15,540 這是完全 錯了,我不知道 309 00:13:15,540 --> 00:13:20,150 怎麼會發生這種事,因為我想要的 做的是分配一個編號,變量 310 00:13:20,150 --> 00:13:22,900 試著打接下來,嘗試印刷 一遍,看看是否可行。 311 00:13:22,900 --> 00:13:27,830 因為它只會執行和 之後,你實際上分配的東西 312 00:13:27,830 --> 00:13:29,340 點擊Next。 313 00:13:29,340 --> 00:13:30,336 道理大家? 314 00:13:30,336 --> 00:13:30,836 嗯? 315 00:13:30,836 --> 00:13:33,220 >> 揚聲器2:當你隨意 數字是什麼意思呢? 316 00:13:33,220 --> 00:13:34,790 >> 揚聲器1:這只是隨機的。 317 00:13:34,790 --> 00:13:35,710 這只是垃圾。 318 00:13:35,710 --> 00:13:38,320 這只是一些你 電腦會隨機分配。 319 00:13:38,320 --> 00:13:39,721 320 00:13:39,721 --> 00:13:40,220 涼爽。 321 00:13:40,220 --> 00:13:45,760 所以,現在我們可以通過移動,等等 現在我們有這個純文本的GetString。 322 00:13:45,760 --> 00:13:48,600 所以,讓我介紹什麼 會發生什麼,當我們點擊Next這裡。 323 00:13:48,600 --> 00:13:51,320 種了GDB消失了,對不對? 324 00:13:51,320 --> 00:13:55,720 這是因為GetString的 現在執行的,對不對? 325 00:13:55,720 --> 00:14:01,460 所以,當我們看到純文本等於 GetString的,開放的括號和括號, 326 00:14:01,460 --> 00:14:04,380 和我們打接下來,有 實際執行了。 327 00:14:04,380 --> 00:14:06,580 因此,它在等待 我們輸入一些東西。 328 00:14:06,580 --> 00:14:13,560 >> 所以,我們要輸入我們的食物, 就是它的失敗,因為我告訴過你 329 00:14:13,560 --> 00:14:18,020 那只是說,這是 完成執行,該封閉 330 00:14:18,020 --> 00:14:19,980 支架是指它的 退出了該循環。 331 00:14:19,980 --> 00:14:21,170 332 00:14:21,170 --> 00:14:25,420 因此,我們可以接著打,而現在,因為我 確保你所有的從凱撒熟悉, 333 00:14:25,420 --> 00:14:27,260 這,這是什麼行會的事情。 334 00:14:27,260 --> 00:14:32,030 這對INT I等於0,N等於 strlen的,純文本,然後 335 00:14:32,030 --> 00:14:33,960 我是小於n,I,加,加。 336 00:14:33,960 --> 00:14:35,210 什麼是這個循環怎麼辦呢? 337 00:14:35,210 --> 00:14:37,900 338 00:14:37,900 --> 00:14:39,160 打開你的郵件。 339 00:14:39,160 --> 00:14:39,770 涼爽。 340 00:14:39,770 --> 00:14:41,330 那麼,讓我們開始這樣做。 341 00:14:41,330 --> 00:14:47,210 >> 因此,應此條件 匹配,我們的第一個? 342 00:14:47,210 --> 00:14:52,250 如果它是一個B,這是純文本格式一,我們 可以了解我們當地人的信息。 343 00:14:52,250 --> 00:14:53,610 344 00:14:53,610 --> 00:14:57,970 所以,我是零​​,而如果6,其 我們希望,我們的重點是三。 345 00:14:57,970 --> 00:14:59,227 所有這一切是有意義的,對嗎? 346 00:14:59,227 --> 00:15:01,310 這些數字都 正是他們應該的。 347 00:15:01,310 --> 00:15:02,590 348 00:15:02,590 --> 00:15:03,870 因此,哼? 349 00:15:03,870 --> 00:15:05,620 揚聲器3:我有 隨機數我的。 350 00:15:05,620 --> 00:15:09,156 351 00:15:09,156 --> 00:15:12,030 揚聲器1:嗯,我們可以check-- - 我們 可以聊,在第二。 352 00:15:12,030 --> 00:15:14,110 353 00:15:14,110 --> 00:15:15,750 但是,你應該得到這個。 354 00:15:15,750 --> 00:15:17,700 355 00:15:17,700 --> 00:15:20,130 所以,如果我們有一個資本 B我們的第一個, 356 00:15:20,130 --> 00:15:22,080 這種情況下應該抓住它,對不對? 357 00:15:22,080 --> 00:15:27,120 所以,如果我們打接下來,我們看到 這如果實際執行。 358 00:15:27,120 --> 00:15:29,220 因為如果你是以下 沿著你的代碼, 359 00:15:29,220 --> 00:15:33,460 這條線在這裡,在純文本我 替換為算術, 360 00:15:33,460 --> 00:15:35,720 僅當如果執行 條件是正確的嗎? 361 00:15:35,720 --> 00:15:36,905 362 00:15:36,905 --> 00:15:40,240 >> GDB只是要告訴你 這是實際執行的東西。 363 00:15:40,240 --> 00:15:45,140 所以,如果沒有達到這個如果條件下,它的 只是要跳到下一行。 364 00:15:45,140 --> 00:15:46,540 行? 365 00:15:46,540 --> 00:15:48,510 因此,我們有。 366 00:15:48,510 --> 00:15:51,171 這架意味著它 現在關閉了該循環。 367 00:15:51,171 --> 00:15:52,420 因此,它會重新開始。 368 00:15:52,420 --> 00:15:54,760 369 00:15:54,760 --> 00:15:56,280 就這樣。 370 00:15:56,280 --> 00:15:59,120 因此,我們可以得到的信息 關於我們當地人在這裡, 371 00:15:59,120 --> 00:16:02,575 我們看到,我們的第一個 信改變了,對不對? 372 00:16:02,575 --> 00:16:05,150 它現在是E,因為它應該是。 373 00:16:05,150 --> 00:16:07,360 因此,我們可以繼續。 374 00:16:07,360 --> 00:16:08,500 >> 我們有這個檢查。 375 00:16:08,500 --> 00:16:09,916 而這種檢查應該工作了吧? 376 00:16:09,916 --> 00:16:12,570 這是A.應該改變 三個字母前進。 377 00:16:12,570 --> 00:16:14,320 378 00:16:14,320 --> 00:16:16,530 但是,如果你注意到,我們 得到不同的東西。 379 00:16:16,530 --> 00:16:17,580 380 00:16:17,580 --> 00:16:22,860 所以在這種情況下在這裡,它抓 它,因此這條線執行, 381 00:16:22,860 --> 00:16:28,620 它修改了我們的B. 但是,在這裡這種情況下, 382 00:16:28,620 --> 00:16:32,860 我們認為它只是跳過它, 並到[? L SIFF。 ?] 383 00:16:32,860 --> 00:16:34,660 因此,一些對那裡發生。 384 00:16:34,660 --> 00:16:37,780 什麼是告訴你的是, 我們知道,它應該在這裡趕, 385 00:16:37,780 --> 00:16:39,200 但事實並非如此。 386 00:16:39,200 --> 00:16:42,210 任何人都可以看到我們的 問題是在該行? 387 00:16:42,210 --> 00:16:45,380 388 00:16:45,380 --> 00:16:46,969 這是一個非常微小的事情。 389 00:16:46,969 --> 00:16:48,510 你也可以看看你的代碼。 390 00:16:48,510 --> 00:16:49,980 391 00:16:49,980 --> 00:16:54,940 它也line--忘了這是什麼線 在那裡 - 但它在[聽不清]。 392 00:16:54,940 --> 00:16:55,480 是嗎? 393 00:16:55,480 --> 00:16:58,639 >> 揚聲器4:這是在比大 頁面,如果你在書中讀到它。 394 00:16:58,639 --> 00:16:59,430 揚聲器1:沒錯。 395 00:16:59,430 --> 00:17:02,620 所以,調試分不清楚 你說,但是調試器 396 00:17:02,620 --> 00:17:05,880 可以讓你下到一條線 你知道不正常。 397 00:17:05,880 --> 00:17:09,319 有時候,特別是當 後來在學期中,當 398 00:17:09,319 --> 00:17:12,910 你處理了一百,一 百幾行代碼,你 399 00:17:12,910 --> 00:17:16,190 不知道它的失敗, 這是一個偉大的方式來做到這一點。 400 00:17:16,190 --> 00:17:17,900 401 00:17:17,900 --> 00:17:18,989 所以,我們發現我們的錯誤。 402 00:17:18,989 --> 00:17:21,530 您可以修復它在你的文件, 然後,你可以再次運行它, 403 00:17:21,530 --> 00:17:23,029 一切都將正常工作。 404 00:17:23,029 --> 00:17:24,970 405 00:17:24,970 --> 00:17:30,590 而最重要的事情是 這似乎是,OK。 406 00:17:30,590 --> 00:17:31,090 是啊。 407 00:17:31,090 --> 00:17:31,370 涼爽。 408 00:17:31,370 --> 00:17:32,744 你知道你在尋找什麼。 409 00:17:32,744 --> 00:17:34,910 所以,你知道該怎麼做。 410 00:17:34,910 --> 00:17:39,021 >> GDB可能是因為你超級有幫助 可以打印出所有這些東西,你 411 00:17:39,021 --> 00:17:39,520 不會。 412 00:17:39,520 --> 00:17:41,160 它比的printf有用得多。 413 00:17:41,160 --> 00:17:43,440 你們有多少人使用 如printf語句 414 00:17:43,440 --> 00:17:46,200 找出其中的錯誤是,對不對? 415 00:17:46,200 --> 00:17:48,450 所以,這一點,你不 必須保持回去, 416 00:17:48,450 --> 00:17:51,139 和喜歡的評論 printf的,或者註釋掉, 417 00:17:51,139 --> 00:17:52,930 並找出哪些 你應該打印。 418 00:17:52,930 --> 00:17:55,670 這實際上只是讓你 步,打印出來的東西 419 00:17:55,670 --> 00:18:00,000 當你正在經歷,所以,你可以 觀察他們在現實時間的變化, 420 00:18:00,000 --> 00:18:02,190 因為你的程序正在運行。 421 00:18:02,190 --> 00:18:04,390 >> 它確實需要一點點 對習慣一下。 422 00:18:04,390 --> 00:18:07,850 我會強烈建議正中下懷 的是一個有點沮喪吧 423 00:18:07,850 --> 00:18:08,930 對於現在。 424 00:18:08,930 --> 00:18:13,450 如果你在花一個小時 下週學習如何使用GDB, 425 00:18:13,450 --> 00:18:16,140 你能救自己 如此多的時間以後。 426 00:18:16,140 --> 00:18:18,750 和字面上。告訴我們 這人年年有, 427 00:18:18,750 --> 00:18:23,890 我記得,當我把 類,我很喜歡,我會沒事的。 428 00:18:23,890 --> 00:18:24,700 號 429 00:18:24,700 --> 00:18:27,030 PSET 6來了,我是 喜歡,我要學習 430 00:18:27,030 --> 00:18:29,500 如何使用GDB,因為我不 知道是怎麼回事。 431 00:18:29,500 --> 00:18:32,940 >> 如果你花時間,所以, 使用它的小程序 432 00:18:32,940 --> 00:18:35,697 那你會是 工作,喜歡工作 433 00:18:35,697 --> 00:18:37,530 通過類似 Visionare,是這樣的。 434 00:18:37,530 --> 00:18:38,800 435 00:18:38,800 --> 00:18:42,850 或者,如果你想要額外的練習,我敢肯定, 我可以用bug的程序上來, 436 00:18:42,850 --> 00:18:45,300 為您調試,如果你願意的話​​。 437 00:18:45,300 --> 00:18:49,300 >> 但如果你只是需要一些時間來獲得 習慣了,只是玩它, 438 00:18:49,300 --> 00:18:50,550 它真的會滿足你的需要。 439 00:18:50,550 --> 00:18:52,591 而且它是真正的一個 那些東西,你只是 440 00:18:52,591 --> 00:18:57,340 必須嘗試,並得到你的手臟 用,在你真正了解它。 441 00:18:57,340 --> 00:19:02,090 我真的只聽懂了一次 我調試的東西吧, 442 00:19:02,090 --> 00:19:08,170 和它的更漂亮有一個想法 如何調試宜早不宜遲。 443 00:19:08,170 --> 00:19:08,850 行。 444 00:19:08,850 --> 00:19:09,625 涼爽。 445 00:19:09,625 --> 00:19:12,960 我知道這有點像 速成班GDB, 446 00:19:12,960 --> 00:19:16,400 我一定會努力的讓 這些看起來更大下一次。 447 00:19:16,400 --> 00:19:17,590 448 00:19:17,590 --> 00:19:18,280 涼爽。 449 00:19:18,280 --> 00:19:20,390 >> 所以,如果我們回到我們的PowerPoint。 450 00:19:20,390 --> 00:19:27,194 451 00:19:27,194 --> 00:19:28,110 這是去上班? 452 00:19:28,110 --> 00:19:29,711 453 00:19:29,711 --> 00:19:30,210 AWH。 454 00:19:30,210 --> 00:19:31,101 是。 455 00:19:31,101 --> 00:19:31,600 行。 456 00:19:31,600 --> 00:19:35,480 所以,如果你需要任何 這些再次,還有的列表。 457 00:19:35,480 --> 00:19:37,160 458 00:19:37,160 --> 00:19:40,830 所以二進制搜索,人人 記得大衛的偉大奇觀 459 00:19:40,830 --> 00:19:42,259 撕成兩半電話簿。 460 00:19:42,259 --> 00:19:44,050 我真的不明白了 電話簿了, 461 00:19:44,050 --> 00:19:46,530 因為喜歡你在哪裡 獲取電話簿可好? 462 00:19:46,530 --> 00:19:48,220 我真的不知道。 463 00:19:48,220 --> 00:19:49,840 464 00:19:49,840 --> 00:19:50,590 二進制搜索。 465 00:19:50,590 --> 00:19:52,464 有誰還記得 如何二進制搜索作品? 466 00:19:52,464 --> 00:19:54,380 467 00:19:54,380 --> 00:19:55,220 人呢? 468 00:19:55,220 --> 00:19:56,325 是嗎? 469 00:19:56,325 --> 00:19:58,283 揚聲器5:你知道什麼時候 你看看是哪一半 470 00:19:58,283 --> 00:20:01,146 這將是在,在此基礎上, 和擺脫的另一半。 471 00:20:01,146 --> 00:20:01,896 >> 揚聲器1沒錯。 472 00:20:01,896 --> 00:20:06,290 因此,二進制搜索,它是一種A-- - 我們喜歡叫它分而治之。 473 00:20:06,290 --> 00:20:09,170 所以,你要做的是 你將看到在中間, 474 00:20:09,170 --> 00:20:11,990 你會看它是否符合 您要查找的內容。 475 00:20:11,990 --> 00:20:15,420 如果沒有,那麼你嘗試 搞清楚,它是將要離開 476 00:20:15,420 --> 00:20:16,450 一半或右半部。 477 00:20:16,450 --> 00:20:19,325 所以,這可能是如果你正在尋找 在東西是按字母順序排列, 478 00:20:19,325 --> 00:20:20,720 你看,哦。 479 00:20:20,720 --> 00:20:22,750 難道佳佳來到先於M? 480 00:20:22,750 --> 00:20:23,250 是。 481 00:20:23,250 --> 00:20:25,030 所以,我們要 看看上半場。 482 00:20:25,030 --> 00:20:26,450 >> 或者它可能是像數字。 483 00:20:26,450 --> 00:20:28,830 什麼,你可以 比較,就可以進行排序。 484 00:20:28,830 --> 00:20:29,920 485 00:20:29,920 --> 00:20:31,260 您可以使用二進制搜索。 486 00:20:31,260 --> 00:20:32,340 487 00:20:32,340 --> 00:20:37,455 因此,任何人都記住了這個 圖表或這是什麼? 488 00:20:37,455 --> 00:20:39,520 這是漸近複雜性。 489 00:20:39,520 --> 00:20:42,830 因此,此圖只 介紹了多長時間 490 00:20:42,830 --> 00:20:46,230 你需要解決一個問題, 你增加多少東西 491 00:20:46,230 --> 00:20:47,090 您正在使用。 492 00:20:47,090 --> 00:20:51,260 >> 因此,我們有N個,其是直鏈的時間。 493 00:20:51,260 --> 00:20:54,560 如果N超過2,略 好,還是成長超快。 494 00:20:54,560 --> 00:20:58,360 然後我們登錄,這是 我們認為二分查找。 495 00:20:58,360 --> 00:21:03,630 如果我們注意到,作為您的問題 變多,大得多, 496 00:21:03,630 --> 00:21:06,600 它把你的時間來解決它 並沒有真正增加那麼多。 497 00:21:06,600 --> 00:21:09,010 這就像媲美 在這裡開始。 498 00:21:09,010 --> 00:21:10,060 你就像,OK。 499 00:21:10,060 --> 00:21:13,000 任何事情在這裡並沒有真正 無論哪一種我們使用, 500 00:21:13,000 --> 00:21:16,220 但你得到了一百萬,一十億。 501 00:21:16,220 --> 00:21:20,010 你想找到some-- --you're 試圖找到大海撈針。 502 00:21:20,010 --> 00:21:21,550 >> 我想你想這個問題。 503 00:21:21,550 --> 00:21:25,850 你想這種複雜性,不 線性的,因為所有你 504 00:21:25,850 --> 00:21:30,049 知道你會通過搜索來 每個單獨的針,乾草的事情, 505 00:21:30,049 --> 00:21:31,340 試圖尋找你的針。 506 00:21:31,340 --> 00:21:34,730 而這還不是在我看來,太好玩了。 507 00:21:34,730 --> 00:21:35,500 我喜歡快。 508 00:21:35,500 --> 00:21:36,620 我喜歡有效率。 509 00:21:36,620 --> 00:21:40,450 而作為勤奮的學生,你 傢伙,你知道的更聰明地工作, 510 00:21:40,450 --> 00:21:43,010 而不是更辛苦類型的事情,你怎麼 可以彌補這些算法。 511 00:21:43,010 --> 00:21:45,110 512 00:21:45,110 --> 00:21:47,910 >> 所以,我們要走路 僅僅通過一個簡單的例子。 513 00:21:47,910 --> 00:21:51,090 我想你們應該有 在二進制搜索手, 514 00:21:51,090 --> 00:21:54,352 但在任何情況下,一點點 模糊,要加強它, 515 00:21:54,352 --> 00:21:56,310 我們打算才行 通過這裡的例子。 516 00:21:56,310 --> 00:21:59,490 所以,我們要尋找的,如果 該數組包含七個。 517 00:21:59,490 --> 00:22:00,540 518 00:22:00,540 --> 00:22:06,010 >> 所以,我們首先要做的就是 看在中間,對不對? 519 00:22:06,010 --> 00:22:09,340 而且你要被編碼 在短短的二二分查找。 520 00:22:09,340 --> 00:22:11,310 因此,這將很有趣。 521 00:22:11,310 --> 00:22:13,710 因此,我們期待在 中間的小數組3。 522 00:22:13,710 --> 00:22:15,501 3是否等於7? 523 00:22:15,501 --> 00:22:16,000 沒有。 524 00:22:16,000 --> 00:22:18,670 525 00:22:18,670 --> 00:22:19,550 這是6。 526 00:22:19,550 --> 00:22:21,480 那麼,是不是小於 或大於7? 527 00:22:21,480 --> 00:22:23,080 528 00:22:23,080 --> 00:22:23,960 少於。 529 00:22:23,960 --> 00:22:24,570 是。 530 00:22:24,570 --> 00:22:25,170 幹得漂亮傢伙。 531 00:22:25,170 --> 00:22:25,569 532 00:22:25,569 --> 00:22:27,360 我覺得我我應該 有糖果,因為我 533 00:22:27,360 --> 00:22:29,460 想要把它伸到碼。 534 00:22:29,460 --> 00:22:30,270 這就是我將在下週的事。 535 00:22:30,270 --> 00:22:31,436 這將讓你們鋒利。 536 00:22:31,436 --> 00:22:32,560 537 00:22:32,560 --> 00:22:34,690 >> 所以,我們扔掉了 上半年,對不對? 538 00:22:34,690 --> 00:22:35,670 這是小於。 539 00:22:35,670 --> 00:22:39,325 我們知道,一切 在該左側 540 00:22:39,325 --> 00:22:41,700 將是小於什麼 我們實際上是在尋找。 541 00:22:41,700 --> 00:22:43,491 所以,沒有必要 注意它。 542 00:22:43,491 --> 00:22:45,120 忘掉它。 543 00:22:45,120 --> 00:22:48,720 所以,現在我們看一下我們的右手邊, 我們期待在中間那邊, 544 00:22:48,720 --> 00:22:50,510 現在它是9。 545 00:22:50,510 --> 00:22:55,510 因此,9 is-- --Everyone? 546 00:22:55,510 --> 00:22:57,470 比我們大 找了吧? 547 00:22:57,470 --> 00:22:59,860 因此,我們要扔掉 客場的一切權利。 548 00:22:59,860 --> 00:23:00,970 549 00:23:00,970 --> 00:23:01,940 這樣。 550 00:23:01,940 --> 00:23:03,700 現在,我們只剩下一個。 551 00:23:03,700 --> 00:23:07,760 所以我們檢查,是這個東西 我們正在尋找什麼?它是。 552 00:23:07,760 --> 00:23:08,970 我們發現我們想要的。 553 00:23:08,970 --> 00:23:10,440 554 00:23:10,440 --> 00:23:11,690 所以,我們就大功告成了。 555 00:23:11,690 --> 00:23:12,550 雙線性搜索。 556 00:23:12,550 --> 00:23:15,740 >> 如果你注意到,我們 有七個輸入存在。 557 00:23:15,740 --> 00:23:24,320 只花了我們喜歡的三倍, 但如果你正在做的像一個十億, 558 00:23:24,320 --> 00:23:28,190 你們知道要走多少步會 走,如果我們有四十億的事情呢? 559 00:23:28,190 --> 00:23:29,940 560 00:23:29,940 --> 00:23:30,455 任何猜測? 561 00:23:30,455 --> 00:23:32,286 562 00:23:32,286 --> 00:23:33,960 這是32。 563 00:23:33,960 --> 00:23:37,110 32步找到的東西 在四十億 564 00:23:37,110 --> 00:23:39,650 因為兩個大國的元素數組。 565 00:23:39,650 --> 00:23:43,550 所以,二是32個,是四十億。 566 00:23:43,550 --> 00:23:50,430 >> 所以很瘋狂怎麼你還在內 像一個相當小的數目的步驟 567 00:23:50,430 --> 00:23:52,650 找東西 four十億元素。 568 00:23:52,650 --> 00:23:55,730 所以,關於這一點,我們 將這個代碼 569 00:23:55,730 --> 00:23:58,950 所以你們其實可以 樣的了解其工作原理。 570 00:23:58,950 --> 00:24:01,520 好吧,讓你們可以代碼。 571 00:24:01,520 --> 00:24:04,100 我將讓你們 聊了一點點。 572 00:24:04,100 --> 00:24:07,970 了解你周圍的人,這是 從最後一節什麼人想要的。 573 00:24:07,970 --> 00:24:10,280 >> 所以,了解你周圍的人。 574 00:24:10,280 --> 00:24:11,305 聊了一點點。 575 00:24:11,305 --> 00:24:12,580 576 00:24:12,580 --> 00:24:15,730 和所有我想從你 你們現在只是 577 00:24:15,730 --> 00:24:17,575 嘗試創建偽代碼的輪廓。 578 00:24:17,575 --> 00:24:18,075 行? 579 00:24:18,075 --> 00:24:20,825 580 00:24:20,825 --> 00:24:21,325 哇。 581 00:24:21,325 --> 00:24:23,320 582 00:24:23,320 --> 00:24:29,520 所有我想從你們這些傢伙是你 只是要填補這一情況時。 583 00:24:29,520 --> 00:24:32,170 所以我已經設置了這些上 界和下界哪 584 00:24:32,170 --> 00:24:35,250 代表開始 我們的陣列和末端。 585 00:24:35,250 --> 00:24:40,440 而你要真正 遍歷並找出 586 00:24:40,440 --> 00:24:42,470 我們正在做的這個while循環中。 587 00:24:42,470 --> 00:24:45,810 >> 所以,如果你自己看著辦out--我 暗示那裡 - 是什麼情況 588 00:24:45,810 --> 00:24:46,640 我們有嗎? 589 00:24:46,640 --> 00:24:48,100 590 00:24:48,100 --> 00:24:51,560 所以,如果你想弄清楚的 的情況下,我們將這些偽 591 00:24:51,560 --> 00:24:53,350 然後我們就可以真的實現它們。 592 00:24:53,350 --> 00:24:55,330 而這將是我 想想,希望它會 593 00:24:55,330 --> 00:24:56,788 比預期的更容易一些。 594 00:24:56,788 --> 00:24:57,554 595 00:24:57,554 --> 00:25:00,220 因為它沒有那麼多的代碼, 其實,這是真的很酷。 596 00:25:00,220 --> 00:25:34,110 597 00:25:34,110 --> 00:25:35,018 >> 嗯? 598 00:25:35,018 --> 00:25:35,893 >> 學生:[聽不清]? 599 00:25:35,893 --> 00:25:36,984 600 00:25:36,984 --> 00:25:37,650 指導老師:是的。 601 00:25:37,650 --> 00:25:38,595 有一件事 發現在中間。 602 00:25:38,595 --> 00:25:39,552 >> 學生:所以我們可以使用它。 603 00:25:39,552 --> 00:25:39,770 行。 604 00:25:39,770 --> 00:25:40,603 >> 講師:完美。 605 00:25:40,603 --> 00:25:42,950 所以這是我們需要做的第一件事。 606 00:25:42,950 --> 00:25:44,330 所以,找到中間。 607 00:25:44,330 --> 00:25:45,415 608 00:25:45,415 --> 00:25:45,915 太好了。 609 00:25:45,915 --> 00:25:47,770 610 00:25:47,770 --> 00:25:55,010 所以,你有一個想法,我們怎麼可能 實際上找到的代碼中間? 611 00:25:55,010 --> 00:25:55,980 >> 學生:是啊。 612 00:25:55,980 --> 00:25:57,000 ñ超過2? 613 00:25:57,000 --> 00:25:58,500 614 00:25:58,500 --> 00:25:59,500 講師:因此n超過2。 615 00:25:59,500 --> 00:26:05,170 所以,有一點要記住的是, 你的上界和下界改變。 616 00:26:05,170 --> 00:26:08,110 我們不斷收縮的部分 數組的,我們正在尋找。 617 00:26:08,110 --> 00:26:11,970 因此n超過2只會工作 對於第一件事,我們做的。 618 00:26:11,970 --> 00:26:17,810 因此服用上下兼顧, 怎麼可能,我們得到了中量元素? 619 00:26:17,810 --> 00:26:20,640 因為我們想要中間 之間的上,下,右? 620 00:26:20,640 --> 00:26:21,730 621 00:26:21,730 --> 00:26:22,494 嗯? 622 00:26:22,494 --> 00:26:23,369 >> 學生:[聽不清]。 623 00:26:23,369 --> 00:26:26,170 624 00:26:26,170 --> 00:26:28,080 >> 講師:所以我們有一些中間。 625 00:26:28,080 --> 00:26:32,730 而這將是上加下超過2。 626 00:26:32,730 --> 00:26:34,740 627 00:26:34,740 --> 00:26:35,690 真棒。 628 00:26:35,690 --> 00:26:36,570 在那裡,我們走了。 629 00:26:36,570 --> 00:26:37,280 一號線下來。 630 00:26:37,280 --> 00:26:38,560 你們是在用自己的方式。 631 00:26:38,560 --> 00:26:41,400 所以,現在,我們有我們 中間,有什麼事我們想幹什麼? 632 00:26:41,400 --> 00:26:45,050 633 00:26:45,050 --> 00:26:45,900 只是一般。 634 00:26:45,900 --> 00:26:47,734 您不必編寫它。 635 00:26:47,734 --> 00:26:48,335 是。 636 00:26:48,335 --> 00:26:49,210 學生:[聽不清]? 637 00:26:49,210 --> 00:27:00,310 638 00:27:00,310 --> 00:27:10,310 講師:所以這是加,因為你 發現兩者之間的平均 639 00:27:10,310 --> 00:27:10,810 對他們。 640 00:27:10,810 --> 00:27:11,890 641 00:27:11,890 --> 00:27:17,370 所以,如果你認為它們是一種 在從側面增加, 642 00:27:17,370 --> 00:27:21,640 想想看,當你接近 中間,你想這樣的。 643 00:27:21,640 --> 00:27:27,150 所以,如果你是對的兩邊 中間,我們有像5和7。 644 00:27:27,150 --> 00:27:31,440 當你把它們加起來,你 得到12,你除以2,就是6。 645 00:27:31,440 --> 00:27:33,726 >> 有時候很難 解釋為什麼這樣的作品, 646 00:27:33,726 --> 00:27:35,600 但如果你的工作,通過 一個例子有時候, 647 00:27:35,600 --> 00:27:37,962 它會幫你計算出,如果 它應該是正或負。 648 00:27:37,962 --> 00:27:38,846 是。 649 00:27:38,846 --> 00:27:40,830 >> 學生:[聽不清] 恰好在中間 650 00:27:40,830 --> 00:27:43,950 如果他們的情況 還有很多小的數字 651 00:27:43,950 --> 00:27:45,860 而像一個大的數量? 652 00:27:45,860 --> 00:27:49,750 >> 講師:所以你需要 是陣列的中間。 653 00:27:49,750 --> 00:27:53,010 所以,如果你有一堆小數字 再一個真正大量 654 00:27:53,010 --> 00:27:54,799 在末端,也沒關係。 655 00:27:54,799 --> 00:27:56,840 所有的事情是, 他們排序,你只要 656 00:27:56,840 --> 00:27:59,339 想看看中間 數組是因為你還 657 00:27:59,339 --> 00:28:00,700 一半切片您的問題。 658 00:28:00,700 --> 00:28:03,020 659 00:28:03,020 --> 00:28:03,680 涼爽。 660 00:28:03,680 --> 00:28:06,430 所以,現在,我們有 中間,我們接下來做什麼? 661 00:28:06,430 --> 00:28:07,150 >> 學生:比較。 662 00:28:07,150 --> 00:28:08,150 講師:當比較。 663 00:28:08,150 --> 00:28:11,670 所以比較中間value_wanted。 664 00:28:11,670 --> 00:28:14,300 665 00:28:14,300 --> 00:28:15,160 涼爽。 666 00:28:15,160 --> 00:28:17,950 所以你看在這裡,我們有 我們要在這裡這個值。 667 00:28:17,950 --> 00:28:22,012 668 00:28:22,012 --> 00:28:23,095 請記住,這是一個數組。 669 00:28:23,095 --> 00:28:24,100 670 00:28:24,100 --> 00:28:26,970 所以中間是指索引。 671 00:28:26,970 --> 00:28:29,785 所以,我們要做的中間值。 672 00:28:29,785 --> 00:28:32,380 673 00:28:32,380 --> 00:28:35,650 如果你想不要忘記 比較,雙等號​​。 674 00:28:35,650 --> 00:28:38,250 你做單等於你 只是要重新分配它, 675 00:28:38,250 --> 00:28:41,090 然後,當然,它們也 會是你想要的值。 676 00:28:41,090 --> 00:28:42,300 所以,不要那樣做。 677 00:28:42,300 --> 00:28:44,350 >> 所以,我們要如果看 在中間的值 678 00:28:44,350 --> 00:28:46,460 等於我們想要的值。 679 00:28:46,460 --> 00:28:47,749 680 00:28:47,749 --> 00:28:48,790 不要忘了你的牙套。 681 00:28:48,790 --> 00:28:50,520 682 00:28:50,520 --> 00:28:52,235 Dropbox的應該消失。 683 00:28:52,235 --> 00:28:54,140 684 00:28:54,140 --> 00:28:56,200 那麼,我們在這種情況下怎麼辦? 685 00:28:56,200 --> 00:28:59,360 如果它是什麼,我們要回去呢? 686 00:28:59,360 --> 00:29:01,510 687 00:29:01,510 --> 00:29:02,626 我們想說的。 688 00:29:02,626 --> 00:29:03,440 >> 學生:打印關閉。 689 00:29:03,440 --> 00:29:05,314 >> 講師:嗯,我們 不想打印出來。 690 00:29:05,314 --> 00:29:08,220 因此,這是這裡的布爾值,因此我們 要返回true或false。 691 00:29:08,220 --> 00:29:12,280 我們要說的,就是這個號碼 一個[? RRA? ?]因此,如果它是, 692 00:29:12,280 --> 00:29:13,788 我們只是回到它真實的。 693 00:29:13,788 --> 00:29:16,780 694 00:29:16,780 --> 00:29:17,760 如果我能拼寫正確。 695 00:29:17,760 --> 00:29:18,830 696 00:29:18,830 --> 00:29:20,805 >> 學生:你為什麼不回零? 697 00:29:20,805 --> 00:29:22,930 講師:所以,你可以 返回零,如果你想要的。 698 00:29:22,930 --> 00:29:26,780 但在這種情況下,因為 我們的函數返回一個布爾值, 699 00:29:26,780 --> 00:29:28,962 我們需要返回true或false。 700 00:29:28,962 --> 00:29:30,920 學生:當你 話說布爾表達式, 701 00:29:30,920 --> 00:29:33,450 你可以將其設置為假? 702 00:29:33,450 --> 00:29:39,860 就像如果我想說,如果這種情況 沒有得到滿足時,象是上等於false。 703 00:29:39,860 --> 00:29:42,332 如果你只是將它理解 把假的另一邊? 704 00:29:42,332 --> 00:29:43,040 指導老師:是啊。 705 00:29:43,040 --> 00:29:44,820 因此,實際上,如果你 曾經做的事情 706 00:29:44,820 --> 00:29:49,600 象是上還是下, 返回true或false 707 00:29:49,600 --> 00:29:53,850 它實際上是不好的風格 比方說等於等於true或等於 708 00:29:53,850 --> 00:29:54,840 等於false。 709 00:29:54,840 --> 00:30:00,210 要使用該結果 因為本身你的支票。 710 00:30:00,210 --> 00:30:04,720 711 00:30:04,720 --> 00:30:05,860 不是我想要的。 712 00:30:05,860 --> 00:30:08,150 713 00:30:08,150 --> 00:30:09,240 這就是我想要的。 714 00:30:09,240 --> 00:30:13,205 所以,在你的情況你問 關於像保存在C。 715 00:30:13,205 --> 00:30:16,320 716 00:30:16,320 --> 00:30:25,150 >> 所以,如果我們有INT主要(無效) 而這樣的事情。 717 00:30:25,150 --> 00:30:31,922 你有,如果是上 一些輸入你的 718 00:30:31,922 --> 00:30:33,630 問如果你能做到 這樣的事情? 719 00:30:33,630 --> 00:30:35,010 720 00:30:35,010 --> 00:30:35,679 對不對? 721 00:30:35,679 --> 00:30:37,470 學生:我是想 要做到這一點[聽不清]。 722 00:30:37,470 --> 00:30:38,450 因為如果it's-- 723 00:30:38,450 --> 00:30:39,200 指導老師:對。 724 00:30:39,200 --> 00:30:41,197 所以,你希望這是假的,對不對? 725 00:30:41,197 --> 00:30:41,780 學生:是啊。 726 00:30:41,780 --> 00:30:45,960 講師:所以在這種情況下,你 希望它執行的,如果它是不正確的。 727 00:30:45,960 --> 00:30:50,510 所以,你在那裡做的很酷的事情是這樣的。 728 00:30:50,510 --> 00:30:52,900 729 00:30:52,900 --> 00:30:55,650 所以請記住驚嘆號 點否定的東西呢? 730 00:30:55,650 --> 00:30:58,270 它說[聽不清]表示不。 731 00:30:58,270 --> 00:31:03,590 因此,如果我們看一下剛剛 這部分在這裡,你會 732 00:31:03,590 --> 00:31:05,740 說,計算結果為 只要你想為false。 733 00:31:05,740 --> 00:31:06,790 734 00:31:06,790 --> 00:31:09,880 不是假的是真的, 這意味著將執行。 735 00:31:09,880 --> 00:31:11,037 這是否有道理? 736 00:31:11,037 --> 00:31:11,620 學生:是啊。 737 00:31:11,620 --> 00:31:12,453 講師:真棒。 738 00:31:12,453 --> 00:31:13,800 739 00:31:13,800 --> 00:31:14,300 行。 740 00:31:14,300 --> 00:31:16,330 因此,我們可以只返回 真在這種情況下。 741 00:31:16,330 --> 00:31:20,357 所以,現在我們有兩個 例在這種情況下。 742 00:31:20,357 --> 00:31:21,565 什麼是我們的另外兩個情況? 743 00:31:21,565 --> 00:31:31,610 744 00:31:31,610 --> 00:31:32,900 讓我們只是做這種方式。 745 00:31:32,900 --> 00:31:40,660 所以,讓我們開始其他 如果在中間值 746 00:31:40,660 --> 00:31:43,230 不到我們想要的值。 747 00:31:43,230 --> 00:31:47,200 748 00:31:47,200 --> 00:31:52,020 所以我們在中間的值小於 不是我們要尋找的價值。 749 00:31:52,020 --> 00:31:53,765 750 00:31:53,765 --> 00:31:56,720 >> 那麼,哪綁定你 我們認為要更新? 751 00:31:56,720 --> 00:31:57,870 752 00:31:57,870 --> 00:31:58,780 上或下? 753 00:31:58,780 --> 00:32:01,440 754 00:32:01,440 --> 00:32:01,940 上? 755 00:32:01,940 --> 00:32:03,230 756 00:32:03,230 --> 00:32:06,470 因此,該陣列的一側 我們將要在看什麼? 757 00:32:06,470 --> 00:32:07,500 >> 學生:下部。 758 00:32:07,500 --> 00:32:09,750 >> 教師:我們豈不是 可以看左邊。 759 00:32:09,750 --> 00:32:11,120 所以,如果別人沒有什麼價值較少。 760 00:32:11,120 --> 00:32:14,730 所以,你的中間值在這裡 不到我們想要的。 761 00:32:14,730 --> 00:32:17,202 因此,我們要採取 右側我們的陣列。 762 00:32:17,202 --> 00:32:18,910 所以,我們要 更新我們的下界。 763 00:32:18,910 --> 00:32:20,210 764 00:32:20,210 --> 00:32:23,020 因此,我們將重新分配我們的低。 765 00:32:23,020 --> 00:32:25,221 那你覺得下應該是什麼? 766 00:32:25,221 --> 00:32:26,304 學生:中間值? 767 00:32:26,304 --> 00:32:27,446 768 00:32:27,446 --> 00:32:28,820 講師:所以中間value-- 769 00:32:28,820 --> 00:32:30,136 學生:加1。 770 00:32:30,136 --> 00:32:31,010 講師:--plus 1。 771 00:32:31,010 --> 00:32:32,300 772 00:32:32,300 --> 00:32:34,380 誰能告訴我為什麼 我們有一個加1? 773 00:32:34,380 --> 00:32:35,730 >> 學生:[?沒有價值?] 更等於它。 774 00:32:35,730 --> 00:32:36,120 >> 指導老師:對。 775 00:32:36,120 --> 00:32:38,661 因為我們已經知道, 我們的中間值不等於 776 00:32:38,661 --> 00:32:42,750 它和我們要排除 所有後續搜索。 777 00:32:42,750 --> 00:32:46,360 如果你忘了加1,這 會喜歡無限循環。 778 00:32:46,360 --> 00:32:49,620 而你只是陷入了 無限循環,然後你就會出現段錯誤 779 00:32:49,620 --> 00:32:50,370 而事情變壞。 780 00:32:50,370 --> 00:32:54,780 因此,始終確保你不 其中包括價值,你只是 781 00:32:54,780 --> 00:32:55,380 看了看。 782 00:32:55,380 --> 00:32:58,530 因此,我們照顧與加1。 783 00:32:58,530 --> 00:33:04,840 >> 所以,現在我們有我們的最後一個條件 我總是為了安全著想 784 00:33:04,840 --> 00:33:12,664 您可以點擊這裡,否則,如果在值 中間的是大於該值 785 00:33:12,664 --> 00:33:13,163 我們想要的。 786 00:33:13,163 --> 00:33:16,260 787 00:33:16,260 --> 00:33:20,230 這意味著,我們要 左手一半。 788 00:33:20,230 --> 00:33:21,350 789 00:33:21,350 --> 00:33:23,260 那麼,哪一個我們要更新? 790 00:33:23,260 --> 00:33:23,760 上。 791 00:33:23,760 --> 00:33:25,470 792 00:33:25,470 --> 00:33:26,970 什麼是這個打算一樣的嗎? 793 00:33:26,970 --> 00:33:31,630 794 00:33:31,630 --> 00:33:33,690 中間減1,因為, 當然,我們要 795 00:33:33,690 --> 00:33:38,370 以確保我們不 再看那中間值。 796 00:33:38,370 --> 00:33:41,830 797 00:33:41,830 --> 00:33:45,110 然後,我們有它。 798 00:33:45,110 --> 00:33:45,610 就是這樣。 799 00:33:45,610 --> 00:33:46,820 這是所有的二進制搜索。 800 00:33:46,820 --> 00:33:48,190 這並不是說不好,對不對? 801 00:33:48,190 --> 00:33:51,590 這就像10行 用空格代碼。 802 00:33:51,590 --> 00:33:57,510 所以很強大,很實用,你會 在你以後的pset中的一個使用它。 803 00:33:57,510 --> 00:33:59,360 也許不是這一個,但後來。 804 00:33:59,360 --> 00:34:00,670 所以,學習它。 805 00:34:00,670 --> 00:34:01,510 愛它。 806 00:34:01,510 --> 00:34:02,980 它會善待你。 807 00:34:02,980 --> 00:34:05,370 因此,沒有人有任何 在二進制搜索的問題? 808 00:34:05,370 --> 00:34:06,196 是。 809 00:34:06,196 --> 00:34:09,840 >> 學生:它的問題 您是否n為偶數​​或奇數? 810 00:34:09,840 --> 00:34:10,750 >> 導師:第 811 00:34:10,750 --> 00:34:18,150 因為我們投它中間的 一個int,它只會截斷。 812 00:34:18,150 --> 00:34:21,600 所以它會留一個整數,它會 通過一切最終排序。 813 00:34:21,600 --> 00:34:23,909 所以,你不必擔心。 814 00:34:23,909 --> 00:34:24,580 大家好? 815 00:34:24,580 --> 00:34:25,659 816 00:34:25,659 --> 00:34:26,850 真棒。 817 00:34:26,850 --> 00:34:27,919 涼爽。 818 00:34:27,919 --> 00:34:30,836 所以,你們得到這個。 819 00:34:30,836 --> 00:34:33,380 820 00:34:33,380 --> 00:34:33,880 幻燈片。 821 00:34:33,880 --> 00:34:35,719 822 00:34:35,719 --> 00:34:43,270 因此,當我們在談論,我知道 大衛提到的複雜的運行時間。 823 00:34:43,270 --> 00:34:44,420 824 00:34:44,420 --> 00:34:50,340 >> 因此,在最好的情況下,它只是 1,我們稱之為恆定時間。 825 00:34:50,340 --> 00:34:51,909 誰能告訴我為什麼,可能是? 826 00:34:51,909 --> 00:34:52,969 827 00:34:52,969 --> 00:34:55,800 什麼類型的場景會是意味著什麼? 828 00:34:55,800 --> 00:34:58,260 829 00:34:58,260 --> 00:34:58,760 嗯。 830 00:34:58,760 --> 00:34:59,926 >> 學生:[聽不清] first-- 831 00:34:59,926 --> 00:35:00,789 832 00:35:00,789 --> 00:35:03,830 講師:所以中間作為 我們來到了第一個元素,對不對? 833 00:35:03,830 --> 00:35:08,167 這樣的一個數組或 無論我們正在尋找的只是 834 00:35:08,167 --> 00:35:09,750 正好是在中間嫌民建聯。 835 00:35:09,750 --> 00:35:11,190 836 00:35:11,190 --> 00:35:13,380 所以這是我們最好的情況。 837 00:35:13,380 --> 00:35:17,540 你進入真正的問題,恐怕不是 要達到[聽不清]經常。 838 00:35:17,540 --> 00:35:18,667 839 00:35:18,667 --> 00:35:19,750 那麼我們最壞的情況? 840 00:35:19,750 --> 00:35:21,270 我們最糟的情況是日誌ñ。 841 00:35:21,270 --> 00:35:25,360 並且,是因為有全 兩件事,我談到的權力。 842 00:35:25,360 --> 00:35:30,930 >> 所以在最壞的情況下這將意味著 我們不得不砍了下來陣列 843 00:35:30,930 --> 00:35:33,270 直到它是1的一個元素。 844 00:35:33,270 --> 00:35:34,810 845 00:35:34,810 --> 00:35:38,930 因此,我們不得不砍了下去一半 因為很多時候,我們可能會。 846 00:35:38,930 --> 00:35:41,430 這就是為什麼它的日誌N,因為 你只是保持除以二。 847 00:35:41,430 --> 00:35:42,890 848 00:35:42,890 --> 00:35:45,830 所以假設,你的東西 要知道,如果你曾經 849 00:35:45,830 --> 00:35:48,050 要使用二進制搜索。 850 00:35:48,050 --> 00:35:50,680 你必須元素進行排序。 851 00:35:50,680 --> 00:35:53,890 他們進行排序,因為 這是你唯一的出路 852 00:35:53,890 --> 00:35:57,060 可以知道,如果你能 扔了出來一半。 853 00:35:57,060 --> 00:36:00,260 >> 如果你有這個混亂的包包 號碼和你說, 854 00:36:00,260 --> 00:36:05,380 好了,我要去檢查中間 號碼和我正在尋找數 855 00:36:05,380 --> 00:36:08,510 小於說,我只是去 隨意扔掉一半。 856 00:36:08,510 --> 00:36:11,130 你不會知道你的 在另一半的數字。 857 00:36:11,130 --> 00:36:12,655 列表中的排序。 858 00:36:12,655 --> 00:36:14,030 859 00:36:14,030 --> 00:36:16,560 同樣,這可能是 要提前一點點, 860 00:36:16,560 --> 00:36:18,360 但你需要有隨機訪問。 861 00:36:18,360 --> 00:36:21,940 你需要能夠公正 去那個中間的元素。 862 00:36:21,940 --> 00:36:25,110 如果你必須遍歷 通過什麼 863 00:36:25,110 --> 00:36:28,630 或者你花額外的步驟 去了中間的元素, 864 00:36:28,630 --> 00:36:31,750 它沒有日誌N了,因為 您要添加更多的工作了進去。 865 00:36:31,750 --> 00:36:34,800 這將使一點 在兩週更有意義, 866 00:36:34,800 --> 00:36:37,950 但我就是那種想要前言, 給你們一個什麼樣的想法 867 00:36:37,950 --> 00:36:38,999 來。 868 00:36:38,999 --> 00:36:40,790 但就是這兩種 重要的假設 869 00:36:40,790 --> 00:36:44,804 你需要一個二進制名單。 870 00:36:44,804 --> 00:36:45,720 請確保它的排序。 871 00:36:45,720 --> 00:36:47,920 這是大個的 你們現在。 872 00:36:47,920 --> 00:36:52,170 和我們能進入 我們各種各樣的休息。 873 00:36:52,170 --> 00:36:56,444 所以4選擇產品類別泡沫, 插入,選擇和合併。 874 00:36:56,444 --> 00:36:57,485 他們都很酷。 875 00:36:57,485 --> 00:37:02,860 如果你們決定採取CS 124, 您將了解各種不爽。 876 00:37:02,860 --> 00:37:07,575 如果你是一個XKCD風扇,有 是一個非常酷的漫畫有關 877 00:37:07,575 --> 00:37:11,530 就像真的無效的種種,我 強烈建議你去看看。 878 00:37:11,530 --> 00:37:16,170 其中之一是喜歡那種恐慌,這 就像是,哦,不,返回隨機數組。 879 00:37:16,170 --> 00:37:16,991 關閉系統。 880 00:37:16,991 --> 00:37:17,490 離開。 881 00:37:17,490 --> 00:37:19,070 882 00:37:19,070 --> 00:37:21,500 所以古怪的幽默總是好的。 883 00:37:21,500 --> 00:37:22,620 884 00:37:22,620 --> 00:37:25,750 >> 因此,沒有人記得那種 像只是一個總體思路 885 00:37:25,750 --> 00:37:27,810 如何冒泡排序工作。 886 00:37:27,810 --> 00:37:31,130 887 00:37:31,130 --> 00:37:32,155 你還記得嗎? 888 00:37:32,155 --> 00:37:32,755 >> 學生:是啊。 889 00:37:32,755 --> 00:37:33,970 >> 講師:大膽試試吧。 890 00:37:33,970 --> 00:37:38,980 >> 學生:所以你要通過和 如果是做大,那麼你交換兩個。 891 00:37:38,980 --> 00:37:39,820 >> 指導老師:嗯。 892 00:37:39,820 --> 00:37:40,564 沒錯。 893 00:37:40,564 --> 00:37:41,730 所以你只要遍歷。 894 00:37:41,730 --> 00:37:43,050 您檢查兩個數字。 895 00:37:43,050 --> 00:37:46,510 如果前一個比較大 比一算賬, 896 00:37:46,510 --> 00:37:50,230 你只要將它們使得在 這樣一來所有的高數 897 00:37:50,230 --> 00:37:54,990 氣泡向著列表的末尾向上 和所有的數字低泡下來。 898 00:37:54,990 --> 00:37:59,355 >> 他有沒有告訴你傢伙很酷 音效分揀的視頻? 899 00:37:59,355 --> 00:38:00,480 這是一種很酷的。 900 00:38:00,480 --> 00:38:01,510 901 00:38:01,510 --> 00:38:05,200 所以羅伯特剛才說的,該算法 您在列表中只是一步, 902 00:38:05,200 --> 00:38:07,930 交換相鄰的值 如果他們不正常。 903 00:38:07,930 --> 00:38:10,975 然後自顧自地重複 直到你不作任何交換。 904 00:38:10,975 --> 00:38:11,990 905 00:38:11,990 --> 00:38:12,740 所以,還不錯吧? 906 00:38:12,740 --> 00:38:14,080 907 00:38:14,080 --> 00:38:16,319 所以我們只需要一個簡單的例子在這裡。 908 00:38:16,319 --> 00:38:18,360 所以,這是怎麼回事排序 他們按升序排列。 909 00:38:18,360 --> 00:38:19,470 910 00:38:19,470 --> 00:38:23,470 所以,當我們經過第一 時間,我們期待通過八個 911 00:38:23,470 --> 00:38:26,880 六顯然不 為了我們交換它們。 912 00:38:26,880 --> 00:38:27,985 >> 所以,看看下一個。 913 00:38:27,985 --> 00:38:29,430 八,以4沒有。 914 00:38:29,430 --> 00:38:30,450 交換它們。 915 00:38:30,450 --> 00:38:32,530 然後8兩,交換它們。 916 00:38:32,530 --> 00:38:33,470 在那裡,我們走了。 917 00:38:33,470 --> 00:38:39,519 所以,你第一遍之後,你 知道你最多 918 00:38:39,519 --> 00:38:41,810 將是一路 在頂部,因為它只是 919 00:38:41,810 --> 00:38:44,210 要不斷地 比一切更大 920 00:38:44,210 --> 00:38:46,810 它只是將泡沫 向上一路到底那裡。 921 00:38:46,810 --> 00:38:48,226 這是否有道理給大家? 922 00:38:48,226 --> 00:38:48,560 923 00:38:48,560 --> 00:38:49,060 涼爽。 924 00:38:49,060 --> 00:38:51,310 925 00:38:51,310 --> 00:38:53,920 >> 所以,接下來我們來看看我們的第二次。 926 00:38:53,920 --> 00:38:54,980 6個和4,開關。 927 00:38:54,980 --> 00:38:55,920 六兩,開關。 928 00:38:55,920 --> 00:38:58,700 現在我們有為了幾件事情。 929 00:38:58,700 --> 00:39:02,240 因此,對於每一個傳球,我們 讓我們的整個列表, 930 00:39:02,240 --> 00:39:06,320 我們知道,像許多號碼 在年底將被排序。 931 00:39:06,320 --> 00:39:07,690 932 00:39:07,690 --> 00:39:09,610 所以我們做了第三次, 這是一個交換。 933 00:39:09,610 --> 00:39:10,860 934 00:39:10,860 --> 00:39:15,910 然後在我們的第四個 過去,我們是零插槽。 935 00:39:15,910 --> 00:39:18,570 因此,我們知道,我們的 數組已排序。 936 00:39:18,570 --> 00:39:20,900 >> 那就是大 與冒泡排序的事情。 937 00:39:20,900 --> 00:39:23,720 我們知道,當我們 具有零掉期,即 938 00:39:23,720 --> 00:39:26,497 意味著一切 是完整的訂單。 939 00:39:26,497 --> 00:39:27,580 這是一種怎樣檢查。 940 00:39:27,580 --> 00:39:28,740 941 00:39:28,740 --> 00:39:36,480 因此,我們也要去泡代碼 排序也並不壞。 942 00:39:36,480 --> 00:39:38,120 這些都不是那麼糟糕。 943 00:39:38,120 --> 00:39:40,210 我知道他們看起來有點嚇人。 944 00:39:40,210 --> 00:39:42,124 我知道,當我把 類,甚至當我 945 00:39:42,124 --> 00:39:44,290 教的班 第一次,去年, 946 00:39:44,290 --> 00:39:46,165 我當時想,我該怎麼辦呢? 947 00:39:46,165 --> 00:39:48,540 是有意義的理論,但 我們如何真正做到這一點? 948 00:39:48,540 --> 00:39:51,420 這就是為什麼我還不想走 通過與你們這裡的代碼。 949 00:39:51,420 --> 00:39:54,915 所以,我有一個偽 對你們這段時間。 950 00:39:54,915 --> 00:39:55,950 951 00:39:55,950 --> 00:39:58,970 因此,只要記住這一點作為 我們要轉型了。 952 00:39:58,970 --> 00:40:04,210 因此,我們有一些反了 讓我們的掉期交易的軌道, 953 00:40:04,210 --> 00:40:08,370 因為我們需要確保 我們正在檢查。 954 00:40:08,370 --> 00:40:11,830 我們遍歷整個數組 因為我們只是做了這個例子。 955 00:40:11,830 --> 00:40:12,900 956 00:40:12,900 --> 00:40:17,325 如果元素之前大於 之後,我們是在元素, 957 00:40:17,325 --> 00:40:20,760 我們交換他們,我們增加我們的 計數器,因為只要我們交換, 958 00:40:20,760 --> 00:40:23,850 我們要讓我們的櫃檯都知道。 959 00:40:23,850 --> 00:40:26,247 有什麼問題嗎? 960 00:40:26,247 --> 00:40:27,580 有些事情似乎好笑在這裡。 961 00:40:27,580 --> 00:40:29,225 962 00:40:29,225 --> 00:40:32,350 學生:你設置計數器為零 每次經過循環? 963 00:40:32,350 --> 00:40:34,339 難道你不堅持下去 回零每次? 964 00:40:34,339 --> 00:40:35,505 講師:不一定。 965 00:40:35,505 --> 00:40:39,710 那麼,什麼情況是我們經過這裡。 966 00:40:39,710 --> 00:40:43,830 所以,做一段時間,記住,這 將執行一次沒有失敗。 967 00:40:43,830 --> 00:40:46,480 因此,它會設置 計數器等於零, 968 00:40:46,480 --> 00:40:48,070 然後,它會遍歷。 969 00:40:48,070 --> 00:40:50,590 由於它遍歷, 它會更新計數器。 970 00:40:50,590 --> 00:40:51,870 971 00:40:51,870 --> 00:40:56,900 由於它更新計數器,當它完成, 當它到達數組的末尾, 972 00:40:56,900 --> 00:41:00,830 如果我們的名單還沒有被排序, 計數器將被更新。 973 00:41:00,830 --> 00:41:01,840 974 00:41:01,840 --> 00:41:07,150 >> 那樣的話就檢查情況,並 說,OK,就是櫃檯大於零。 975 00:41:07,150 --> 00:41:09,290 如果是,再這樣做。 976 00:41:09,290 --> 00:41:14,340 要重置,這樣,當你 經過,計數器等於零。 977 00:41:14,340 --> 00:41:18,240 如果你通過一個排序 陣,沒有什麼變化, 978 00:41:18,240 --> 00:41:21,355 失敗了,你 返回的排序列表。 979 00:41:21,355 --> 00:41:23,104 980 00:41:23,104 --> 00:41:24,020 這是否有道理? 981 00:41:24,020 --> 00:41:24,940 982 00:41:24,940 --> 00:41:26,356 學生:它可能在一點點。 983 00:41:26,356 --> 00:41:27,147 講師:OK。 984 00:41:27,147 --> 00:41:28,980 如果有任何其他 問題的出現​​。 985 00:41:28,980 --> 00:41:30,180 986 00:41:30,180 --> 00:41:30,680 是。 987 00:41:30,680 --> 00:41:33,760 >> 學生:你會的功能 對於交換的元素呢? 988 00:41:33,760 --> 00:41:36,900 >> 講師:所以我們其實可以寫 如果我們現在要的權利。 989 00:41:36,900 --> 00:41:37,801 990 00:41:37,801 --> 00:41:38,300 涼爽。 991 00:41:38,300 --> 00:41:42,155 所以,關於這一點,艾莉森是怎麼回事 切換回設備。 992 00:41:42,155 --> 00:41:43,080 這將很有趣。 993 00:41:43,080 --> 00:41:45,170 994 00:41:45,170 --> 00:41:47,390 我們有我們的好 在這裡冒泡排序的事情。 995 00:41:47,390 --> 00:41:50,800 所以,我已經做了騎自行車 通過該陣列。 996 00:41:50,800 --> 00:41:53,030 我們有我們互換了 都等於零。 997 00:41:53,030 --> 00:41:54,480 998 00:41:54,480 --> 00:41:58,440 因此,我們要交換相鄰 元素,如果他們太過份了。 999 00:41:58,440 --> 00:42:03,020 所以,第一件事,我們需要 做的是通過我們的數組遍歷。 1000 00:42:03,020 --> 00:42:04,500 1001 00:42:04,500 --> 00:42:08,260 >> 那麼,你如何認為我們也許 通過我們遍歷數組? 1002 00:42:08,260 --> 00:42:09,720 1003 00:42:09,720 --> 00:42:13,990 我們有和我等於0。 1004 00:42:13,990 --> 00:42:16,950 1005 00:42:16,950 --> 00:42:22,454 我們希望我要少 大於n減1負ķ。 1006 00:42:22,454 --> 00:42:23,870 我會解釋說,在第二。 1007 00:42:23,870 --> 00:42:26,280 1008 00:42:26,280 --> 00:42:32,830 所以這是一個最優化在這些地方, 記得我每次傳球後是怎麼說的 1009 00:42:32,830 --> 00:42:36,655 通過數組我們 知道什麼是on-- 1010 00:42:36,655 --> 00:42:43,590 1011 00:42:43,590 --> 00:42:46,295 >> 打完一遍我們 知道這是排序。 1012 00:42:46,295 --> 00:42:47,370 1013 00:42:47,370 --> 00:42:50,060 經過兩道我們知道 這一切進行排序。 1014 00:42:50,060 --> 00:42:52,750 經過三關我們 知道的排序。 1015 00:42:52,750 --> 00:42:55,620 所以,我現在的迭代 通過陣列這裡, 1016 00:42:55,620 --> 00:43:01,090 是它確保只有走 通過我們所知道的是未排序的。 1017 00:43:01,090 --> 00:43:01,644 行? 1018 00:43:01,644 --> 00:43:02,810 這只是一個優化。 1019 00:43:02,810 --> 00:43:04,430 1020 00:43:04,430 --> 00:43:08,210 你可以寫它只是天真 通過迭代的一切, 1021 00:43:08,210 --> 00:43:09,970 它只是需要更長的時間。 1022 00:43:09,970 --> 00:43:12,470 與此四環路是 一個不錯的優化 1023 00:43:12,470 --> 00:43:18,460 因為我們知道,以後每滿 通過數組迭代這裡, 1024 00:43:18,460 --> 00:43:24,050 喜歡這裡的每一個完整的循環,我們知道 一個多這些元素 1025 00:43:24,050 --> 00:43:25,760 在最後進行排序。 1026 00:43:25,760 --> 00:43:28,294 >> 所以我們不必擔心這些。 1027 00:43:28,294 --> 00:43:29,710 這是否有道理給大家? 1028 00:43:29,710 --> 00:43:30,950 很酷的小把戲? 1029 00:43:30,950 --> 00:43:32,060 1030 00:43:32,060 --> 00:43:37,270 因此,在這種情況下,如果 我們通過迭代, 1031 00:43:37,270 --> 00:43:50,590 我們知道,我們要檢查 數組n和n加1是為了。 1032 00:43:50,590 --> 00:43:52,640 1033 00:43:52,640 --> 00:43:53,559 行。 1034 00:43:53,559 --> 00:43:54,600 因此,這裡的偽代碼。 1035 00:43:54,600 --> 00:43:57,540 我們要檢查數組ñ 和N加1是為了。 1036 00:43:57,540 --> 00:43:59,520 那麼,什麼可能我們有嗎? 1037 00:43:59,520 --> 00:44:01,090 1038 00:44:01,090 --> 00:44:03,120 這將是一些條件。 1039 00:44:03,120 --> 00:44:04,220 這將是如果一個。 1040 00:44:04,220 --> 00:44:07,066 >> 學生:如果array n是 比數組n​​與1少。 1041 00:44:07,066 --> 00:44:07,816 指導老師:嗯。 1042 00:44:07,816 --> 00:44:09,000 1043 00:44:09,000 --> 00:44:10,699 那麼,小於或大於。 1044 00:44:10,699 --> 00:44:11,615 學生:大於。 1045 00:44:11,615 --> 00:44:15,850 1046 00:44:15,850 --> 00:44:17,620 然後,我們要交換他們。 1047 00:44:17,620 --> 00:44:18,570 沒錯。 1048 00:44:18,570 --> 00:44:23,570 所以,現在我們進入有什麼 機制交換呢? 1049 00:44:23,570 --> 00:44:24,840 1050 00:44:24,840 --> 00:44:28,137 因此,我們通過這個簡短去了, 一種交換功能的最後一周。 1051 00:44:28,137 --> 00:44:29,595 有誰還記得它是如何工作的? 1052 00:44:29,595 --> 00:44:32,300 1053 00:44:32,300 --> 00:44:34,950 因此,我們不能只是重新分配,對不對? 1054 00:44:34,950 --> 00:44:36,640 因為其中一人將得到丟失。 1055 00:44:36,640 --> 00:44:41,696 如果我們說,A等於B,然後B 等於A,突然兩個人 1056 00:44:41,696 --> 00:44:43,150 只是等於B. 1057 00:44:43,150 --> 00:44:45,720 >> 所以,我們要做的是我們 有一個臨時變量,是 1058 00:44:45,720 --> 00:44:49,055 將要舉辦的我們,而一個 我們在交換的過程中。 1059 00:44:49,055 --> 00:44:50,200 1060 00:44:50,200 --> 00:44:56,464 所以,我們所擁有的是我們有一些INT 溫度等於to--你可以指定它 1061 00:44:56,464 --> 00:44:59,130 到任何一個你想要的,只是 請確保你跟踪它 - 的 1062 00:44:59,130 --> 00:45:01,840 所以在這種情況下,我要去 它分配給數組n與1。 1063 00:45:01,840 --> 00:45:03,360 1064 00:45:03,360 --> 00:45:07,674 所以這是將要舉辦什麼 值是在該第二塊 1065 00:45:07,674 --> 00:45:08,590 我們正在尋找。 1066 00:45:08,590 --> 00:45:09,700 1067 00:45:09,700 --> 00:45:13,240 >> 然後我們可以做的是,我們可以去 提前並重新分配數組n與1, 1068 00:45:13,240 --> 00:45:14,990 因為我們知道,我們 有存儲該值。 1069 00:45:14,990 --> 00:45:16,645 1070 00:45:16,645 --> 00:45:19,270 這也是大的一個 things--我不知道你們中的任何 1071 00:45:19,270 --> 00:45:23,780 曾:如果你切換的兩個問題 代碼行突然事情的來龍去脈。 1072 00:45:23,780 --> 00:45:25,880 為了在CS非常重要的。 1073 00:45:25,880 --> 00:45:29,450 所以一定要確保你關係圖 事情是否可能 1074 00:45:29,450 --> 00:45:31,230 至於什麼是實際發生的事情。 1075 00:45:31,230 --> 00:45:34,256 所以,現在我們要 重新分配數組n與1, 1076 00:45:34,256 --> 00:45:36,005 因為我們知道,我們 有存儲該值。 1077 00:45:36,005 --> 00:45:37,090 1078 00:45:37,090 --> 00:45:41,560 >> 我們可以將它賦值給數組 在這種情況下,陣列I n或。 1079 00:45:41,560 --> 00:45:50,540 1080 00:45:50,540 --> 00:45:51,465 太多的變數。 1081 00:45:51,465 --> 00:45:54,230 1082 00:45:54,230 --> 00:45:55,470 行。 1083 00:45:55,470 --> 00:46:01,500 所以,現在我們已經重新分配數組我 加1等於什麼陣我。 1084 00:46:01,500 --> 00:46:08,240 現在我們可以回去 分配數組我的是什麼? 1085 00:46:08,240 --> 00:46:10,680 1086 00:46:10,680 --> 00:46:11,180 任何人嗎? 1087 00:46:11,180 --> 00:46:13,490 1088 00:46:13,490 --> 00:46:14,010 >> 學生:10。 1089 00:46:14,010 --> 00:46:14,680 >> 講師:10。 1090 00:46:14,680 --> 00:46:15,180 沒錯。 1091 00:46:15,180 --> 00:46:16,930 1092 00:46:16,930 --> 00:46:18,640 而最後一件事。 1093 00:46:18,640 --> 00:46:21,840 如果我們現在已經換了, 什麼,我們需要做什麼? 1094 00:46:21,840 --> 00:46:23,740 什麼是一件事 這是怎麼回事告訴我們 1095 00:46:23,740 --> 00:46:27,542 如果我們終止這項計劃? 1096 00:46:27,542 --> 00:46:29,250 什麼告訴我們 有一個排序的列表? 1097 00:46:29,250 --> 00:46:31,560 1098 00:46:31,560 --> 00:46:33,750 如果我們不進行任何交換,對不對? 1099 00:46:33,750 --> 00:46:36,900 如果互換等於 在此結束零。 1100 00:46:36,900 --> 00:46:42,975 所以每當你完成一個交換,因為我們 只是在這裡做,我們要更新掉。 1101 00:46:42,975 --> 00:46:45,002 1102 00:46:45,002 --> 00:46:47,210 我知道有一個 剛才的問題能左右你 1103 00:46:47,210 --> 00:46:49,689 用零次或一次,而不是 true或false。 1104 00:46:49,689 --> 00:46:50,980 而這正是這並不在這裡。 1105 00:46:50,980 --> 00:46:52,750 因此,這如果不是掉期說。 1106 00:46:52,750 --> 00:47:01,310 所以,如果掉期為零,這is--我總是 讓我的真理,我falses混淆。 1107 00:47:01,310 --> 00:47:03,960 我們希望我們能夠評估 以真實,事實並非如此。 1108 00:47:03,960 --> 00:47:07,680 1109 00:47:07,680 --> 00:47:09,630 所以,如果是零,那麼它是假的。 1110 00:47:09,630 --> 00:47:12,560 如果你有一個否定它 [?一聲?]成為事實。 1111 00:47:12,560 --> 00:47:13,975 那麼接下來這條線執行。 1112 00:47:13,975 --> 00:47:15,060 1113 00:47:15,060 --> 00:47:17,370 >> 真理與虛假, 零和一弄瘋了。 1114 00:47:17,370 --> 00:47:20,690 只是,如果你慢慢走 通過它它才有意義。 1115 00:47:20,690 --> 00:47:23,320 但是,這就是這個小 代碼位在這裡呢。 1116 00:47:23,320 --> 00:47:26,490 因此,這將檢查 我們做任何交換。 1117 00:47:26,490 --> 00:47:30,054 所以,如果它的任何東西,除了 零,這將是錯誤的 1118 00:47:30,054 --> 00:47:31,970 而整個事情是 要再次執行。 1119 00:47:31,970 --> 00:47:33,150 1120 00:47:33,150 --> 00:47:33,650 很酷吧? 1121 00:47:33,650 --> 00:47:34,660 1122 00:47:34,660 --> 00:47:36,000 >> 學生:什麼突破呢? 1123 00:47:36,000 --> 00:47:38,990 >> 講師:剛剛突破 打破你跳出循環。 1124 00:47:38,990 --> 00:47:41,570 所以在這種情況下,它會 只是想結束程序 1125 00:47:41,570 --> 00:47:43,828 而你只想 有你的排序列表。 1126 00:47:43,828 --> 00:47:44,536 學生:驚人的。 1127 00:47:44,536 --> 00:47:48,094 1128 00:47:48,094 --> 00:47:49,010 講師:對不起? 1129 00:47:49,010 --> 00:47:52,110 學生:因為以前我們 用過寫1比寫零 1130 00:47:52,110 --> 00:47:54,170 提出,如果 將工作或沒有。 1131 00:47:54,170 --> 00:47:54,878 >> 指導老師:是啊。 1132 00:47:54,878 --> 00:47:56,410 所以,你可以返回零個或1。 1133 00:47:56,410 --> 00:47:58,950 在這種情況下,因為我們沒有真正 做什麼用的功能, 1134 00:47:58,950 --> 00:48:00,150 我們只是希望它打破。 1135 00:48:00,150 --> 00:48:02,680 我們真的不關心它。 1136 00:48:02,680 --> 00:48:06,960 剎車也不錯,如果 它是用於突破 1137 00:48:06,960 --> 00:48:10,710 四個環或條件的那 你不希望繼續執行。 1138 00:48:10,710 --> 00:48:12,110 它只是需要你了出來。 1139 00:48:12,110 --> 00:48:13,587 1140 00:48:13,587 --> 00:48:14,795 這是一個有點細微的事情。 1141 00:48:14,795 --> 00:48:16,737 1142 00:48:16,737 --> 00:48:18,445 我覺得有 很多擺手的, 1143 00:48:18,445 --> 00:48:19,740 就像你將了解這一聲。 1144 00:48:19,740 --> 00:48:20,955 >> 但是,你將了解這一聲。 1145 00:48:20,955 --> 00:48:21,500 我保證。 1146 00:48:21,500 --> 00:48:22,670 1147 00:48:22,670 --> 00:48:23,170 行。 1148 00:48:23,170 --> 00:48:24,840 因此,每個人都得到冒泡排序? 1149 00:48:24,840 --> 00:48:25,550 差不太多。 1150 00:48:25,550 --> 00:48:31,910 遍歷,使用交換的東西 臨時變量,我們都設在那裡? 1151 00:48:31,910 --> 00:48:32,960 涼爽。 1152 00:48:32,960 --> 00:48:34,080 真棒。 1153 00:48:34,080 --> 00:48:34,807 行。 1154 00:48:34,807 --> 00:48:35,765 回到PowerPoint文件。 1155 00:48:35,765 --> 00:48:38,140 1156 00:48:38,140 --> 00:48:40,130 一般來說任何問題 這些這麼遠嗎? 1157 00:48:40,130 --> 00:48:41,200 1158 00:48:41,200 --> 00:48:41,700 涼爽。 1159 00:48:41,700 --> 00:48:43,110 1160 00:48:43,110 --> 00:48:43,695 嗯。 1161 00:48:43,695 --> 00:48:45,279 >> 學生:[聽不清]詮釋主通常。 1162 00:48:45,279 --> 00:48:46,695 你必須有這個? 1163 00:48:46,695 --> 00:48:48,400 1164 00:48:48,400 --> 00:48:53,550 >> 講師:所以我們只是在尋找 只是在實際的排序算法。 1165 00:48:53,550 --> 00:48:54,559 1166 00:48:54,559 --> 00:48:56,350 如果你在有它 像一個更大的程序, 1167 00:48:56,350 --> 00:48:57,891 你將有一個int的主要地方。 1168 00:48:57,891 --> 00:49:00,070 1169 00:49:00,070 --> 00:49:02,880 這取決於你在哪裡 使用這種算法, 1170 00:49:02,880 --> 00:49:05,860 這將決定什麼 由它返回。 1171 00:49:05,860 --> 00:49:09,960 但對於我們而言,我們是嚴格 著眼於如何真正做這個 1172 00:49:09,960 --> 00:49:11,300 遍歷數組。 1173 00:49:11,300 --> 00:49:12,570 所以,我們並不擔心。 1174 00:49:12,570 --> 00:49:14,150 1175 00:49:14,150 --> 00:49:19,830 >> 因此,我們在談論最好的情況和 最壞的情況下為二進制搜索。 1176 00:49:19,830 --> 00:49:22,470 因此,這也是非常重要的做 對於每一個我們的排序。 1177 00:49:22,470 --> 00:49:24,200 1178 00:49:24,200 --> 00:49:27,560 所以你認為是什麼做的是最差的 冒泡排序的情況下運行? 1179 00:49:27,560 --> 00:49:29,560 1180 00:49:29,560 --> 00:49:30,700 你們還記得嗎? 1181 00:49:30,700 --> 00:49:31,784 >> 學生:N減1。 1182 00:49:31,784 --> 00:49:32,700 講師:N減1。 1183 00:49:32,700 --> 00:49:35,070 因此,這意味著有 ñ減1的比較。 1184 00:49:35,070 --> 00:49:40,060 所以,有一點認識是 即在第一次迭代中, 1185 00:49:40,060 --> 00:49:43,360 我們經歷,我們比較 這些two--所以這是1。 1186 00:49:43,360 --> 00:49:46,685 這兩個,三個,四個。 1187 00:49:46,685 --> 00:49:48,070 1188 00:49:48,070 --> 00:49:55,050 所以一次迭代後,我們 已經有四個比較。 1189 00:49:55,050 --> 00:49:58,230 當我說的是運行和n。 1190 00:49:58,230 --> 00:50:04,680 N表示比較的數量 有多少元素的函數 1191 00:50:04,680 --> 00:50:05,570 我們有。 1192 00:50:05,570 --> 00:50:06,430 行? 1193 00:50:06,430 --> 00:50:08,860 >> 因此,我們過不去,我們有四個。 1194 00:50:08,860 --> 00:50:11,780 下一次當你知道我們不 要利用這一服務。 1195 00:50:11,780 --> 00:50:15,140 我們比較這兩個, 這兩個,這兩個, 1196 00:50:15,140 --> 00:50:20,050 如果我們沒有這個優化 與四循環,我寫的, 1197 00:50:20,050 --> 00:50:22,750 你會比較這裡反正。 1198 00:50:22,750 --> 00:50:26,170 所以,你必須 通過陣列上運行 1199 00:50:26,170 --> 00:50:34,380 而從N比較ñ 次,因為每次我們 1200 00:50:34,380 --> 00:50:36,670 運行通過它我們排序的一件事。 1201 00:50:36,670 --> 00:50:38,300 1202 00:50:38,300 --> 00:50:41,475 >> 每次我們通過運行時間 數組,我們從N比較。 1203 00:50:41,475 --> 00:50:42,920 1204 00:50:42,920 --> 00:50:46,330 因此,我們運行的是 實際上Ñ平方,其中 1205 00:50:46,330 --> 00:50:48,400 是更糟糕了 日誌末尾,因為這 1206 00:50:48,400 --> 00:50:51,965 也就是說,如果我們有四個 十億元素,它的 1207 00:50:51,965 --> 00:50:55,260 我們要花費four十億 平方,而不是32。 1208 00:50:55,260 --> 00:51:01,240 所以不是最好的運行時間, 但對於某些事情, 1209 00:51:01,240 --> 00:51:04,610 你知道,如果你是內 在一定範圍內的元素 1210 00:51:04,610 --> 00:51:06,540 冒泡排序可能會比較好用。 1211 00:51:06,540 --> 00:51:07,530 >> 行。 1212 00:51:07,530 --> 00:51:12,290 所以,現在什麼是最好的情況下運行? 1213 00:51:12,290 --> 00:51:14,357 1214 00:51:14,357 --> 00:51:14,940 學生:零? 1215 00:51:14,940 --> 00:51:16,420 還是1? 1216 00:51:16,420 --> 00:51:18,140 >> 教師:那麼1人 是一次比較。 1217 00:51:18,140 --> 00:51:19,114 右。 1218 00:51:19,114 --> 00:51:20,002 >> 學生:N減1? 1219 00:51:20,002 --> 00:51:21,380 1220 00:51:21,380 --> 00:51:22,320 >> 講師:所以,是的。 1221 00:51:22,320 --> 00:51:22,990 因此n減1。 1222 00:51:22,990 --> 00:51:26,510 當你有一個像N A概念 減去1,我們往往只是把它關閉 1223 00:51:26,510 --> 00:51:31,680 我們只說N,因為你有 比較每個these--每對。 1224 00:51:31,680 --> 00:51:36,470 所以它會為n減去1,這是我們 我們剛剛說的是大約ñ。 1225 00:51:36,470 --> 00:51:39,280 當你正在處理的運行時間, 一切都在接近。 1226 00:51:39,280 --> 00:51:43,860 只要指數是 正確的,你很不錯。 1227 00:51:43,860 --> 00:51:45,700 >> 這就是我們如何處理它。 1228 00:51:45,700 --> 00:51:47,410 1229 00:51:47,410 --> 00:51:51,780 所以,最好的情況下是n,這 意味著該列表已經排序, 1230 00:51:51,780 --> 00:51:54,320 而我們要做的就是通過運行 並檢查它的排序。 1231 00:51:54,320 --> 00:51:56,110 1232 00:51:56,110 --> 00:51:56,855 涼爽。 1233 00:51:56,855 --> 00:51:57,355 行。 1234 00:51:57,355 --> 00:51:58,980 1235 00:51:58,980 --> 00:52:01,920 所以,當你看到這裡,我們 只是有一些更多的圖形。 1236 00:52:01,920 --> 00:52:02,660 因此n的平方。 1237 00:52:02,660 --> 00:52:03,780 1238 00:52:03,780 --> 00:52:05,120 好玩的。 1239 00:52:05,120 --> 00:52:09,730 遠小於n更糟,因為我們看到了, 多,比數2n個糟糕得多。 1240 00:52:09,730 --> 00:52:12,060 然後你也進入日誌記錄。 1241 00:52:12,060 --> 00:52:18,020 你拿124,你進入 像日誌的明星,這是像瘋了似的。 1242 00:52:18,020 --> 00:52:20,172 所以,如果你有興趣, 查詢日誌的明星。 1243 00:52:20,172 --> 00:52:20,880 這是一種樂趣。 1244 00:52:20,880 --> 00:52:22,800 1245 00:52:22,800 --> 00:52:24,220 因此,我們有這個偉大的圖表。 1246 00:52:24,220 --> 00:52:25,360 1247 00:52:25,360 --> 00:52:28,720 只是抬起頭,這是一個 精彩圖有 1248 00:52:28,720 --> 00:52:31,350 為您的中期,因為我們 長問你這些變薄。 1249 00:52:31,350 --> 00:52:36,090 所以才抬起頭來,這個對你 對你的好小抄中期 1250 00:52:36,090 --> 00:52:36,616 那裡。 1251 00:52:36,616 --> 00:52:37,990 所以,我們只是看著冒泡排序。 1252 00:52:37,990 --> 00:52:39,510 1253 00:52:39,510 --> 00:52:42,370 最壞的情況下,N的平方,最好的情況下,N。 1254 00:52:42,370 --> 00:52:43,367 1255 00:52:43,367 --> 00:52:44,950 而且我們要看看其他人。 1256 00:52:44,950 --> 00:52:47,940 >> 正如你所看到的,唯一的 一個真正做得好 1257 00:52:47,940 --> 00:52:50,910 是歸併排序,我們將進入的原因。 1258 00:52:50,910 --> 00:52:52,690 1259 00:52:52,690 --> 00:52:55,215 所以我們要去的 下一個這裡 - 選擇排序。 1260 00:52:55,215 --> 00:52:56,360 1261 00:52:56,360 --> 00:52:58,420 有誰還記得 選擇排序工作? 1262 00:52:58,420 --> 00:53:05,200 1263 00:53:05,200 --> 00:53:05,700 去了。 1264 00:53:05,700 --> 00:53:08,210 >> 學生:基本上經歷 一種秩序,創造一個新的列表。 1265 00:53:08,210 --> 00:53:11,001 而且,正如你把元素 中,把他們在正確的地方 1266 00:53:11,001 --> 00:53:11,750 在新的清單。 1267 00:53:11,750 --> 00:53:14,040 >> 講師:這樣的聲音 更像是插入排序。 1268 00:53:14,040 --> 00:53:15,040 但是你真的很近。 1269 00:53:15,040 --> 00:53:15,915 他們是非常相似的。 1270 00:53:15,915 --> 00:53:17,440 就算我讓他們混在一起的時候。 1271 00:53:17,440 --> 00:53:18,981 這部分我像以前一樣,等待。 1272 00:53:18,981 --> 00:53:20,130 1273 00:53:20,130 --> 00:53:20,630 行。 1274 00:53:20,630 --> 00:53:24,141 所以,你要 做的是選擇排序, 1275 00:53:24,141 --> 00:53:25,890 你能想到的方式 它和方式 1276 00:53:25,890 --> 00:53:30,140 我要確保我盡量不要讓 它們混合起來,是它通過 1277 00:53:30,140 --> 00:53:33,280 的情況下選擇 最小數目和它 1278 00:53:33,280 --> 00:53:36,070 提出,在列表的開頭。 1279 00:53:36,070 --> 00:53:37,730 它交換它與第一點。 1280 00:53:37,730 --> 00:53:42,600 1281 00:53:42,600 --> 00:53:45,370 他們居然對我有一個例子。 1282 00:53:45,370 --> 00:53:46,540 真棒。 1283 00:53:46,540 --> 00:53:50,130 所以,只是一個方式去思考它 - 選擇 排序,選擇最小的值。 1284 00:53:50,130 --> 00:53:51,940 而我們要 通過一個實例運行 1285 00:53:51,940 --> 00:53:55,320 我認為這將有助於因 我覺得視覺效果總是幫助。 1286 00:53:55,320 --> 00:53:58,510 因此,我們的東西開始了 這是完全無序。 1287 00:53:58,510 --> 00:54:00,730 紅會未排序的, 綠色進行排序。 1288 00:54:00,730 --> 00:54:02,190 它將所有的意義在第二。 1289 00:54:02,190 --> 00:54:08,950 >> 所以,我們通過我們遍歷 從開始到結束。 1290 00:54:08,950 --> 00:54:12,320 我們說好,2 我們最小的號碼。 1291 00:54:12,320 --> 00:54:15,680 因此,我們要採取2,我們要 將它移動到我們的數組的前面 1292 00:54:15,680 --> 00:54:17,734 因為它是 最小數,我們有。 1293 00:54:17,734 --> 00:54:19,150 所以,這就是這是在這裡做。 1294 00:54:19,150 --> 00:54:20,820 它只是要交換這兩個。 1295 00:54:20,820 --> 00:54:21,850 1296 00:54:21,850 --> 00:54:25,450 所以,現在我們有一個排序 部分和未分類的一部分。 1297 00:54:25,450 --> 00:54:27,810 什麼是好記 關於選擇排序 1298 00:54:27,810 --> 00:54:30,690 是我們唯一的選擇 從無序的一部分。 1299 00:54:30,690 --> 00:54:32,220 1300 00:54:32,220 --> 00:54:34,527 >> 排序的一部分,你只是獨自離開。 1301 00:54:34,527 --> 00:54:35,660 嗯? 1302 00:54:35,660 --> 00:54:38,452 >> 學生:它是如何知道什麼是 最小無它比較 1303 00:54:38,452 --> 00:54:39,868 到陣列中的每一個其它值。 1304 00:54:39,868 --> 00:54:41,250 講師:它確實進行比較。 1305 00:54:41,250 --> 00:54:42,041 我們喜歡跳過它。 1306 00:54:42,041 --> 00:54:43,850 這只是一般的整體。 1307 00:54:43,850 --> 00:54:44,831 是啊。 1308 00:54:44,831 --> 00:54:47,205 當我們編寫我的代碼 相信你會更加滿意。 1309 00:54:47,205 --> 00:54:48,696 1310 00:54:48,696 --> 00:54:53,030 但是,你保存這第一 元件為最小。 1311 00:54:53,030 --> 00:54:56,110 你比較,你 說好,是不是更小? 1312 00:54:56,110 --> 00:54:56,660 是。 1313 00:54:56,660 --> 00:54:57,460 保留它。 1314 00:54:57,460 --> 00:54:58,640 這裡是小? 1315 00:54:58,640 --> 00:54:59,660 不是嗎? 1316 00:54:59,660 --> 00:55:02,510 >> 這是你最小, 它重新分配給你的價值。 1317 00:55:02,510 --> 00:55:06,340 你會感到非常的快樂 當我們通過代碼。 1318 00:55:06,340 --> 00:55:07,510 1319 00:55:07,510 --> 00:55:13,970 因此,我們過不去,我們交換了,所以再 我們看一下這個排序的部分。 1320 00:55:13,970 --> 00:55:15,810 所以,我們要選擇三個出來。 1321 00:55:15,810 --> 00:55:18,890 我們打算把它在 我們的排序的部分的端部。 1322 00:55:18,890 --> 00:55:20,267 1323 00:55:20,267 --> 00:55:23,100 而我們只是要繼續做 這,做那,而這樣做。 1324 00:55:23,100 --> 00:55:24,130 1325 00:55:24,130 --> 00:55:27,420 因此,這是我們的一種偽這裡。 1326 00:55:27,420 --> 00:55:29,470 1327 00:55:29,470 --> 00:55:31,380 我們將在這裡編寫它在一秒鐘。 1328 00:55:31,380 --> 00:55:34,140 1329 00:55:34,140 --> 00:55:37,270 但只是一些走 通過在一個高的水平。 1330 00:55:37,270 --> 00:55:40,275 你會從去 i等於0到n減去​​2。 1331 00:55:40,275 --> 00:55:41,570 1332 00:55:41,570 --> 00:55:43,530 這是另一種優化。 1333 00:55:43,530 --> 00:55:45,020 不要太擔心了。 1334 00:55:45,020 --> 00:55:46,620 所以,當你在說什麼。 1335 00:55:46,620 --> 00:55:49,660 1336 00:55:49,660 --> 00:55:54,406 正如雅各說,我們​​怎麼 跟踪我們什麼是最小的? 1337 00:55:54,406 --> 00:55:55,030 我們怎麼知道? 1338 00:55:55,030 --> 00:55:57,060 我們來比較 一切都在我們的名單。 1339 00:55:57,060 --> 00:55:59,600 >> 因此,最小等於我。 1340 00:55:59,600 --> 00:56:03,870 它只是說,在這種情況下, 我們的最低值的索引。 1341 00:56:03,870 --> 00:56:07,660 這樣的話它會遍歷 而它從j為我加1。 1342 00:56:07,660 --> 00:56:11,420 因此,我們已經知道, 這是我們的第一個元素。 1343 00:56:11,420 --> 00:56:13,240 我們不必把它比作自己。 1344 00:56:13,240 --> 00:56:16,970 所以,我們開始把它比作下一個 1這就是為什麼它是我加1到n 1345 00:56:16,970 --> 00:56:20,110 減1,這是 陣列那裡的端部。 1346 00:56:20,110 --> 00:56:25,090 我們說,如果數組 j是小於陣列分鐘, 1347 00:56:25,090 --> 00:56:29,200 那麼,我們在那裡重新分配 我們的最低指標是。 1348 00:56:29,200 --> 00:56:37,470 >> 而如果分不等於i,如 在這裡我們又回到了這裡。 1349 00:56:37,470 --> 00:56:38,950 1350 00:56:38,950 --> 00:56:41,790 所以像我們當初做這個。 1351 00:56:41,790 --> 00:56:49,310 在這種情況下,它會開始 零,這將最終被兩人。 1352 00:56:49,310 --> 00:56:53,010 所以分也不會等於我到底。 1353 00:56:53,010 --> 00:56:55,720 讓我們知道, 我們需要交換它們。 1354 00:56:55,720 --> 00:56:57,420 1355 00:56:57,420 --> 00:57:00,470 我覺得自己像一個具體的例子 將幫助遠不止此。 1356 00:57:00,470 --> 00:57:04,970 因此,我將這個代碼與你們 現在,我認為這將是更好的。 1357 00:57:04,970 --> 00:57:07,380 1358 00:57:07,380 --> 00:57:11,350 >> 排序往往工作方式在 它往往只是為了更​​好地看到它們。 1359 00:57:11,350 --> 00:57:12,780 1360 00:57:12,780 --> 00:57:17,280 所以我們想要做的是 我們首先需要的最小 1361 00:57:17,280 --> 00:57:19,890 元件在它的陣列中的位置。 1362 00:57:19,890 --> 00:57:21,280 正是雅各說的話。 1363 00:57:21,280 --> 00:57:23,090 你需要存儲,不知怎的。 1364 00:57:23,090 --> 00:57:25,900 因此,我們要在這裡開始 遍歷數組。 1365 00:57:25,900 --> 00:57:28,970 我們會說這是我們的 第一次只是開始。 1366 00:57:28,970 --> 00:57:38,308 因此,我們將不得不INT 最小等於陣列在島 1367 00:57:38,308 --> 00:57:40,500 1368 00:57:40,500 --> 00:57:45,050 >> 所以,有一點要注意,每 這個時間循環執行, 1369 00:57:45,050 --> 00:57:48,550 我們開始一起又進了一步。 1370 00:57:48,550 --> 00:57:54,780 1371 00:57:54,780 --> 00:57:57,440 當我們開始我們看這一個。 1372 00:57:57,440 --> 00:58:00,840 接下來的時間,我們遍歷, 我們已經開始在這一個 1373 00:58:00,840 --> 00:58:02,680 而分配給它我們的最小值。 1374 00:58:02,680 --> 00:58:10,450 所以這是非常相似的冒泡排序 我們知道,一個傳球後, 1375 00:58:10,450 --> 00:58:11,700 這最後一個元素進行排序。 1376 00:58:11,700 --> 00:58:12,810 1377 00:58:12,810 --> 00:58:15,120 與選擇排序, 它正好相反。 1378 00:58:15,120 --> 00:58:18,950 >> 在每一個傳球,我們知道, 第一個是排序。 1379 00:58:18,950 --> 00:58:21,360 第二次通過後,將 第二個將被排序。 1380 00:58:21,360 --> 00:58:26,470 正如你看到的幻燈片的例子, 我們來分類的部分只是不斷增長。 1381 00:58:26,470 --> 00:58:34,020 因此,通過設置我們最小的一個 到數組我,所有它做 1382 00:58:34,020 --> 00:58:37,340 收縮是什麼 我們正在尋找這樣 1383 00:58:37,340 --> 00:58:40,164 最小化的數量 比較我們做。 1384 00:58:40,164 --> 00:58:41,770 這是否有意義大家? 1385 00:58:41,770 --> 00:58:42,920 1386 00:58:42,920 --> 00:58:46,380 你需要我通過運行 再慢,或者在不同的話嗎? 1387 00:58:46,380 --> 00:58:47,180 我很高興。 1388 00:58:47,180 --> 00:58:48,095 1389 00:58:48,095 --> 00:58:48,595 行。 1390 00:58:48,595 --> 00:58:50,060 1391 00:58:50,060 --> 00:58:55,540 >> 因此,我們的存儲 在這點上的值, 1392 00:58:55,540 --> 00:58:57,840 但是我們也希望來存儲索引。 1393 00:58:57,840 --> 00:59:01,010 所以我們要保存 最小的位置 1394 00:59:01,010 --> 00:59:02,770 1,這是只是要我。 1395 00:59:02,770 --> 00:59:04,357 1396 00:59:04,357 --> 00:59:05,440 所以,現在雅各是滿意的。 1397 00:59:05,440 --> 00:59:06,870 我們所儲存的東西。 1398 00:59:06,870 --> 00:59:08,240 1399 00:59:08,240 --> 00:59:11,870 現在我們需要看看通過 陣列的未分類的一部分。 1400 00:59:11,870 --> 00:59:18,170 所以在這種情況下,這 將是我們未排序的。 1401 00:59:18,170 --> 00:59:20,980 1402 00:59:20,980 --> 00:59:22,462 這就是我。 1403 00:59:22,462 --> 00:59:25,430 1404 00:59:25,430 --> 00:59:26,210 行。 1405 00:59:26,210 --> 00:59:30,040 >> 所以,我們要做些什麼 將是一個循環。 1406 00:59:30,040 --> 00:59:32,066 每當你需要 遍歷數組, 1407 00:59:32,066 --> 00:59:33,440 你的頭腦會去為一個循環。 1408 00:59:33,440 --> 00:59:34,760 1409 00:59:34,760 --> 00:59:38,090 因此,對於一些INTķ equals--什麼,我們認為 1410 00:59:38,090 --> 00:59:39,700 k被要等於開始? 1411 00:59:39,700 --> 00:59:41,580 1412 00:59:41,580 --> 00:59:44,766 這是我們設置了最小 價值,我們要進行比較。 1413 00:59:44,766 --> 00:59:47,090 我們究竟要比較它? 1414 00:59:47,090 --> 00:59:48,730 這將是該下一個,對不對? 1415 00:59:48,730 --> 00:59:53,200 所以我們要k,進而進行初始化 要我加1開始。 1416 00:59:53,200 --> 00:59:55,350 1417 00:59:55,350 --> 01:00:02,800 >> 我們希望K的這種情況下,我們 已經存儲的大小在這裡, 1418 01:00:02,800 --> 01:00:03,930 所以我們可以只使用尺寸。 1419 01:00:03,930 --> 01:00:06,240 大小作為數組的大小。 1420 01:00:06,240 --> 01:00:09,620 我們只是想 一,每次更新ķ。 1421 01:00:09,620 --> 01:00:17,410 1422 01:00:17,410 --> 01:00:17,910 涼爽。 1423 01:00:17,910 --> 01:00:19,650 1424 01:00:19,650 --> 01:00:23,430 所以,現在我們需要找到 這裡的最小元素。 1425 01:00:23,430 --> 01:00:24,470 1426 01:00:24,470 --> 01:00:31,380 因此,如果我們遍歷,我們 想說,如果數組日K 1427 01:00:31,380 --> 01:00:37,080 小於我們最小value-- 這就是我們實際上 1428 01:00:37,080 --> 01:00:42,950 跟踪是什麼 最小這裡 - 1429 01:00:42,950 --> 01:00:47,740 那麼我們要重新分配 就是我們最小的值是。 1430 01:00:47,740 --> 01:00:50,645 >> 這意味著,哦,我們是 迭代經過這裡。 1431 01:00:50,645 --> 01:00:51,699 1432 01:00:51,699 --> 01:00:53,740 無論值是這裡 不是我們最小的事情。 1433 01:00:53,740 --> 01:00:54,448 我們不希望它。 1434 01:00:54,448 --> 01:00:56,100 我們要重新分配它。 1435 01:00:56,100 --> 01:01:02,050 所以,如果我們要重新分配它,做什麼 你覺得可能是這裡的代碼? 1436 01:01:02,050 --> 01:01:04,160 我們要重新分配 最小的位置。 1437 01:01:04,160 --> 01:01:05,740 1438 01:01:05,740 --> 01:01:07,010 還等什麼,現在是最小的? 1439 01:01:07,010 --> 01:01:08,422 1440 01:01:08,422 --> 01:01:09,130 學生:列K。 1441 01:01:09,130 --> 01:01:09,963 講師:列K。 1442 01:01:09,963 --> 01:01:13,480 1443 01:01:13,480 --> 01:01:15,956 是什麼位置呢? 1444 01:01:15,956 --> 01:01:20,940 1445 01:01:20,940 --> 01:01:23,000 什麼的指數 我們最小的價值? 1446 01:01:23,000 --> 01:01:24,030 1447 01:01:24,030 --> 01:01:24,530 它只是ķ。 1448 01:01:24,530 --> 01:01:25,690 1449 01:01:25,690 --> 01:01:27,790 所以列K中,k,它們相匹配。 1450 01:01:27,790 --> 01:01:31,670 1451 01:01:31,670 --> 01:01:33,120 因此,我們要重新分配。 1452 01:01:33,120 --> 01:01:34,390 1453 01:01:34,390 --> 01:01:39,950 再之後,我們發現我們最小的, 因此在今年年底for循環 1454 01:01:39,950 --> 01:01:45,100 在這裡我們找到了我們的最小 值,所以我們只是換了。 1455 01:01:45,100 --> 01:01:47,100 1456 01:01:47,100 --> 01:01:50,816 在這種情況下,像說我們的 最小值是出在這裡。 1457 01:01:50,816 --> 01:01:51,940 這是我們的最小值。 1458 01:01:51,940 --> 01:01:57,690 >> 我們只是想在這裡交換,這是 是什麼在底部的交換功能 1459 01:01:57,690 --> 01:02:01,270 的確,這是我們剛剛寫了 同時幾分鐘前。 1460 01:02:01,270 --> 01:02:02,775 所以它應該很熟悉。 1461 01:02:02,775 --> 01:02:04,320 1462 01:02:04,320 --> 01:02:08,030 然後它只會重複 通過直到它到達一路 1463 01:02:08,030 --> 01:02:13,100 到結束,這意味著你 具有零個元素是無序 1464 01:02:13,100 --> 01:02:14,800 和其他一切已排序。 1465 01:02:14,800 --> 01:02:16,216 1466 01:02:16,216 --> 01:02:16,715 有意義嗎? 1467 01:02:16,715 --> 01:02:18,010 1468 01:02:18,010 --> 01:02:19,280 有一點更具體? 1469 01:02:19,280 --> 01:02:19,990 該代碼的幫助? 1470 01:02:19,990 --> 01:02:21,720 1471 01:02:21,720 --> 01:02:26,410 >> 學生:對於一個規模,你永遠不 真正定義它或改變它, 1472 01:02:26,410 --> 01:02:27,340 它是怎麼知道的? 1473 01:02:27,340 --> 01:02:32,380 >> 教師:那麼一回事, 注意在這裡為int的大小。 1474 01:02:32,380 --> 01:02:35,680 所以我們說在這個類別 - 排序 是在這樣的函數case--它 1475 01:02:35,680 --> 01:02:40,770 選擇排序,它通過 同的功能。 1476 01:02:40,770 --> 01:02:43,460 所以,如果它沒有通過 中,你會做什麼 1477 01:02:43,460 --> 01:02:47,840 像與所述陣列的長度 或者你會遍歷 1478 01:02:47,840 --> 01:02:49,390 找到的長度。 1479 01:02:49,390 --> 01:02:52,680 但由於它的傳遞 中,我們可以只使用它。 1480 01:02:52,680 --> 01:02:55,720 你剛才假設​​用戶 給你一個有效的尺寸 1481 01:02:55,720 --> 01:02:57,698 實際上代表 一個大小的數組。 1482 01:02:57,698 --> 01:02:59,461 1483 01:02:59,461 --> 01:02:59,960 很酷吧? 1484 01:02:59,960 --> 01:03:01,610 1485 01:03:01,610 --> 01:03:05,870 >> 如果你們有這些任何麻煩 還是要多練編碼排序 1486 01:03:05,870 --> 01:03:08,050 在你自己的,你應該 去study.cs50。 1487 01:03:08,050 --> 01:03:11,560 1488 01:03:11,560 --> 01:03:12,670 這是一個工具。 1489 01:03:12,670 --> 01:03:15,040 他們有一個檢查器 你其實可以寫。 1490 01:03:15,040 --> 01:03:16,180 他們這樣做偽。 1491 01:03:16,180 --> 01:03:19,310 他們有更多的視頻和幻燈片 包括那些我在這裡使用。 1492 01:03:19,310 --> 01:03:23,150 所以,如果你仍然感覺 有點模糊,嘗試了這一點。 1493 01:03:23,150 --> 01:03:25,670 與往常一樣,來和我說話了。 1494 01:03:25,670 --> 01:03:26,320 問題? 1495 01:03:26,320 --> 01:03:28,611 >> 學生:你說的 大小是預先定義的? 1496 01:03:28,611 --> 01:03:29,234 1497 01:03:29,234 --> 01:03:29,900 指導老師:是的。 1498 01:03:29,900 --> 01:03:35,570 大小是預先定義了 這裡的函數聲明。 1499 01:03:35,570 --> 01:03:39,060 所以,你認為它已經通過了 由用戶,並且為簡單起見, 1500 01:03:39,060 --> 01:03:41,896 我們將假設 用戶給了我們正確的大小。 1501 01:03:41,896 --> 01:03:43,240 涼爽。 1502 01:03:43,240 --> 01:03:44,390 所以這是選擇排序。 1503 01:03:44,390 --> 01:03:45,590 1504 01:03:45,590 --> 01:03:47,640 伙計們,我知道我們今天學習了很多。 1505 01:03:47,640 --> 01:03:49,710 這是一個密集的數據部分。 1506 01:03:49,710 --> 01:03:51,880 1507 01:03:51,880 --> 01:03:57,340 於是就這樣,我們將 去插入排序。 1508 01:03:57,340 --> 01:04:01,550 1509 01:04:01,550 --> 01:04:02,510 >> 行。 1510 01:04:02,510 --> 01:04:06,100 所以,在這之前,我們需要做的 我們這裡的運行時分析。 1511 01:04:06,100 --> 01:04:10,190 所以,在最好的情況下, 理所當然,因為我給你 1512 01:04:10,190 --> 01:04:11,960 表我已經 種就將它丟棄。 1513 01:04:11,960 --> 01:04:15,430 但是,最好的情況下運行時,我們會怎麼想? 1514 01:04:15,430 --> 01:04:17,310 1515 01:04:17,310 --> 01:04:18,130 一切都來分類的。 1516 01:04:18,130 --> 01:04:21,040 1517 01:04:21,040 --> 01:04:22,070 Ñ​​平方。 1518 01:04:22,070 --> 01:04:24,780 任何人都有一個解釋 為什麼你覺得呢? 1519 01:04:24,780 --> 01:04:29,060 1520 01:04:29,060 --> 01:04:30,519 >> 學生:你比較through-- 1521 01:04:30,519 --> 01:04:31,268 指導老師:對。 1522 01:04:31,268 --> 01:04:32,540 你比較過。 1523 01:04:32,540 --> 01:04:35,630 在每一次迭代中,即使 我們正在遞減這一個, 1524 01:04:35,630 --> 01:04:38,950 你還在尋找通過 一切都找到了最小的一個。 1525 01:04:38,950 --> 01:04:42,390 所以,即使你的最小值 就是在這裡開始, 1526 01:04:42,390 --> 01:04:44,710 你還在比較其 反對一切 1527 01:04:44,710 --> 01:04:46,550 以確保它是最小的事情。 1528 01:04:46,550 --> 01:04:49,820 所以,你最終會通過運行 大約ñ平方倍。 1529 01:04:49,820 --> 01:04:51,090 1530 01:04:51,090 --> 01:04:51,590 行。 1531 01:04:51,590 --> 01:04:52,785 什麼是最糟糕的情況? 1532 01:04:52,785 --> 01:04:54,350 1533 01:04:54,350 --> 01:04:57,980 也可為N的平方,因為你會 在做了同樣的過程。 1534 01:04:57,980 --> 01:05:01,670 所以在這種情況下,選擇 排序有什麼 1535 01:05:01,670 --> 01:05:04,010 我們也呼籲預期運行。 1536 01:05:04,010 --> 01:05:07,400 因此,在別人,我們只知道 的上限和下限。 1537 01:05:07,400 --> 01:05:11,180 這取決於如何瘋狂我們 列表或者如何排序的是, 1538 01:05:11,180 --> 01:05:15,350 它們n或n的平方之間變化。 1539 01:05:15,350 --> 01:05:16,550 我們不知道。 1540 01:05:16,550 --> 01:05:22,820 >> 但由於選擇排序有相同的 最壞和最好的情況下,這告訴我們, 1541 01:05:22,820 --> 01:05:25,880 無論輸入什麼類型的,我們 有,無論是完全 1542 01:05:25,880 --> 01:05:29,130 排序或完全 反向排序,這是 1543 01:05:29,130 --> 01:05:30,740 要採取的相同的時間量。 1544 01:05:30,740 --> 01:05:33,760 因此,在這種情況下,如果 從表中我們還記得, 1545 01:05:33,760 --> 01:05:38,610 它實際上有一個值,該值 這兩類沒有, 1546 01:05:38,610 --> 01:05:40,390 這是預期運行。 1547 01:05:40,390 --> 01:05:43,350 所以我們知道,每當 我們運行選擇排序, 1548 01:05:43,350 --> 01:05:45,380 它保證 運行一個n的平方時間。 1549 01:05:45,380 --> 01:05:46,630 沒有可變性存在。 1550 01:05:46,630 --> 01:05:47,630 這只是預期。 1551 01:05:47,630 --> 01:05:48,820 1552 01:05:48,820 --> 01:05:52,140 並再次,如果你想學習 更多的,拿CS 124的春天。 1553 01:05:52,140 --> 01:05:55,370 1554 01:05:55,370 --> 01:05:56,712 行。 1555 01:05:56,712 --> 01:05:57,545 我們已經看到了這一點。 1556 01:05:57,545 --> 01:05:58,530 1557 01:05:58,530 --> 01:05:59,030 涼爽。 1558 01:05:59,030 --> 01:06:00,930 所以插入排序。 1559 01:06:00,930 --> 01:06:03,330 而且我可能會 走出一條通過此。 1560 01:06:03,330 --> 01:06:05,440 我不會有你們編寫它。 1561 01:06:05,440 --> 01:06:06,580 我們將步行穿過它。 1562 01:06:06,580 --> 01:06:10,500 所以插入排序是怎麼樣 類似於選擇排序 1563 01:06:10,500 --> 01:06:14,460 在我們有兩個未排序 和排序的陣列的一部分。 1564 01:06:14,460 --> 01:06:20,260 >> 但不同的是, 因為我們通過一個接一個, 1565 01:06:20,260 --> 01:06:24,210 我們只取什麼數 接下來是我們未排序的, 1566 01:06:24,210 --> 01:06:28,507 並正確排序 到我們的排序的數組。 1567 01:06:28,507 --> 01:06:30,090 它會更有意義,用一個例子。 1568 01:06:30,090 --> 01:06:31,140 1569 01:06:31,140 --> 01:06:35,430 所以一切開始作為未分類, 只是想用選擇排序。 1570 01:06:35,430 --> 01:06:38,740 而我們要在此排序 升序因為我們一直。 1571 01:06:38,740 --> 01:06:40,360 1572 01:06:40,360 --> 01:06:43,340 因此,我們第一遍 我們採取的第一個值 1573 01:06:43,340 --> 01:06:46,700 我們說好,你是 現在在列表中自己。 1574 01:06:46,700 --> 01:06:49,150 >> 因為你是在一個列表 由自己,你的排序。 1575 01:06:49,150 --> 01:06:52,460 恭喜您成為了 此數組第一個元素。 1576 01:06:52,460 --> 01:06:54,800 你已經排序的所有靠自己了。 1577 01:06:54,800 --> 01:06:58,900 所以,現在我們有一個排序 和一個未排序的數組。 1578 01:06:58,900 --> 01:07:01,760 所以,現在我們採​​取的第一個。 1579 01:07:01,760 --> 01:07:05,600 在此之間會發生什麼 這裡就是我們說的, 1580 01:07:05,600 --> 01:07:08,890 OK,我們要去看看 我們排序的數組的第一個值 1581 01:07:08,890 --> 01:07:13,270 而且我們要投入在其 正確的位置排序數組中。 1582 01:07:13,270 --> 01:07:21,460 >> 所以,我們要做的是,我們採取5 我們說好,5大於3, 1583 01:07:21,460 --> 01:07:24,630 所以我們只是將它的權利 到的,該權利。 1584 01:07:24,630 --> 01:07:25,130 我們是很好的。 1585 01:07:25,130 --> 01:07:26,200 1586 01:07:26,200 --> 01:07:28,420 那麼接下來,我們繼續我們的下一個。 1587 01:07:28,420 --> 01:07:29,720 我們採取2。 1588 01:07:29,720 --> 01:07:34,330 我們說好,2少 比3,所以我們知道它 1589 01:07:34,330 --> 01:07:36,220 需要是在 我們的名單前面了。 1590 01:07:36,220 --> 01:07:41,800 所以,我們做的是我們推3和5下 我們提出2成第一個插槽。 1591 01:07:41,800 --> 01:07:42,990 1592 01:07:42,990 --> 01:07:45,870 所以,我們只是將其插入 正確的位置是應該的。 1593 01:07:45,870 --> 01:07:46,960 1594 01:07:46,960 --> 01:07:49,470 >> 然後我們來看看我們的 下一個,我們說6。 1595 01:07:49,470 --> 01:07:53,620 行,6大於 一切都在我們的排序的數組, 1596 01:07:53,620 --> 01:07:56,000 所以我們只是將其標記到結束。 1597 01:07:56,000 --> 01:07:56,960 然後我們來看看4。 1598 01:07:56,960 --> 01:07:58,130 1599 01:07:58,130 --> 01:08:03,020 圖4是小於6,就少 比5,但它是大於3。 1600 01:08:03,020 --> 01:08:06,270 所以我們只是把它插入到正確的 3和5之間的中間。 1601 01:08:06,270 --> 01:08:07,380 1602 01:08:07,380 --> 01:08:10,530 因此,為了使這一點 多一點具體的, 1603 01:08:10,530 --> 01:08:12,280 這裡是怎麼樣的 想法發生了什麼事。 1604 01:08:12,280 --> 01:08:16,430 因此,對於每一個未排序的元素,我們 確定在排序部分 1605 01:08:16,430 --> 01:08:17,090 它是。 1606 01:08:17,090 --> 01:08:20,680 >> 所以,牢記 分類和未分類, 1607 01:08:20,680 --> 01:08:26,080 我們已經遍歷和數字 出它的排序的數組能容納。 1608 01:08:26,080 --> 01:08:31,460 我們通過移動插入 元素,它的降權。 1609 01:08:31,460 --> 01:08:34,910 然後,我們只是不停 通過迭代,直到我們 1610 01:08:34,910 --> 01:08:39,270 有一個完全排序的列表 其中,無序現在是零 1611 01:08:39,270 --> 01:08:41,720 和排序佔用 我們的全部名單。 1612 01:08:41,720 --> 01:08:43,146 1613 01:08:43,146 --> 01:08:45,854 所以,再一次,為了讓事情 更具體的,我們有偽代碼。 1614 01:08:45,854 --> 01:08:47,979 1615 01:08:47,979 --> 01:08:52,410 >> 所以基本上對我是 等於0到n減1, 1616 01:08:52,410 --> 01:08:54,790 這是我們陣中僅有的長度。 1617 01:08:54,790 --> 01:09:00,979 我們有一些元件,它等於 第一陣列或第一索引。 1618 01:09:00,979 --> 01:09:03,200 我們集合的J相等。 1619 01:09:03,200 --> 01:09:04,649 1620 01:09:04,649 --> 01:09:09,210 因此,雖然j大於 零和陣列,J減去1 1621 01:09:09,210 --> 01:09:11,660 大於 元素,讓所有的做 1622 01:09:11,660 --> 01:09:17,479 為確保 您Ĵ真正代表 1623 01:09:17,479 --> 01:09:20,010 陣列的未分類的部分。 1624 01:09:20,010 --> 01:09:30,745 >> 因此,儘管還有事 排序和j減一is--什麼 1625 01:09:30,745 --> 01:09:31,840 是她的元素? 1626 01:09:31,840 --> 01:09:34,760 J以從來沒有在這裡定義。 1627 01:09:34,760 --> 01:09:35,677 這是一種煩人。 1628 01:09:35,677 --> 01:09:36,176 行。 1629 01:09:36,176 --> 01:09:36,689 反正。 1630 01:09:36,689 --> 01:09:39,899 所以Ĵ減1,你檢查 之前的元素。 1631 01:09:39,899 --> 01:09:46,460 你說,OK,是元素 之前,無論我am--我們 1632 01:09:46,460 --> 01:09:47,540 實際繪製了這一點。 1633 01:09:47,540 --> 01:09:52,580 1634 01:09:52,580 --> 01:09:56,830 所以我們可以說,這是 就像我們的第二次。 1635 01:09:56,830 --> 01:09:59,525 所以我將是相等 為1,這是在這裡。 1636 01:09:59,525 --> 01:10:03,310 1637 01:10:03,310 --> 01:10:06,025 >> 所以我將是等於1。 1638 01:10:06,025 --> 01:10:09,510 1639 01:10:09,510 --> 01:10:13,702 這將是2,4,5,6,7。 1640 01:10:13,702 --> 01:10:16,060 1641 01:10:16,060 --> 01:10:16,750 行。 1642 01:10:16,750 --> 01:10:20,945 因此,我們在這種情況下,元素 將是等於4。 1643 01:10:20,945 --> 01:10:22,110 1644 01:10:22,110 --> 01:10:24,946 我們有一些Ĵ這 將等於1。 1645 01:10:24,946 --> 01:10:29,770 1646 01:10:29,770 --> 01:10:30,971 哦,j被遞減。 1647 01:10:30,971 --> 01:10:31,720 那它是什麼。 1648 01:10:31,720 --> 01:10:35,680 所以j等於我,所以這個是什麼 說的是,我們向前邁進, 1649 01:10:35,680 --> 01:10:37,530 我們只是要確保 我們不是在 1650 01:10:37,530 --> 01:10:43,520 索引這樣,當我們試圖 插入的東西到我們的排序列表。 1651 01:10:43,520 --> 01:10:49,850 >> 因此,當j等於1在這種情況下,與 陣列Ĵ減埃德蒙頓所以數組Ĵ減1 1652 01:10:49,850 --> 01:10:54,610 2本case--如果這就是 大於所述元件, 1653 01:10:54,610 --> 01:10:57,700 那麼這一切是做 被轉移下來。 1654 01:10:57,700 --> 01:11:04,790 所以在這種情況下,陣列Ĵ減一 將陣列為零,這是2。 1655 01:11:04,790 --> 01:11:08,430 圖2為不大於4, 所以這不會執行。 1656 01:11:08,430 --> 01:11:11,460 這樣的移位,並不會向下移動。 1657 01:11:11,460 --> 01:11:18,790 這裡做的事情在這裡只是 移動你的排序的數組下來。 1658 01:11:18,790 --> 01:11:22,340 1659 01:11:22,340 --> 01:11:26,400 在這種情況下,實際上,我們 可以do--讓我們做這3。 1660 01:11:26,400 --> 01:11:28,080 1661 01:11:28,080 --> 01:11:31,970 所以,如果我們穿行與 這個例子,我們現在在這裡。 1662 01:11:31,970 --> 01:11:32,740 這是排序。 1663 01:11:32,740 --> 01:11:34,492 1664 01:11:34,492 --> 01:11:35,200 這是未排序的。 1665 01:11:35,200 --> 01:11:39,090 1666 01:11:39,090 --> 01:11:39,860 很酷吧? 1667 01:11:39,860 --> 01:11:46,620 所以i等於2,所以 我們的元素等於3。 1668 01:11:46,620 --> 01:11:47,920 1669 01:11:47,920 --> 01:11:52,270 與我們的j等於2。 1670 01:11:52,270 --> 01:12:00,620 因此,我們期待通過我們 說好,是數組Ĵ減一 1671 01:12:00,620 --> 01:12:03,470 大於所述元件 那我們看什麼? 1672 01:12:03,470 --> 01:12:05,540 答案是肯定的,對不對? 1673 01:12:05,540 --> 01:12:11,275 圖4是大於3和j 是2,那麼該代碼執行。 1674 01:12:11,275 --> 01:12:12,510 1675 01:12:12,510 --> 01:12:18,550 >> 所以,現在我們做的一個數組 2,所以在這裡,我們交換它們。 1676 01:12:18,550 --> 01:12:25,620 所以,我們只是說,OK,陣列 2,現在將是3。 1677 01:12:25,620 --> 01:12:28,130 1678 01:12:28,130 --> 01:12:32,340 和j是要等於 Ĵ減1,為1。 1679 01:12:32,340 --> 01:12:34,590 1680 01:12:34,590 --> 01:12:37,200 這是可怕的,但 你們的想法。 1681 01:12:37,200 --> 01:12:38,360 J是現在等於1。 1682 01:12:38,360 --> 01:12:44,360 和陣列j的只是要 等於我們的元件,​​為4。 1683 01:12:44,360 --> 01:12:45,950 1684 01:12:45,950 --> 01:12:48,570 我刪除的東西我不應該 有或miswrote東西, 1685 01:12:48,570 --> 01:12:49,910 但是你們的想法。 1686 01:12:49,910 --> 01:12:50,640 >> 它移動以n。 1687 01:12:50,640 --> 01:12:51,920 1688 01:12:51,920 --> 01:12:57,960 然後,如果這是,它會循環 再次,它會說,OK,j是1了。 1689 01:12:57,960 --> 01:13:00,665 和陣列Ĵ減1現在是2。 1690 01:13:00,665 --> 01:13:01,750 1691 01:13:01,750 --> 01:13:03,760 2小於我們的元素? 1692 01:13:03,760 --> 01:13:04,540 不是嗎? 1693 01:13:04,540 --> 01:13:07,970 這意味著,我們已經 插入這個元素 1694 01:13:07,970 --> 01:13:10,110 在我們排序的數組中的正確位置。 1695 01:13:10,110 --> 01:13:14,400 然後,我們就可以利用這個和我們說, OK,我們的排序的數組是在這裡。 1696 01:13:14,400 --> 01:13:19,940 它會採取這個數字6,並 就像,OK,比這個數少6? 1697 01:13:19,940 --> 01:13:20,480 不是嗎? 1698 01:13:20,480 --> 01:13:21,080 涼爽。 1699 01:13:21,080 --> 01:13:22,680 我們很好。 1700 01:13:22,680 --> 01:13:23,530 >> 再次這樣做。 1701 01:13:23,530 --> 01:13:24,740 我們說7。 1702 01:13:24,740 --> 01:13:29,010 比所述端部7少 我們的排序的數組? 1703 01:13:29,010 --> 01:13:29,520 號 1704 01:13:29,520 --> 01:13:30,430 所以,我們很好。 1705 01:13:30,430 --> 01:13:32,760 所以這將被排序。 1706 01:13:32,760 --> 01:13:38,610 基本上,這一切確實 它是在說拿 1707 01:13:38,610 --> 01:13:42,060 的第一個元素 您排序的數組, 1708 01:13:42,060 --> 01:13:46,010 找出通向哪裡 在排序的數組。 1709 01:13:46,010 --> 01:13:48,780 而這只是照顧 掉期來做到這一點。 1710 01:13:48,780 --> 01:13:51,300 你基本上只是交換 直到它在正確的位置。 1711 01:13:51,300 --> 01:13:53,600 1712 01:13:53,600 --> 01:13:56,990 視覺形象是你 移動都記錄下來做的。 1713 01:13:56,990 --> 01:13:59,420 >> 所以,這就像半冒泡排序式的。 1714 01:13:59,420 --> 01:14:02,280 1715 01:14:02,280 --> 01:14:03,420 退房研究50。 1716 01:14:03,420 --> 01:14:06,000 我強烈建議嘗試 編寫這個你自己。 1717 01:14:06,000 --> 01:14:07,220 1718 01:14:07,220 --> 01:14:12,450 如果您有任何問題,或者您想 參見示例代碼插入排序, 1719 01:14:12,450 --> 01:14:13,750 請告訴我。 1720 01:14:13,750 --> 01:14:14,500 我總是四處。 1721 01:14:14,500 --> 01:14:16,600 1722 01:14:16,600 --> 01:14:20,200 因此,最壞的情況下運行 和最好的情況下運行。 1723 01:14:20,200 --> 01:14:30,700 當你的傢伙從表中看到,我已經 表現出你,這既是ñ平方和n。 1724 01:14:30,700 --> 01:14:35,590 >> 種這麼打算過什麼,我們聊 關於我們以前的種種,最糟糕的 1725 01:14:35,590 --> 01:14:38,760 情況下運行時,如果 它是完全不排序, 1726 01:14:38,760 --> 01:14:42,530 我們必須比較所有這些n次。 1727 01:14:42,530 --> 01:14:47,020 我們做了一大堆的比較 因為如果它以相反的順序, 1728 01:14:47,020 --> 01:14:50,360 我們會說,OK,這 是相同的,這是很好的, 1729 01:14:50,360 --> 01:14:54,650 而這一次將要被比較 相對於第一個要被移動回。 1730 01:14:54,650 --> 01:14:56,710 而且隨著我們走向 尾部,我們有 1731 01:14:56,710 --> 01:14:59,440 比較,比較和 與之比較的一切。 1732 01:14:59,440 --> 01:15:03,030 >> 因此它最終被 大約Ñ平方。 1733 01:15:03,030 --> 01:15:09,510 如果它是正確的,那麼你 說好,2,你是​​好。 1734 01:15:09,510 --> 01:15:11,330 3,你比2。 1735 01:15:11,330 --> 01:15:12,310 你很厲害。 1736 01:15:12,310 --> 01:15:14,150 4,你只是比較的尾巴。 1737 01:15:14,150 --> 01:15:14,990 你很厲害。 1738 01:15:14,990 --> 01:15:17,140 6,比較的尾巴,你的罰款。 1739 01:15:17,140 --> 01:15:20,870 因此,對於每一個點,如果它已經 排序,你正在做一次比較。 1740 01:15:20,870 --> 01:15:22,320 所以它只是ñ。 1741 01:15:22,320 --> 01:15:26,840 因為我們有最好的情況下運行 n及n的最壞情況的運行時的 1742 01:15:26,840 --> 01:15:28,680 方,我們也沒有預期的運行。 1743 01:15:28,680 --> 01:15:31,290 1744 01:15:31,290 --> 01:15:34,020 >> 這只是取決於 亂我們的名單中出現。 1745 01:15:34,020 --> 01:15:35,860 1746 01:15:35,860 --> 01:15:39,530 又一次,另一 圖形和另一個表。 1747 01:15:39,530 --> 01:15:41,170 所以各種各樣的差異。 1748 01:15:41,170 --> 01:15:44,180 我只是微風過,我 感覺我們已經談過了廣泛 1749 01:15:44,180 --> 01:15:46,570 有關他們都怎麼樣 的變化,並且連接到一起。 1750 01:15:46,570 --> 01:15:50,564 所以合併排序是最後一個 我要你承擔傢伙。 1751 01:15:50,564 --> 01:15:52,105 我們也有一個漂亮的多彩畫卷。 1752 01:15:52,105 --> 01:15:53,860 1753 01:15:53,860 --> 01:15:56,040 所以,歸併排序是遞歸算法。 1754 01:15:56,040 --> 01:15:59,910 所以,不要你們知道是什麼 遞歸函數是? 1755 01:15:59,910 --> 01:16:01,550 1756 01:16:01,550 --> 01:16:03,320 >> 任何想說的? 1757 01:16:03,320 --> 01:16:04,739 你想試試嗎? 1758 01:16:04,739 --> 01:16:07,280 因此,一個遞歸函數就是 一個函數調用自身。 1759 01:16:07,280 --> 01:16:08,570 1760 01:16:08,570 --> 01:16:11,590 所以,如果你們熟悉 與斐波那契序列, 1761 01:16:11,590 --> 01:16:15,670 該公司認為,因為遞歸 你把前面的兩個 1762 01:16:15,670 --> 01:16:17,530 並把它們相加 讓你的下一個。 1763 01:16:17,530 --> 01:16:21,440 這樣循環,我一直認為 遞歸如像​​一個螺旋形的 1764 01:16:21,440 --> 01:16:24,430 所以你像螺旋式下降了進去。 1765 01:16:24,430 --> 01:16:27,150 但它只是一個功能 調用自身。 1766 01:16:27,150 --> 01:16:32,660 >> 而且,實際上,真的很快我 可以告訴你那是什麼樣子。 1767 01:16:32,660 --> 01:16:34,260 1768 01:16:34,260 --> 01:16:41,840 所以遞歸這裡,如果我們看,這是 遞歸的方式來總結一個數組。 1769 01:16:41,840 --> 01:16:45,900 1770 01:16:45,900 --> 01:16:47,880 因此,所有我們要做的就是 我們有求和函數 1771 01:16:47,880 --> 01:16:52,210 總之,需要一個大小和數組。 1772 01:16:52,210 --> 01:16:55,210 如果你注意到,大小 減一各一次。 1773 01:16:55,210 --> 01:17:00,365 和所有它的作用是,如果x等於 zero--因此,如果該數組的大小 1774 01:17:00,365 --> 01:17:02,710 等於zero--返回零。 1775 01:17:02,710 --> 01:17:10,440 >> 否則,這個總結 所述陣列的最後一個元素, 1776 01:17:10,440 --> 01:17:14,790 然後採取的總和 該陣列的其餘部分。 1777 01:17:14,790 --> 01:17:17,555 所以它只是將它分解 成越來越小的問題。 1778 01:17:17,555 --> 01:17:18,990 1779 01:17:18,990 --> 01:17:21,890 長話短說,遞歸, 函數調用自身。 1780 01:17:21,890 --> 01:17:25,740 如果這是你離開了這一點, 這就是一個遞歸函數。 1781 01:17:25,740 --> 01:17:29,870 如果你51,你會得到非常, 很舒服的遞歸。 1782 01:17:29,870 --> 01:17:31,110 1783 01:17:31,110 --> 01:17:32,370 這真的很酷。 1784 01:17:32,370 --> 01:17:34,660 它以有意義像 上午03點一晚了。 1785 01:17:34,660 --> 01:17:37,900 我當時想,為什麼 我也從來沒有用這個? 1786 01:17:37,900 --> 01:17:39,170 1787 01:17:39,170 --> 01:17:42,430 >> 因此,對於歸併排序,基本上 什麼是要做的是它的 1788 01:17:42,430 --> 01:17:45,620 要打破它,打破它 直到它只是單一的元素。 1789 01:17:45,620 --> 01:17:47,570 單個元件​​很容易就可以進行排序。 1790 01:17:47,570 --> 01:17:48,070 我們看到這一點。 1791 01:17:48,070 --> 01:17:50,760 如果你有一個元素,它的 已經考慮排序。 1792 01:17:50,760 --> 01:17:53,800 等n個元素的一個輸入端, 如果n小於2, 1793 01:17:53,800 --> 01:17:58,120 剛回來,因為那意味著 它是0或1,因為我們已經看到了。 1794 01:17:58,120 --> 01:18:00,050 那些被認為是排序的元素。 1795 01:18:00,050 --> 01:18:02,170 >> 否則,打破它的一半。 1796 01:18:02,170 --> 01:18:06,336 排序上半年,排序第二 一半,然後將它們合併在一起。 1797 01:18:06,336 --> 01:18:07,460 為什麼它被稱為歸併排序。 1798 01:18:07,460 --> 01:18:08,700 1799 01:18:08,700 --> 01:18:12,155 所以,我們在這裡,我們將整理這些。 1800 01:18:12,155 --> 01:18:13,410 1801 01:18:13,410 --> 01:18:17,210 因此,我們繼續讓他們 直到數組大小為1。 1802 01:18:17,210 --> 01:18:20,790 所以,當它的1,我們只返回 因為這是一個排序後的數組, 1803 01:18:20,790 --> 01:18:23,940 這是一個排序的數組,而這 一個排序的數組,我們都來分類的。 1804 01:18:23,940 --> 01:18:25,390 1805 01:18:25,390 --> 01:18:29,420 那麼接下來我們要做的是我們 啟動它們合併在一起。 1806 01:18:29,420 --> 01:18:31,820 >> 所以,這樣就可以 想想合併是 1807 01:18:31,820 --> 01:18:36,240 你只是刪除小 各子陣列中的數 1808 01:18:36,240 --> 01:18:38,330 而只是將其追加到數組中出現。 1809 01:18:38,330 --> 01:18:44,290 所以,如果你看看這裡,當我們有 這些集我們有​​4,6和1。 1810 01:18:44,290 --> 01:18:47,280 當我們要合併這些, 我們看一下前兩個 1811 01:18:47,280 --> 01:18:50,730 我們說好,1越小, 它會向前方。 1812 01:18:50,730 --> 01:18:54,330 4和6,有沒有什麼比較 它,只是將其標記上到結束。 1813 01:18:54,330 --> 01:18:58,020 >> 當我們結合這兩個,我們只是 取這兩個中較小的一個, 1814 01:18:58,020 --> 01:18:59,310 所以它的1。 1815 01:18:59,310 --> 01:19:01,690 現在我們採​​取的 這兩個,所以2的小。 1816 01:19:01,690 --> 01:19:03,330 這兩個,3個較小的。 1817 01:19:03,330 --> 01:19:06,260 這兩個,4,5,6以下。 1818 01:19:06,260 --> 01:19:08,630 所以,你剛才拉過這些。 1819 01:19:08,630 --> 01:19:11,210 而且由於他們把 以前被排序, 1820 01:19:11,210 --> 01:19:14,300 你只有一個 比較有各一次。 1821 01:19:14,300 --> 01:19:19,610 因此,更多的代碼在這裡,只是表示。 1822 01:19:19,610 --> 01:19:24,410 所以你在開始,中間和 您排序左右 1823 01:19:24,410 --> 01:19:26,180 然後你只要這些合併。 1824 01:19:26,180 --> 01:19:30,080 >> 我們沒有代碼 對於合併就在這裡。 1825 01:19:30,080 --> 01:19:34,110 但是,再說一次,如果你去上 研究50,它會在那裡。 1826 01:19:34,110 --> 01:19:36,860 否則,來跟我說話 如果你還在迷茫。 1827 01:19:36,860 --> 01:19:42,340 因此,這裡很酷的事情是最好的情況下, 最壞的情況下,與預期的運行時 1828 01:19:42,340 --> 01:19:46,250 都在日誌中N,其中 遠不如我們已經 1829 01:19:46,250 --> 01:19:48,000 看到了我們各種各樣的休息。 1830 01:19:48,000 --> 01:19:51,840 我們已經看到ñ平方 而其實我們 1831 01:19:51,840 --> 01:19:54,380 拿到這裡的n log N,這是偉大的。 1832 01:19:54,380 --> 01:19:55,830 >> 看看這是多麼要好的多。 1833 01:19:55,830 --> 01:19:56,780 這樣一個漂亮的曲線。 1834 01:19:56,780 --> 01:19:58,130 1835 01:19:58,130 --> 01:20:00,120 因此,更有效。 1836 01:20:00,120 --> 01:20:03,510 如果你可以,使用歸併排序。 1837 01:20:03,510 --> 01:20:04,810 這將節省您的時間。 1838 01:20:04,810 --> 01:20:07,670 話又說回來,正如我們所說的,如果 你倒在這個較低的地區, 1839 01:20:07,670 --> 01:20:09,480 它不會作出這樣的 多大的差別。 1840 01:20:09,480 --> 01:20:11,360 你得到多達數千 和數以千計的投入, 1841 01:20:11,360 --> 01:20:13,318 你一定要一個 更有效的算法。 1842 01:20:13,318 --> 01:20:14,730 1843 01:20:14,730 --> 01:20:19,400 並再次,我們可愛的表 各種各樣,你們今天學到。 1844 01:20:19,400 --> 01:20:21,157 >> 所以,我知道這是一個密集的一天。 1845 01:20:21,157 --> 01:20:23,490 這不一定要去 幫助您與您的PSET。 1846 01:20:23,490 --> 01:20:28,250 但我只想做一個免責聲明 該節不只是pset中。 1847 01:20:28,250 --> 01:20:31,240 所有這些材料是公平的 遊戲中為你的期中考試。 1848 01:20:31,240 --> 01:20:35,430 而且如果你繼續用CS, 這些都是非常重要的基礎 1849 01:20:35,430 --> 01:20:37,870 你需要知道的。 1850 01:20:37,870 --> 01:20:41,700 所以,有些日子將是一個 多一點PSET的幫助, 1851 01:20:41,700 --> 01:20:44,600 但幾個星期會 更多的實際內容 1852 01:20:44,600 --> 01:20:46,600 這似乎並不超 現在對你有用, 1853 01:20:46,600 --> 01:20:51,215 但如果你繼續我答應 上會非常,非常有用。 1854 01:20:51,215 --> 01:20:52,560 1855 01:20:52,560 --> 01:20:54,250 >> 所以這是它的一節。 1856 01:20:54,250 --> 01:20:55,250 下來的電線。 1857 01:20:55,250 --> 01:20:56,570 我做了一分鐘之內。 1858 01:20:56,570 --> 01:20:58,262 1859 01:20:58,262 --> 01:20:58,970 但你去那裡。 1860 01:20:58,970 --> 01:21:01,240 我也有甜甜圈或糖果。 1861 01:21:01,240 --> 01:21:03,464 有沒有人過敏 任何事情,順便? 1862 01:21:03,464 --> 01:21:05,307 1863 01:21:05,307 --> 01:21:05,890 雞蛋和牛奶。 1864 01:21:05,890 --> 01:21:08,120 因此,甜甜圈是一個沒有? 1865 01:21:08,120 --> 01:21:09,400 1866 01:21:09,400 --> 01:21:10,160 行。 1867 01:21:10,160 --> 01:21:10,770 行。 1868 01:21:10,770 --> 01:21:12,120 巧克力不? 1869 01:21:12,120 --> 01:21:12,620 星爆。 1870 01:21:12,620 --> 01:21:13,837 1871 01:21:13,837 --> 01:21:14,670 星形圖案都不錯。 1872 01:21:14,670 --> 01:21:15,170 行。 1873 01:21:15,170 --> 01:21:17,045 我們將有 下週爆吧。 1874 01:21:17,045 --> 01:21:18,240 這就是我去拿。 1875 01:21:18,240 --> 01:21:19,690 你們有一個偉大的一周。 1876 01:21:19,690 --> 01:21:20,460 看了你的天賦。 1877 01:21:20,460 --> 01:21:22,130 >> 讓我知道,如果你有任何問題。 1878 01:21:22,130 --> 01:21:25,300 PSET兩個檔次應該是 出來你在週四。 1879 01:21:25,300 --> 01:21:28,320 如果您有任何問題 我是如何分級的事情 1880 01:21:28,320 --> 01:21:32,250 為什麼我的東西漸變的方式,我 沒有,請給我發電子郵件,來和我說話。 1881 01:21:32,250 --> 01:21:34,210 我有點瘋了這 一周,但我保證 1882 01:21:34,210 --> 01:21:36,340 我仍然會在24小時內回复。 1883 01:21:36,340 --> 01:21:38,240 所以,有一個偉大的一周,每一個人。 1884 01:21:38,240 --> 01:21:40,090 祝你PSET。 1885 01:21:40,090 --> 01:21:41,248