شرح الرسوم والنص لطريقة تطبيق خوارزمية فرز سريع للفرز السريع في جافا

بالمقارنة مع الخوارزميات مثل فرز الفقاعات ، فرز الاختيار ، وما إلى ذلك ، يصعب صعوبة مبادئ الخوارزمية المحددة وتنفيذ الفرز السريع. لفهم الفرز السريع بشكل أفضل ، ما زلنا نصف المبادئ الخوارزمية للفرز السريع بالتفصيل في شكل أمثلة. في خوارزمية الفرز السابقة ، سوف نستخدم مشكلة فرز الارتفاع لـ 5 رياضيين كمثال لشرح ذلك. من أجل التعكس بشكل أفضل خصائص الفرز السريع ، سنضيف 3 رياضيين آخرين هنا. الرياضيون الثمانيون ومعلومات الارتفاع في المثال هم كما يلي (F ، G ، H هم رياضيين جدد): A (181) ، B (169) ، C (187) ، D (172) ، E (163) ، F (191) ، G (189) ، H (182)

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

وفقًا لمبدأ الخوارزمية لطريقة الفرز السريع ، يقف المساعدان على جانبي ترتيب الرياضي ، كما هو موضح في الشكل أدناه:

أولاً ، يختار مساعد 1 رياضيًا من الترتيب (عادةً ما يختار أول رياضي على اليسار أو الرياضي الأوسط) ، وهنا يختار رياضي (181). نظرًا لأن الفرز من اليسار إلى اليمين ومن منخفض إلى أعلى ، يتطلب المساعد 1 رياضيًا أصغر في الارتفاع من (181) (يتم استخدام A (181) كمعيار للمقارنة. تتم مقارنة جميع المقارنات في هذه الجولة مع الرياضي المختار في البداية (181)):

دعنا نستمر في الرجوع إلى الرسم البياني التفصيلي للجولة الأولى من الفرز السريع.

عندما يجتمع المساعدون أثناء عملية الفرز والبحث ، يتم إيقاف مقارنة الجولة الحالية ويتم وضع الرياضي المختار في البداية (181) في المساحة الفارغة حيث يجتمع المساعدون:

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

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

الآن ، ما زلنا نبرمج رمز Java لفرز ارتفاعات الرياضيين 8 أعلاه باستخدام نوع سريع:

 /*** الفرز السريع للعناصر في الصفيف المحدد من البداية إلى النهاية** param صفيف الصفيف المحدد* param ابدأ النقطة الناتجة عن استفسار الصفيف الذي يجب فرزه بسرعة* end end end end end in in in in in ، is in in in in in in is en ex en e is en e is in in e is en e is in in in ، يعادل موقف المساعد 2 int i = start ، j = end ؛ int pivot = array [i] ؛ // خذ العنصر الأول كعنصر مرجعي int fmareIndex = i ؛ // يشار إلى فهرس الموضع للمساحة الفارغة ، والافتراضي هو موضع العنصر المرجعي الذي يتم استرداده // إذا كان هناك أكثر من عنصر واحد لفرز ، فأدخل نوعًا سريعًا (طالما أن أنا و j يختلفان ، فهذا يعني أن هناك عناصر صفيف على الأقل (j] إذا كان (i <j) {// إذا وجد مساعد 2 العنصر المقابل قبل مواجهة مساعد 1 ، فإنه يعطي العنصر إلى "الوظائف الشاغرة" للمساعد 1 ، j يصبح صفيف مساحة فارغ [فارغد } // Assistant 1 يبدأ في البحث عن عناصر أكبر من العنصر المرجعي من اليسار إلى اليمين (i <j && array [i] <= pivot) i ++ ؛ إذا كان (i <j) {// إذا وجد مساعد 1 العنصر المقابل قبل مواجهة مساعد 2 ، فسوف يعطي العنصر إلى "الشواغر" للمساعد 2 ، وأصبحت صفيفًا شاغرًا [فارغد }} // بعد مساعد 1 ومساعد 2 اللقاء ، ستتوقف الحلقة ويتم أخذ القيمة المرجعية الأولية إلى صفيف شاغر آخر [فارغدد] = pivot ؛ // ====== يتم الانتهاء من هذه الجولة من الفرز السريع ====== // إذا كان هناك أكثر من عنصرين على الجانب الأيسر من النقطة المنقسمة I ، تستمر المكالمة العودية في فرزها بسرعة إذا (I - ابدأ> 1) {QuickSort (Array ، 0 ، i - 1) ؛ } // إذا كان هناك أكثر من عنصرين على الجانب الأيمن من نقطة الانقسام J ، فستستمر المكالمة العودية في فرزها بسرعة إذا (end - j> 1) {QuickSort (Array ، j + 1 ، end) ؛ }} // main may main main static void main (string []] args) {// ===== lore from low to thight with require sort tell لتمثيل ارتفاعات 8 رياضيين ====== // a (181) ، b (169) ، c (187) ، d (172) ، e (163) ، f (191) ، g (189) ، h (182) 187 ، 172 ، 163 ، 191 ، 189 ، 182} ؛ // استدعاء طريقة الفرز السريع QuickSort (مرتفعات ، 0 ، ارتفاعات. الطول - 1) ؛ // النتيجة المصنفة لـ (ارتفاع int: مرتفعات) {system.out.println (الارتفاع) ؛ }}

يتم إخراج نتائج تشغيل رمز Java أعلاه على النحو التالي:

 163169172181182187189191

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

تطبيق آخر: مسح في اتجاه واحد
هناك نسخة فحص أخرى في اتجاه واحد للتقطيع السريع للفرز. الخطوة المحددة هي تحديد العنصر الأخير في الصفيف كعنصر التقطيع ، وتعيين مؤشرين. يشير المؤشر الذي أشير إليه إلى موقع أمام العنصر الأول في الصفيف ، ويشير J إلى العنصر الأول في الصفيف. J فحوصات من الأمام إلى اليمين واليمين. عند مواجهة عنصر تقطيع أقل من أو يساوي ، أضف I إلى واحد ، ثم تبادل العناصر التي أشار إليها I و J. أخيرًا ، تبادل العناصر في الموضع i+1 وعناصر التقطيع لإكمال قسم الصفيف. تطبيق الكود كما يلي:

 int partition (int [] a ، int lo ، int hi) {int i = lo - 1 ، j = lo ؛ int v = a [hi] ؛ بينما (j <hi) {if (a [j] <= v) {swap (a ، ++ i ، j) ؛ } j ++ ؛ } swap (a ، i + 1 ، hi) ؛ إرجاع i + 1 ؛}