DOUG LLOYD: Jadi dalam CS50 kita belajar tentang pelbagai menyusun dan mencari algoritma. Dan kadang-kadang ia boleh menjadi sedikit rumit untuk menjaga mengesan apa algoritma tidak apa. Kami telah benar-benar hanya skim permukaan juga, terdapat banyak pencarian lain dan menyusun algoritma. Jadi, dalam video ini mari kita hanya mengambil masa beberapa minit untuk mencuba dan menyuling setiap algoritma turun kepada unsur-unsur teras supaya anda boleh ingat yang paling maklumat penting tentang mereka dan dapat menyatakan dengan jelas perbezaan, jika perlu. 

Yang pertama adalah jenis pemilihan. Idea asas di sebalik jenis pemilihan ialah mencari unsur terisih yang paling kecil dalam array dan tukar dengan unsur terisih pertama array itu. Kami berkata, kes terburuk yang masa berjalan itu telah n kuasa dua. Dan jika anda mahu untuk menarik balik mengapa, mengambil yang melihat video jenis pemilihan. Terbaik-kes masa jangka juga n kuasa dua. 

Semacam gelembung, idea di sebalik yang satu adalah untuk menukar pasangan bersebelahan. Jadi itulah kunci yang membantu anda ingat perbezaan di sini. Pemilihan jenis iaitu, setakat ini, mencari gelembung smallest-- MENGASINGKAN menukar pasangan bersebelahan. Kami menukar pasangan bersebelahan elemen jika mereka adalah daripada perintah, yang berkesan gelembung unsur-unsur yang lebih besar ke kanan, dan pada masa yang sama ia juga bermula untuk bergerak unsur-unsur yang lebih kecil ke kiri. The terburuk masa kes jangka semacam gelembung adalah n kuasa dua. Terbaik-kes masa jangka gelembung jenis adalah n. Kerana dalam keadaan yang kita tidak actually-- kita mungkin tidak perlu membuat apa-apa pertukaran pada semua. Kita hanya perlu membuat satu lulus dalam semua unsur-unsur n. 

Dalam jenis kemasukan, yang Idea asas di sini beralih. Itulah kata kunci untuk jenis kemasukan. Kita akan melangkah sekali melalui array dari kiri ke kanan. Dan seperti yang kita lakukan, kita berada akan beralih unsur-unsur kita telah pun melihat untuk memberi ruang kepada yang lebih kecil yang perlu dimuatkan di suatu tempat kembali bahawa sebahagian disusun. Oleh itu, kita membina array disusun satu elemen pada satu masa, kiri ke kanan, dan kita beralih perkara untuk membuat bilik. Kali jangka kes terburuk daripada jenis kemasukan adalah n kuasa dua. Terbaik-kes yang dikendalikan masa adalah n. 

Bergabung sort-- kata kunci di sini adalah berpecah dan bergabung. Kami berpecah array penuh, sama ada itu enam elemen, lapan elemen, 10000 elements-- kita berpecah turun sebanyak separuh, separuh, separuh, sehingga kita di bawah pelbagai n satu tatasusunan unsur. Satu set n satu tatasusunan unsur. Oleh itu, kita bermula dengan satu Pelbagai 1000-elemen, dan kita sampai ke tahap di mana kita mempunyai 1,000 tatasusunan satu elemen. Kemudian kita mula untuk menggabungkan mereka sub tatasusunan kembali bersama-sama dalam susunan yang betul. Oleh itu, kita mengambil dua tatasusunan satu elemen dan mewujudkan pelbagai dua unsur. Kami mengambil dua tatasusunan dua unsur dan mewujudkan pelbagai empat elemen dan sebagainya dan sebagainya sehingga kami telah lagi dibina semula satu n unsur tatasusunan. 

Kali jangka kes terburuk daripada bergabung MENGASINGKAN n kali log n. Kami mempunyai n unsur, tetapi proses recombining ini mengambil log n langkah-langkah untuk mendapatkan menyandarkan kepada pelbagai penuh. Kes terbaik masa berjalan juga n log n kerana proses ini tidak benar-benar peduli sama ada array adalah disusun atau tidak untuk memulakan dengan. Proses ini adalah yang sama, ada ada cara untuk perkara litar pintas. Jadi n n dalam kes paling teruk log, n log n dalam hal yang terbaik. 

Kita bercakap kira-kira dua mencari algoritma. Jadi carian linear adalah kira-kira iterating. Kita teruskan seluruh array sekali, dari kiri ke kanan, cuba untuk mencari nombor yang kita cari. Masa yang paling buruk jalankan adalah O besar n. Ia mungkin membawa kita iterating di setiap elemen tunggal untuk mencari elemen yang kita sedang untuk, sama ada dalam kedudukan yang terakhir, atau tidak sama sekali. Tetapi kita tidak boleh mengesahkan bahawa sehingga kita telah melihat segala-galanya. m terbaik kes, kita dapati dengan segera. Kali jangka kes terbaik daripada carian linear adalah omega 1. 

Akhir sekali, terdapat carian binari, yang memerlukan lokasi yang pelbagai. Ingat itulah yang sangat pertimbangan yang penting apabila bekerja dengan carian binari. Ia adalah pra-syarat untuk menggunakan kitab itu array bahawa anda melihat melalui mesti disusun. Jika tidak, kata kunci adalah pecah dan perintah. Split array ke dalam separuh dan menghapuskan separuh daripada unsur-unsur setiap kali apabila anda meneruskan melalui. Oleh kerana jurang ini dan menakluk dan perkara-perkara membelah dalam pendekatan separuh, masa jangka kes terburuk carian binari adalah log n, yang sebahagian besarnya lebih baik daripada carian linear ini n. Terbaik-kes menjalankan masa masih salah. 

Kita mungkin merasa segera kali pertama kami membuat pembahagian, tetapi, lagi, ingat bahawa walaupun carian binari adalah jauh lebih baik daripada carian linear selaku log n berbanding n, anda mungkin perlu melalui kerja menyusun pelbagai anda pertama, yang mungkin membuat ia kurang berkesan bergantung kepada saiz iterating yang disusun. 

Saya Doug Lloyd, ini adalah CS50.