Doug LLOYD: Yani CS50 biz öğrendik sıralama ve arama çeşitli algoritmaları. Ve bazen bu olabilir tutmak biraz zor Ne algoritması parça ne yapar. Biz gerçekten sadece ettik çok yüzeyi yağsız Birçok başka arama vardır ve sıralama algoritmaları. Yani bu video diyelim Sadece birkaç dakika sürebilir denemek ve her algoritma damıtmak için onun temel unsurları aşağı böylece en hatırlıyorum Onlar hakkında önemli bilgiler ve ifade etmeye muktedir farklılıklar, gerekirse. 

İlk seçim türüdür. Seçim tür arkasındaki temel fikir En küçük ayrımı yapılmamış diğer eleman bulmak olduğunu ve bir dizideki ile takas Bu dizinin ilk sıralanmamış öğesi. Biz en kötü durum olduğunu söyledi Bunun çalışma süresi n karesi oldu. Ve neden hatırlamak istiyorsanız, almak Seçim sıralama video bakmak. En iyi durum çalışma süresi Ayrıca n karesi edilir. 

Kabarcık sıralama, o arkasındaki fikir tek bitişik çift takas etmektir. Yani size yardımcı olur anahtar Burada fark hatırlıyorum. Seçim sıralama isimli, şimdiye kadar, smallest-- balonu bulmak sıralama isimli bitişik çift takas. Biz bitişik çift takas elemanların onlar halinde hangi etkili, sırasız sağdaki büyük elemanları kabarcıklar ve aynı zamanda, aynı zamanda başlar sola küçük öğeleri taşımak için. En kötü durum durum çalışma süresi kabarcık tür n karesi edilir. En iyi durum çalışma süresi kabarcık tür n. Çünkü bu durumda Biz actually-- yok Biz gerek olmayabilir hiç bir swapları yapmak. Biz sadece bir tane yapmak zorunda tüm n elemanları arasında geçmektedir. 

Ekleme sıralamada, Burada temel fikir kayıyor. Bu ekleme sıralama için anahtar kelime var. Biz aracılığıyla bir kez adım gidiyoruz dan dizi soldan sağa. Bizim gibi, biz konum elemanları degisecek biz zaten yer açmak için gördüm yere sığdırmak için gereken küçük olanlar geri o sıralanmış kısmında. Bu yüzden sıralı dizi inşa biri soldan sağa bir anda eleman, ve biz oda yapmak şeyler kaydırır. En kötü durum çalışma süresi Ekleme sıralama n karesi edilir. En iyi durum çalışma zamanı n. 

Anahtar kelime sort-- Birleştirme Burada bölme ve birleştirme olduğunu. Biz ister, tam bir dizi bölünmüş Altı elemanları, sekiz elemanları var, 10,000 öğelerin-- biz bölmek Aşağı yarı yarıya yarıya, yarı yarıya, Biz dizide altında elde edene kadar n bir unsuru diziler. N bir unsuru dizilerin kümesi. Bu yüzden biriyle başladık 1000-eleman dizisi, ve biz noktaya nereden biz 1000 tek eleman diziler var. Sonra o alt dizilerini birleştirmek başlar tekrar bir araya doğru sırayla. Bu yüzden iki tek eleman dizileri almak ve bir iki eleman dizi oluşturmak. Biz iki, iki eleman dizileri almak ve dört element dizi oluşturmak ve böylece ve böylece biz ettik kadar yine bir n elemanı dizisi yeniden inşa edildi. 

En kötü durum çalışma süresi sıralama isimli birleştirme n kat n oturum açın. Biz n unsurlar var, ama Bu yeniden birleştirici süreci log alır n adımlar almak Tam diziye geri. Çalışma süresi en iyi durumda da n log n bu süreç gerçekten yok çünkü Dizi olup olmadığını bakım sıralanmış ya da başlamak. Süreç var, aynı kısa devre şeyler hiçbir şekilde. Yani n kötü durumda log n, n iyi durumda log n. 

Biz iki konuştuk algoritmaları arıyor. Yani doğrusal arama iterating ilgili. Biz dizi boyunca devam Bir kez, soldan sağa doğru, numarasını bulmak için çalışıyor biz arıyoruz. En kötü durum çalışma zamanı n büyük O'dur. Bu yineleme Bizi alabilir her elemanın karşısında Biz arıyoruz eleman bulmak için için, ya da en son yer, ya da hiç. Ama biz gelene kadar teyit edemez biz her şeyi baktım. En iyi davayı m, biz hemen bulabilirsiniz. En iyi durum çalışma süresi doğrusal arama 1 omega olduğunu. 

Son olarak, ikili arama, orada hangi çeşitli dizi gerektirir. Bu çok var: Ol önemli bir husus İkili arama ile çalışırken. Bu Durdur-- kullanarak bir ön koşul var Üzerinden aradığınız dizi sıralanması gerekir. Aksi takdirde, anahtar kelime böl ve fethet olduğunu. Yarıya dizi Split ve elemanların yarı ortadan Her zaman doğru ilerlerken. Çünkü bu böl ve yönet arasında ve yarım yaklaşımda yarma şeyler, en kötü durum çalışma süresi ikili arama olduğunu esas olan, log n Lineer arama en n daha iyi. En iyi durum çalışma süresi hala biridir. 

Biz hemen bulabilirsiniz İlk kez biz, bir bölümü yapmak, ancak Yine, unutmayın İkili arama olmasına rağmen Lineer arama daha önemli ölçüde daha iyi Günlük olmanın gereği n n karşı, Eğer çalışma sayesinde gitmek zorunda kalabilirsiniz İlk dizinizi sıralama hangi bağlı daha az etkili hale getirebileceğini kriteri iterating boyutuna. 

Ben Doug Lloyd değilim, bu CS50 olduğunu.