ملخص
الفرز السريع هو خوارزمية الفرز التي طورتها توني هول. في الوضع المتوسط ، يتطلب ترتيب العناصر n مقارنة (Nlogn). في الواقع ، يكون الفرز السريع عادةً أسرع بكثير من خوارزميات (NLOGN) الأخرى ، لأنه يمكن تنفيذ حلقةها الداخلية بكفاءة على معظم البنى ، وفي معظم البيانات الواقعية ، يمكنها تحديد اختيار التصميم وتقليل إمكانية المصطلحات التربيعية التي تتطلب وقتًا.
الفرز السريع ، قسّم السجلات المراد فرزها إلى جزأين مستقلين من خلال ترتيب واحد ، حيث تكون الكلمات الرئيسية لبعض السجلات أصغر من الكلمات الرئيسية للجزء الآخر ، ثم يتم فرز السجلين بشكل منفصل لتحقيق الغرض من طلب التسلسل بالكامل.
توضيح الصورة:
خطوة
عند تحديد عنصر قياسي ، يتم تحديد العنصر الأول أو العنصر الأخير عادة لتقسيم السجلات المراد فرزها إلى جزأين مستقلين من خلال الخزانة الواحدة ، حيث تكون قيم العناصر لبعض السجلات أصغر من قيم العناصر القياسية. العناصر المسجلة في الجزء الآخر أكبر من القيمة المرجعية. في هذا الوقت ، تكون العناصر المرجعية في الموضع الصحيح بعد فرزها ، ثم يتم فرز جزأين من السجلات بنفس الطريقة حتى يتم طلب التسلسل بأكمله.
مثال
البيانات الخام:
3 5 2 6 2
حدد 3 كمعيار
الجولة الأولى
من اليمين إلى اليسار للعثور على شيء أصغر من 3 و 2 تطابقات ، وضبط 2 و 3 2 5 2 6 3 3 مرة واحدة ، ويتم عكس اتجاه البحث ، من اليسار إلى اليمين للعثور على شيء أكبر من 3 ، 5 مباريات ، وضبط 2 3 2 6 5 ثم من اليمين إلى اليسار للعثور
الجولة 2
يتم تنفيذ نفس الطريقة على النحو الوارد أعلاه لـ [2 2] ، و 2 2 3 6 5
الجولة الثالثة
يتم تنفيذ نفس الطريقة على النحو الوارد أعلاه لـ [6 5] ، و 2 2 3 5 6
النتيجة النهائية
2 2 3 5 6
تنفيذ الكود (Java)
package com.coder4j.main.arithmetic.sorting ؛ الطبقة العامة Quick {private static int mark = 0 ؛ / ** * طريقة التبادل المساعدة * * param array * param a * param b */ private static void swap (int [] Array ، int a ، int b) {if (a! = b) {int temp = array [a] ؛ صفيف [a] = صفيف [b] ؛ صفيف [ب] = درجة الحرارة ؛ // ابحث عن المطابقة ، switch system.out.println ("shift" + array [a] + "و" + array [b] + "، get") ؛ لـ (int i: array) {system.out.print (i + "") ؛ } system.out.println () ؛ }} / ** * جولة جديدة من الفصل * * param array * param low * param high * @return * / private static int partition (int array [] ، int low ، int base = array [low] ؛ مارك ++ ؛ System.out.println ("thredth in progress" + mark + "فصل العجلة ، المنطقة:" + low + "-" + High) ؛ بينما (low <High) {بينما (low <High && Array [High]> = base) {High-- ؛ System.out.println ("من اليمين إلى اليسار للعثور على النسبة" + قاعدة + "صغيرة ، تغيير المؤشر:" + low + "-" + High) ؛ } مبادلة (صفيف ، منخفضة ، عالية) ؛ بينما (low <High && Array [low] <= base) {low ++ ؛ System.out.println ("من اليسار إلى اليمين للعثور على النسبة" + قاعدة + "كبيرة ، تغيير المؤشر:" + low + "-" + High) ؛ } مبادلة (صفيف ، منخفضة ، عالية) ؛ } العودة منخفضة ؛ } / ** * الفرز السريع للمصفوفة ، اتصل بشكل متكرر * * param array * param low * param height * @return * / private static int [] Quicksort (int [] int ، int light ، int int) {if (low <height) {int division = partition (Array ، low ، height) ؛ Quicksort (صفيف ، منخفض ، التقسيم - 1) ؛ QuickSort (صفيف ، تقسيم + 1 ، الارتفاع) ؛ } صفيف الإرجاع ؛ } / ** * Quick Sort * * param array * @return * / public static int [] sort (int [] array) {return QuickSort (Array ، 0 ، Array.length - 1) ؛ } main static void main (string [] args) {int [] array = {3 ، 5 ، 2 ، 6 ، 2} ؛ int [] sorted = sort (Array) ؛ System.out.println ("النتيجة النهائية") ؛ لـ (int i: sorted) {system.out.print (i + "") ؛ }}}نتائج اختبار الإخراج:
حدد الكل ووضعه في الملاحظات. يتم تنفيذ الجولة الأولى من الانفصال. المنطقة: 0-4. الجولة الثانية من التعديلات هي 2 و 3. الجولة الثانية من الانفصال هي 2 5 2 6 3. الجولة الثانية من الفصل هي 3 و 5. الجولة الثانية من الانفصال هي 2 3 2 6 5. الجولة الثانية من الانفصال هي 3 و 5. الجولة الثانية من الفصل 2 و 3. الانفصال هو 2 و 3. الجولة الثانية من الفصل هي 2 و 3. الجولة الثانية من الانفصال هي 2 و 3. الجولة الثانية من الانفصال هي 2 و 2 هي 3. 5. الجولة الأخيرة من الانفصال هي 2 هي 2 و 3 هي 5. النتيجة الأخيرة هي 2 هي 2 و 3 هي 5. 6. النتيجة الأخيرة هي 2 2 3 5. 6.
بعد الاختبار ، يتوافق مع النتائج في المثال.