[Bermain muzik] 

DOUG LLOYD: Jadi jenis kemasukan adalah satu lagi algoritma boleh kita gunakan untuk menyelesaikan array. Idea di sebalik algoritma ini adalah untuk membina pelbagai disusun anda di tempat, beralih unsur-unsur daripada jalan sebagai anda pergi, untuk memberi ruang. Ini adalah sedikit berbeza dari jenis pemilihan atau gelembung jenis, sebagai contoh, di mana kita menyesuaikan lokasi, di mana kita membuat swap. 

Dalam kes ini apa yang kita sebenarnya lakukan adalah unsur-unsur gelongsor ke atas, keluar dari jalan. Bagaimana algoritma ini bekerja dalam kod pseudo? Nah mari kita sewenang-wenangnya mengatakan bahawa Elemen pertama array disusun. Kami membina di tempat. 

Kita akan pergi satu elemen pada satu masa dan membinanya, dan perkara pertama yang kita lihat adalah pelbagai satu unsur. Dan mengikut definisi, satu elemen array disusun. 

Kemudian kami akan mengulangi proses ini until-- kami akan mengulangi proses berikut sehingga semua unsur-unsur yang disusun. Lihatlah unsur terisih depan dan masukkannya ke dalam bahagian yang disusun, dengan memindahkan jumlah yang diperlukan unsur-unsur keluar dari jalan. Mudah-mudahan visualisasi ini akan membantu anda melihat dengan jelas apa yang berlaku dengan jenis kemasukan. 

Jadi sekali lagi, di sini kami pelbagai keseluruhan terisih, semua unsur-unsur yang ditunjukkan dalam merah. Dan mari kita ikut langkah-langkah pseudokod kami. Perkara pertama yang kita lakukan, adalah kita panggil Elemen pertama array, disusun. Jadi kami hanya akan berkata lima, anda sedang disusun. 

Kemudian kami melihat seterusnya unsur terisih array dan kami mahu memasukkan bahawa ke dalam bahagian yang disusun, dengan mengalihkan unsur berakhir. Jadi kedua-duanya adalah terisih seterusnya elemen array. Jelas sekali ia tergolong sebelum lima, jadi apa yang kita nak buat umpama memegang dua diketepikan untuk kali kedua, beralih lima lebih, dan kemudian masukkan dua sebelum lima, di mana untuk harus pergi. Dan sekarang kita boleh mengatakan bahawa dua disusun. 

Jadi seperti yang anda boleh lihat, kami telah hanya setakat melihat dua elemen array. Kami tidak melihat kepada berehat di semua, tetapi kami telah mendapat kedua-dua unsur-unsur disusun mengikut cara mekanisme peralihan. 

Oleh itu, kita mengulangi proses lagi. Lihatlah terisih seterusnya elemen, itu satu. Mari kita berpegang bahawa selain untuk kali kedua, beralih segala-galanya ke atas, dan meletakkan satu di mana ia harus pergi. 

Sekali lagi, masih, kami telah hanya pernah melihat satu, dua, dan lima. Kita tidak tahu apa lagi yang akan datang, tetapi kami telah disusun ketiga-tiga unsur-unsur. 

Seterusnya elemen terisih adalah tiga, jadi kita akan mengetepikannya. Kami akan beralih terhadap apa yang kita perlu yang, kali ini bukan segala-galanya seperti dalam sebelumnya dua kes, ia hanya lima. Dan kemudian kita akan berpegang tiga, antara kedua-dua dan lima. 

Enam adalah terisih seterusnya elemen untuk array. Dan sebenarnya enam adalah lebih besar daripada lima, jadi kita tidak perlu melakukan apa-apa bertukar-tukar. Kita hanya boleh jelujur enam kanan ke akhir bahagian yang disusun. 

Akhir sekali, empat adalah unsur terisih lepas. Jadi kita akan mengetepikannya, beralih ke atas unsur-unsur yang perlu kita beralih ke atas, dan kemudian meletakkan empat mana ia tergolong. Dan kini melihat, kami telah menyusun semua unsur-unsur. Perhatikan dengan kemasukan jenis, kita tidak mempunyai untuk kembali dan sebagainya di seluruh array. Kami hanya pergi di seluruh array satu masa, dan kita beralih perkara bahawa kita sudah sedang dihadapi, agar untuk memberi ruang kepada unsur-unsur baru. 

Jadi apa kes yang paling teruk senario dengan jenis kemasukan? Dalam kes paling teruk, Pelbagai adalah secara terbalik. Anda perlu beralih setiap n unsur sehingga n jawatan, setiap kita kali tunggal membuat sisipan yang. Itulah banyak beralih. 

Dalam kes yang terbaik, lokasi sempurna disusun. Dan jenis seperti apa yang berlaku dengan lima dan enam dalam contoh, di mana kita boleh jelujur pada tanpa perlu melakukan apa-apa penukaran gear, kita pada dasarnya akan berbuat demikian. 

Jika anda bayangkan bahawa kami lokasi adalah satu melalui enam, kita akan memulakan dengan mengisytiharkan satu disusun. Dua datang selepas satu supaya kita boleh hanya berkata, OK, baik satu dan dua yang disusun. Tiga datang selepas dua jadi, OK, satu dan dua dan tiga disusun. 

Kami tidak membuat apa-apa pertukaran, kami hanya bergerak garis sewenang-wenangnya ini antara disusun dan terisih seperti yang kita pergi. Dengan berkesan seperti yang kita lakukan dalam contoh, beralih elemen biru, seperti yang kita meneruskan. Jadi apa kes runtime paling teruk, maka? Ingat, jika kita perlu beralih setiap n elemen mungkin n jawatan, mudah-mudahan yang memberikan anda idea bahawa kes yang paling teruk runtime adalah O Big n kuasa dua. 

Jika array adalah sempurna disusun, semua yang perlu kita lakukan adalah melihat setiap elemen tunggal sekali, dan kemudian kami sudah selesai. Jadi dalam kes ini, ia omega n. 

Saya Doug Lloyd. Ini adalah CS50.