النوع السريع هو نوع من نوع تبادل التقسيم الذي اقترحه Crahoare في عام 1962. الفكرة الأساسية لهذه الطريقة هي:
1. أولاً ، خذ رقمًا من التسلسل كرقم مرجعي.
2. في عملية التقسيم ، ضع جميع الأرقام أكبر من هذا الرقم على يمينه ، وجميع الأرقام أصغر من أو تساوي يسارها.
3. كرر الخطوة الثانية للفترات اليمنى واليمنى حتى يكون هناك رقم واحد فقط في كل فاصل.
تحتوي الخوارزمية على فكرة واضحة ، ولكن إذا لم يتم التعامل مع قيمة الحدود بشكل جيد أثناء عملية تقسيم الفاصل الزمني ، فمن السهل التسبب في الأخطاء. فيما يلي تفكير أكثر وضوحًا لتوجيه كتابة رمز تقسيم الفاصل.
النوع الأول من التفكير هو التفكير في طريقة الحفر الحفرة. ما يلي هو تحليل عملية الحفر الحفرة من خلال تحليل مثال:
أخذ صفيف كمثال ، خذ الرقم الأول في الفاصل الزمني كرقم مرجعي.
في البداية ، اليسار = 0 ؛ اليمين = 9 ؛ x = a [يسار] = 72
نظرًا لأن الرقم الموجود في A [0] قد تم حفظه إلى X ، يمكن فهمه على أنه حفر ثقب في المصفوفة A [0] ، ويمكن ملء البيانات الأخرى هنا.
ابدأ من اليمين وابحث عن عدد من <= x. من الواضح ، عندما يكون اليمين = 8 ، إذا تم استيفاء الشروط ، فقم بإخراجها [8] واملأها في الحفرة السابقة A [اليسار]. يتم حل مثل هذا الحفرة A [0] ، ولكن يتم تشكيل حفرة جديدة [8]. ماذا علي أن أفعل؟ بسيط ، ابحث عن الرقم لملء الحفرة A [8]. هذه المرة ، ابدأ من اليسار وابحث عن رقم أكبر من X. عند اليسار = 3 ، تلبية الشروط ، وينفجر A [3] واملأه في الحفرة السابقة A [يمين] ؛
الصفيف يصبح:
كرر الخطوات المذكورة أعلاه وسيصبح الصفيف النهائي هو النموذج التالي:
يمكن ملاحظة أن الأرقام قبل [5] أصغر منها ، والأرقام بعد A [5] أكبر منها. املأ x في حفرة A [5] وتصبح البيانات:
لذلك ، كرر الخطوات المذكورة أعلاه للداخلين الفرعيين A [0 ... 4] و A [6 ... 9].
ملخص لعدد الثقوب المحفورة
1. i = l ؛ j = r ؛ قم بإخراج الرقم المرجعي لتشكيل الحفرة الأولى A [i].
2. J-من الخلف إلى المقدمة ، ابحث عن الرقم أصغر منه ، وحفر هذا الرقم وملء الحفرة السابقة A [i].
3. I ++ يجد رقمًا أكبر منه من الأمام إلى الخلف ، وبعد العثور عليه ، قم بإخراج هذا الرقم وملءه في الحفرة السابقة A [J].
4. كرر الخطوات 2 و 3 حتى i == j ، واملأ الرقم المرجعي في [i].
اتبع طريقة التقسيم هذه ، يتم فرز رمز Java بسرعة على النحو التالي:
قسم الفئة العامة { / ** * استنادًا إلى القسم الأساسي ، يكون الصغار على اليسار والكبير على اليمين ، ولا يلزم طلب التسلسل بأكمله * * param ary * param base * / static void sort (int [] ary ، int base) {int left = 0 ؛ int right = ary.length - 1 ؛ int int layspoint = left ، rightpoint = right ؛ بينما (صحيح) {// اقسم إلى اليسار واليمين إلى اليمين في نفس الوقت للمقارنة ، من اليسار إلى اليمين ، بينما (lightpoint <right && ary [LaftPoint ++] <base) ؛ // LASEPOINT أكبر من اليمين أو ary [LAVESPOINT]> توقف القاعدة عن الحلقات بينما (يمين> = يسار && ary [rightpoint--]> base) ؛ // على عكس النظام. System.out.println ("الفهرس الذي يجب تبديله على اليمين:"+ (pointpoint+ 1)) ؛ . util.printarray (ary) ؛ بوينت = اليسار ؛ اليمين = يمين ؛ } آخر {break ؛ }}} تبادل الفراغ الثابت الخاص (int [] ary ، int a ، int b) {int temp = ary [a] ؛ ary [a] = ary [b] ؛ آري [ب] = درجة الحرارة ؛ } main static void main (string [] args) {int [] ary = util.generateIntArray (10) ؛ System.out.println ("التسلسل الأصلي:") ؛ util.printarray (ary) ؛ فرز (آري ، 5) ؛ system.out.println ("sorted:") ؛ util.printarray (ary) ؛ }} نتيجة:
التسلسل الأصلي: [2 ، 8 ، 4 ، 3 ، 7 ، 5 ، 1 ، 9 ، 0 ، 6] فهرس للتبادل على اليسار: 1 فهرس للتبادل على اليمين: 8 [2 ، 0 ، 4 ، 3 ، 7 ، 5 ، 1 ، 9 ، 8 ، 6] فهرس للتبادل على اليسار: 4 فهرس للتبادل: الفرز: [2 ، 0 ، 4 ، 3 ، 1 ، 5 ، 7 ، 9 ، 8 ، 6]
تفكير توجيهي آخر في قسم الفاصل:
استخدم العنصر الأول من الصفيف كقيمة فاصل ، وقسمه من العنصر الثاني حتى يتم تشكيل النتيجة الموضحة في الشكل.
ثم تبادل القيم الحدودية الصحيحة و T للفاصل الزمني لتكوين النتيجة التالية:
وبهذه الطريقة ، يمكنك كتابة رمز فرز سريع على النحو التالي:
public void qsort (int array [] ، int left ، int right) {if (left <right) {int key = array [left] ؛ int عالية = يمين ؛ int low = left+1 ؛ بينما (صحيح) {بينما (low <= high && array [low] <= key) low ++ ؛ بينما (منخفض <= High && Array [High]> = Key) High-- ؛ إذا (منخفض> مرتفع) كسر ؛ مبادلة (صفيف ، منخفضة ، عالية) ؛ } مبادلة (صفيف ، يسار ، مرتفع) ؛ printarray (صفيف) ؛ QSort (صفيف ، يسار ، عالية 1) ؛ QSort (صفيف ، مرتفع+1 ، يمين) ؛ }}