[عزف الموسيقى] 

DOUG لويد: OK، ولذلك فإن دمج النوع هو بعد خوارزمية أخرى التي يمكننا استخدامها لفرز عناصر صفيف. ولكن كما سنرى، انها حصلت على الفرق الأساسي جدا من اختيار نوع، فقاعة النوع، والإدراج الفرز التي تجعل حقا ذكي جدا. 

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

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

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

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

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

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

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

حسنا، الآن لدينا ثلاثة مجموعة العنصر. كيف يمكننا فرز النصف الأيسر من هذا مجموعة، التي لا تزال هذه الخطوة؟ نحاول فرز اليسار نصف array-- الأحمر الطوب النصف الأيسر منها لقد الملونة الآن البرتقال. 

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

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

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

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

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

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

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

النصف الأيسر، أصغر عنصر في النصف الأيسر هو خمسة. أصغر عنصر في النصف الأيمن هو واحد. أي من هؤلاء هو أصغر؟ واحدة. 

أصغر عنصر في النصف الأيسر هو خمسة. أصغر عنصر في النصف الأيمن هو اثنين. ما هو أصغر؟ اثنين. ثم أخيرا خمسة و لا شيء، نستطيع أن نقول خمسة. 

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

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

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

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

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

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

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

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

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

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

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

قارنا أصغر قيمة على الجانب الأيسر من array-- أو عفوا، أصغر قيمة النصف الأيسر إلى أصغر قيمة الحق نصف وتجد أن ثلاثة هي أصغر. والآن قليلا من التحسين، أليس كذلك؟ هناك في الواقع شيئا تركت على الجانب الأيسر. 

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

حسنا، الآن دعونا مرة أخرى وتجميد معرفة أين نحن في القصة. في مجموعة الشاملة، ما أنجزناه؟ لقد إنجاز فعلا الخطوات الآن واحدة وخطوتين. نحن فرز النصف الأيسر، و نحن فرز النصف الأيمن. 

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

الثاني هو أقل من ثلاثة، لذلك يذهب اثنين. ثلاثة أقل من 5، لذلك ثلاثة يذهب. أربعة أقل من 5، لذلك أربعة يذهب. ثم خمسة هو أقل من ستة، وستة هو كل ما تبقى. 

الآن، وأنا أعلم، وكان ذلك الكثير من الخطوات. ولقد ترك الكثير من الذاكرة في أعقاب لدينا. وهذا ما هي تلك الساحات الرمادية. وربما شعرت أن أخذت الكثير أطول من الإدراج النوع، فقاعة نوع، أو اختيار نوع. 

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

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

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

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

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

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