يُستخدم الفرز السريع على نطاق واسع باعتباره خوارزمية فرز فعالة. تستخدم طريقة Arrays.sort في JDK الخاصة بـ SUN الفرز السريع.
يتبنى الفرز السريع فكرة فرق تسد الكلاسيكية:
التقسيم: حدد X البدائي (عادةً العنصر الأول في المصفوفة)، وقم بتقسيم المصفوفة إلى جزأين من خلال بعض عمليات التقسيم: النصف الأيسر أقل من أو يساوي X، والنصف الأيمن أكبر من أو يساوي X .
Conquer: تستدعي المصفوفتان الفرعيتان اليسرى واليمنى عملية Divide بشكل متكرر.
الدمج: يتم استخدام الفرز السريع كخوارزمية فرز موضعي ولا يتطلب أي عمليات دمج.
يمكن ملاحظة أن الجزء الأساسي من الفرز السريع هو عملية التقسيم. وفيما يلي مثال لشرح كيفية تقسيم المصفوفة بالتفصيل (الصورة مأخوذة من "مقدمة إلى الخوارزميات").
التهيئة: حدد العنصر البدائي P=2، وهو العنصر الأول في المصفوفة. i=1,j=i+1=2 (الصفيف منخفض يبدأ بـ 1)
حلقة ثابتة: العناصر الموجودة بين 2~i كلها أقل من أو تساوي P، والعناصر الموجودة بين i+1~j كلها أكبر من أو تساوي P.
عملية الحلقة: ينتقل j من 2 إلى n، ويفحص العنصر في الموضع j، وإذا كان أكبر من أو يساوي P، تابع الحلقة. إذا كان أقل من P، قم بتبديل العناصر الموجودة في الموضع j (الذي لا ينبغي أن يظهر في النطاق i+1~j) مع العناصر الموجودة في الموضع i+1 (لا يزال في النطاق i+1~j بعد التبادل)، وفي نفس الوقت قم بتغيير i+1. وهذا يحافظ على ثوابت الحلقة (انظر وصف ثوابت الحلقة أعلاه). حتى j=n، تكتمل عملية الحلقة الأخيرة.
تجدر الإشارة إلى أنه بعد إكمال الحلقة، يجب تبادل العنصر الموجود في الموضع i مع العنصر الأول في المصفوفة لتلبية المتطلبات التي حددناها أولاً (المقابلة للخطوة i في الشكل).
قد يفكر القراء المتأنيون في طريقة تقسيم أخرى أكثر وضوحًا، وهي إزالة العناصر الأولية وتخزينها في مصفوفة أخرى بنفس الحجم. عند مواجهة عناصر أصغر من العناصر الأولية، يتم تخزينها في النصف الأيسر من المصفوفة العناصر الأكبر من العناصر الأولية، يتم تخزينها في النصف الأيسر من المصفوفة. يتم تخزين العناصر في النصف الأيمن من المصفوفة. تعقيد مثل هذه العمليات خطي أيضًا، أي ثيتا (ن). لكن تعقيد الفضاء مضاعف. وهذه أيضًا ميزة الفرز السريع في المكان.
انسخ رمز الكود كما يلي:
الطبقة العامة QuickSort {
الفرز السريع الخاص بفراغ ثابت (int[] array،int start،int end)
{
إذا (البدء<النهاية)
{
int key=array[start];// تهيئة وحفظ الأوليات
int i=start,j;// تهيئة i,j
ل(ي=بداية+1;ي<=نهاية;ي++)
if(array[j]<key)// إذا كان العنصر هنا أقل من العنصر البدائي، فاستبدل هذا العنصر بالعنصر الموجود في i+1، وأضف 1 إلى i. إذا كان أكبر من العنصر البدائي أو يساويه، فاستمر الحلقة.
{
int temp=array[j];
array[j]=array[i+1];
array[i+1]=temp;
أنا++;
}
}
array[start]=array[i];// تبادل العناصر والأوليات في i
array[i]=key;
QuickSort(array, start, i-1);//استدعاء متكرر
QuickSort(array, i+1, end);
}
}
الفراغ العام الثابت الرئيسي (String[] args)
{
int[] array=new int[]{11,213,134,44,77,78,23,43};
QuickSort(array, 0, array.length-1);
ل(int i=0;i<array.length;i++)
{
System.out.println((i+1)+"th:"+array[i]);
}
}
}