داگ لوید: بنابراین در CS50 ما در مورد به دست انواع مرتب سازی و جستجو الگوریتم باشد. و گاهی اوقات می توان آن را یک مشکل کمی برای حفظ آهنگ از چه الگوریتم می کند آنچه. ما واقعا تنها خامه سطح بیش از حد، بسیاری از جستجوی دیگر وجود دارد و مرتب سازی الگوریتم باشد. بنابراین در این فیلم اجازه دهید فقط چند دقیقه طول می کشد را امتحان کنید و تقطیر هر الگوریتم به عناصر اصلی آن بنابراین شما می توانید به یاد داشته باشید ترین اطلاعات مهم در مورد آنها و قادر به بیان تفاوت ها، در صورت لزوم. 

اولین مرتب سازی انتخابی است. ایده اصلی در پشت مرتب سازی انتخابی است پیدا کردن کوچکترین عنصر نامرتب در یک آرایه و آن را مبادله با اولین عنصر آرایه نامرتب از که. ما گفت که بدترین حالت زمان اجرا که N مربع بود. و اگر شما می خواهید به یاد چرا، را نگاهی به فیلم مرتب سازی انتخابی است. در بهترین حالت زمان اجرا همچنین N مربع. 

حباب مرتب سازی بر، ایده پشت این یکی است که به مبادله جفت های مجاور. به طوری که کلیدی است که شما کمک می کند را به یاد داشته باشید تفاوت در اینجا. مرتب سازی انتخابی است، تا کنون، پیدا کردن حباب smallest-- مرتب کردن بر اساس مبادله جفت های مجاور. ما مبادله جفت های مجاور از عناصر اگر آنها خارج از دستور، که به طور موثر حباب عناصر بزرگتر به سمت راست، و در همان زمان آن را نیز آغاز می شود به حرکت عناصر کوچکتر به سمت چپ. بدترین حالت زمان مورد اجرا از مرتب سازی حبابی است N مربع. در بهترین حالت زمان اجرا از حباب مرتب سازی بر است N. از آنجا که در این وضعیت ما actually-- نیست ما ممکن است نیاز به هر گونه معاوضه در همه. ما فقط باید برای ساختن یک تصویب در تمام عناصر N. 

در مرتب سازی بر درج، ایده اصلی در اینجا در حال تغییر است. که کلمه کلیدی برای مرتب سازی درجی است. ما در حال رفتن به مرحله یک بار از طریق آرایه از چپ به راست. و همانطور که ما انجام دهید، ما رفتن به تغییر عناصر ما در حال حاضر دیده می شود به اتاق را برای کوچکتر که نیاز به جا به جایی در آن بخش طبقه بندی شده اند. بنابراین ما ساخت یک آرایه مرتب شده عنصر در یک زمان، چپ به راست، و ما تغییر همه چیز را به اتاق. بدترین حالت زمان اجرا از مرتب سازی بر درج شده است N مربع. ساعت هم بهترین حالت اجرا است N. 

ادغام sort-- کلمه کلیدی در اینجا تقسیم و ادغام. ما تقسیم آرایه کامل، چه آن را شش عنصر، هشت عنصر، 10،000 elements-- ما آن را تقسیم پایین به نصف، نصف، نصف، تا زمانی که ما تحت آرایه دارند از n یک آرایه عنصر. مجموعه ای از N یک آرایه عنصر. بنابراین ما با یک آغاز شده آرایه 1،000 عنصر، و ما به نقطه که در آن ما 1،000 آرایه یک عنصر است. پس از آن ما شروع به ادغام آن زیر آرایه تماس با هم در جهت درست. بنابراین ما دو آرایه یک عنصر و ایجاد یک آرایه دو عنصر است. ما را دو آرایه دو عنصر و ایجاد یک آرایه چهار عنصر و به همین ترتیب و تا زمانی که ما این دوباره بازسازی یک آرایه از عناصر N. 

بدترین حالت زمان اجرا از ادغام مرتب کردن بر اساس n بار log n است. ما عناصر N، اما این فرایند ترکیب مجدد طول می کشد log n است مراحل دریافت به یک آرایه کامل برگشت. بهترین حالت زمان اجرا نیز N ورود به سیستم N چرا که این فرآیند واقعا نمی مراقبت که آیا آرایه بود طبقه بندی شده اند و یا برای شروع با است. این روند همان است، وجود دارد هیچ راهی برای چیزهایی اتصال کوتاه. بنابراین n log n استفاده در بدترین حالت، n log n استفاده در بهترین حالت. 

ما در مورد دو صحبت جستجو الگوریتم. بنابراین جستجوی خطی است که در مورد تکرار. ما در سراسر آرایه ادامه یک بار، از چپ به راست، تلاش برای پیدا کردن تعداد که ما دنبال آن هستید. ساعت هم بدترین حالت اجرا O بزرگ از n است. این ممکن است ما را تکرار در سراسر هر عنصر برای پیدا کردن عنصر ما به دنبال برای، چه در موقعیت و زمان آخرین، یا نه در همه. اما ما نمی توانیم تا زمانی که تایید می کنند که ما همه چیز را کرده ام. متر در بهترین حالت، ما بلافاصله پیدا کنید. در بهترین حالت زمان اجرا از جستجوی خطی امگا، از مجموع 1 است. 

در نهایت، بود جستجوی دودویی وجود دارد، که نیاز به آرایه های همه فن حریف. به یاد داشته باشید که بسیار توجه مهم در هنگام کار با جستجوی دودویی. این یک پیش نیاز به استفاده it-- آرایه که شما به دنبال از طریق باید طبقه بندی شده اند. در غیر این صورت، کلمه کلیدی تقسیم و حل است. تقسیم این آرایه را به نصف و از بین بردن نیمی از عناصر هر بار که شما ادامه از طریق. از آنجا که این تقسیم و حل و چیزهای تقسیم در نیمه رویکرد، بدترین حالت زمان اجرا از جستجوی دودویی است log n است، که قابل ملاحظه است بهتر از N جستجوی خطی است. ساعت هم بهترین حالت اجرا هنوز هم یکی. 

ما ممکن است آن را بلافاصله پیدا اولین بار که ما را یک تقسیم، اما، دوباره، به یاد داشته باشید که اگرچه جستجوی دودویی است قابل ملاحظه ای بهتر از جستجوی خطی به خاطر اینکه ورود N در برابر N، شما ممکن است از طریق کار به مرتب سازی آرایه خود را برای اولین بار است که ممکن است آن را کمتر بسته موثر به اندازه از تکرار طبقه بندی شده اند. 

من داگ لوید هستم، این CS50.