DOUG لويد: حتى في CS50 علمنا مجموعة متنوعة من الفرز والبحث الخوارزميات. وأحيانا يمكن أن يكون صعبة بعض الشيء للحفاظ على تتبع ما خوارزمية يفعل ما. قمنا حقا فقط منزوع الدسم السطح أيضا، هناك الكثير من البحث الأخرى والفرز الخوارزميات. حتى في هذا الفيديو دعنا تأخذ فقط بضع دقائق في محاولة لاستخلاص كل خوارزمية وصولا الى العناصر الأساسية لذا يجب أن نتذكر أكثر معلومات هامة عنهم وتكون قادرة على توضيح الاختلافات، إذا لزم الأمر. 

الأول هو اختيار نوع. الفكرة الأساسية وراء اختيار نوع تم العثور على أصغر عنصر لم يتم فرزها في مجموعة ومبادلة مع ل أول عنصر لم يتم فرزها من أن مجموعة. قلنا إن الأسوأ وقت التشغيل من أنه تم تربيع ن. وإذا كنت تريد أن تذكر السبب، واتخاذ نظرة على الفيديو اختيار نوع. وقت التشغيل أفضل الحالات كما ن المربعة. 

فقاعة النوع، والفكرة وراء ذلك واحد هو لمبادلة الأزواج المجاورة. لذلك هذا هو المفتاح الذي يساعدك تذكر الفرق هنا. اختيار نوع هو، حتى الآن، العثور على فقاعة smallest-- النوع غير مبادلة الأزواج المجاورة. نحن مبادلة الأزواج المجاورة من العناصر إذا كانت هي خارج الترتيب، الذي فعال فقاعات أكبر عناصر إلى اليمين، وفي الوقت نفسه فإنه يبدأ أيضا لنقل عناصر أصغر إلى اليسار. والأسوأ الوقت حالة تشغيل فقاعة نوع n غير المربعة. وقت التشغيل أفضل الحالات فقاعة النوع هو ن. لأنه في هذه الحالة نحن لا actually-- نحن قد لا تحتاج ل إجراء أية مقايضة على الإطلاق. ليس لدينا سوى أن يجعل واحدة تمر عبر جميع العناصر ن. 

في الإدراج النوع، و الفكرة الأساسية هنا يتحول. هذا الكلمة لإدخال نوع. ونحن في طريقنا إلى الخطوة مرة واحدة من خلال مجموعة من اليسار إلى اليمين. وكما نفعل، ونحن الذهاب إلى تحول العناصر رأيناه بالفعل لإفساح المجال ل أصغر تلك التي تحتاج لتناسب مكان ما مرة أخرى في هذا الجزء فرزها. وبالتالي نحن نبني مجموعة فرزها واحدة العنصر في نفس الوقت، من اليسار إلى اليمين، وننتقل الأشياء لإفساح المجال. وقت التشغيل أسوأ حالة ون تربيع الإدراج النوع. الوقت أفضل حال نفاد هو ن. 

دمج sort-- الكلمة هنا يتم تقسيم ودمج. يمكننا تقسيم مجموعة كاملة، سواء انها ستة عناصر، ثمانية عناصر، 10000 elements-- نحن تقسيمه بمقدار النصف، بمقدار النصف، بمقدار النصف، حتى يكون لدينا تحت مجموعة ن واحد صفائف عنصر. وهناك مجموعة من ن واحد صفائف عنصر. لذلك بدأنا مع واحد مجموعة 1000 عنصر، ونصل إلى النقطة التي وصلنا لدينا 1000 صفائف عنصر واحد. ثم نبدأ في دمج تلك المصفوفات الفرعية معا مرة أخرى في الترتيب الصحيح. لذلك نحن نأخذ اثنين من صفائف عنصر واحد وإنشاء مجموعة من عنصر اثنين. نحن نأخذ اثنين من صفائف عنصر اثنين وإنشاء مجموعة أربعة عناصر وهلم جرا وهكذا دواليك حتى قمنا أعيد بناؤها مرة أخرى واحدة مجموعة العنصر n. 

وقت التشغيل أسوأ حالة دمج النوع غير مرة n السجل ن. لدينا عناصر ن، ولكن هذه العملية إعادة توحيد يأخذ تسجيل ن الخطوات للحصول على دعم لمجموعة كاملة. أفضل حال نفاد الوقت أيضا ن سجل ن لأن هذه العملية لا حقا يهمني ما إذا كانت مجموعة مرتبة أم لا لتبدأ. هذه العملية هي نفسها، وهناك أي وسيلة لأشياء ماس كهربائى. هكذا ن ن تسجيل في أسوأ الأحوال، ن ن تسجيل في أفضل الأحوال. 

تحدثنا عن اثنين البحث الخوارزميات. لذلك البحث الخطي نحو بالتكرار. ننطلق عبر مجموعة مرة واحدة، من اليسار إلى اليمين، محاولة للعثور على عدد أن نبحث عنه. الساعة أسوأ حال نفاد هو يا كبير من ن. قد يستغرق لنا بالتكرار عبر كل عنصر واحد العثور على عنصر نحن نبحث ل، سواء في المركز الأخير، أو لا على الاطلاق. ولكن لا يمكننا تأكيد ذلك حتى لقد بحثت في كل شيء. م أفضل الحالات، نجد على الفور. وقت التشغيل أفضل حالة البحث الخطي هو أوميغا 1. 

وأخيرا، كان هناك بحث ثنائي، الأمر الذي يتطلب مجموعة متنوعة. تذكر هذا جدا الاعتبارات الهامة عند العمل مع البحث الثنائي. انها شرط أساسي لاستخدام it-- مجموعة التي كنت أبحث من خلال يجب فرزها. خلاف ذلك، والكلمة هو فرق تسد. تقسيم مجموعة إلى نصف و القضاء على نصف العناصر في كل مرة كما كنت المضي قدما من خلال. وبسبب هذا فرق تسد وأشياء تقسيم في نصف النهج، وقت التشغيل الأسوأ البحث ثنائي تسجيل ن، والتي هي إلى حد كبير أفضل من ن البحث الخطي ل. الوقت أفضل حال نفاد لا يزال واحدا. 

قد نجد أنه على الفور المرة الأولى التي نقوم بإجراء التقسيم، ولكن، مرة أخرى، تذكر أن على الرغم من أن البحث ثنائي أفضل بكثير من البحث الخطي بحكم كونه سجل ن ن مقابل، قد يكون لديك للذهاب من خلال عمل فرز مجموعة الخاصة بك أولا، التي قد جعلها أقل فعالية اعتمادا على حجم بالتكرار فرزها. 

أنا دوغ ويد، وهذا هو CS50.