تعقيد الوقت
المتوسط: O (NLGN)
أسوأ حالة: o (n*n) ، يحدث عندما تكون البيانات بالفعل في حالة الفرز.
1. حدد قيمة A [i] من البيانات كمرجع
2. أخذ [i] كمرجع ، قسّم البيانات إلى جزأين: P1 و P2. جميع البيانات في p1≤a [i] ، جميع البيانات في p2> a [i] ، وتصبح البيانات {{p1} {a [i]} {p2}}
3. كرر الخطوات أعلاه مع P1 و P2 حتى يتم ترك بيانات واحدة فقط في كل جزء.
4. يتم فرز البيانات بترتيب تصاعدي
مثال أساسي:
البيانات الخام:
{3 ، 9 ، 8 ، 5 ، 2 ، 1 ، 6} الخطوة 1: حدد البيانات الأولى: 3
الخطوة 2: قسّم البيانات إلى جزأين ، والجانب الأيسر هو ≤3 ، والجانب الأيمن أكبر من> 3:
{2،1} {3} {9،8،5،6} الخطوة 3: كرر الخطوات المذكورة أعلاه لكل جزء حتى يتم ترك بيانات واحدة فقط في كل جزء:
{2،1} => {1} {2} {9 ، 8 ، 5 ، 6} => {8 ، 5 ، 6} {9} => {5 ، 6} {8} {9} => {5} {6}} {9} الخطوة 4: يتم فرز البيانات بترتيب تصاعدي:
{1} {2} {3} {5} {6} {8} {9}عادة ما يتم تخزين البيانات في البرنامج في صفيف. أخذ مجموعة من النوع int كمثال ، يمكنك كتابة الخطوات المذكورة أعلاه إلى نموذج أولي للدالة Quicksort:
QuickSort (int begr ، int end) {// begin هي قيمة الفهرس للبيانات الأولى للمصفوفة ، النهاية هي قيمة الفهرس للبيانات الأخيرة من المصفوفة +1 // إذا كانت هناك بيانات واحدة فقط أو 0 بيانات ، فإن البرنامج يعود إذا (start == end || begin == (end-1)) إرجاع ؛ int p = in [start] ؛ // p هو بيانات المرجع المحددة ، حدد البيانات الأولى int a = start +1 ؛ // A كقيمة فهرس للبيانات المكونة من جزأين تقسيم السطر int b = a ؛ // b هي قيمة الفهرس للبيانات المراد مقارنتها لـ (؛ b <end ؛ b ++) {// قارن البيانات في المصفوفة مع البيانات المرجعية بالتسلسل إذا (في [b] <p) {// إذا كانت البيانات <البيانات المرجعية ، تحركها إلى اليسار إذا (a == b) {a a++؛ متابعة ؛} // إذا كانت البيانات موجودة بالفعل على اليسار ، فلن تتحرك int temp = في [a] ؛ // نقل البيانات إلى اليسار في [a] = في [b] ؛ في [ب] = درجة الحرارة ؛ A ++ ؛ // حرك الخط الفاصل الأيمن}}} في [begin] = في [A-1] ؛ // whike القيمة المرجعية إلى منتصف مجموعتين من البيانات في [a-1] = p ؛ إذا (A-1> start) {// إذا كانت هناك بيانات على اليسار ، كرر الخطوات المذكورة أعلاه Quicksort (ابدأ ، أ) ؛ } if (end-1> a) {// إذا كانت هناك بيانات على اليمين ، كرر الخطوات المذكورة أعلاه QuickSort (a ، end) ؛ } يعود؛ // إذا لم تكن هناك بيانات} تحسين الخوارزمية
يمكن القول أن خوارزمية الفرز السريع أعلاه هي النوع السريع الأساسي لأنه لا يأخذ في الاعتبار أي بيانات إدخال. ومع ذلك ، من السهل العثور على عيوب هذه الخوارزمية: هذا هو عندما يتم طلب بيانات الإدخال لدينا بشكل أساسي أو حتى يتم طلبها بالكامل ، تتحول الخوارزمية إلى فرز الفقاعات ، لم تعد O (NN) ، ولكن O (n^2).
السبب الجذري هو أنه في تنفيذ الكود لدينا ، نبدأ فقط من الصفيف الأول في وقت واحد. إذا استخدمنا "ثلاثة رأس" ، أي أن القيم المتوسطة لـ ARR [Low] ، ARR [High] ، ARR [(Low+High)/2] كسجل محوري ، يمكن تحسين أداء الفرز السريع في سيناريو أسوأ حالة إلى حد كبير. ومع ذلك ، ما زلنا لا نستطيع تحسين أدائها إلى O (n) في الحالة التي تم طلبها. هناك أيضًا طرق لتحسين الأداء الزمني للفرز السريع في سيناريو أسوأ الحالات إلى درجات متفاوتة.
بالإضافة إلى ذلك ، يتطلب الفرز السريع مكدسًا متكررًا ، والذي عادة ما يكون عميقًا جدًا وهو على مستوى السجل (N). ومع ذلك ، إذا كان طول المصفمين المقسمين في وقت واحد غير متوازن للغاية ، في أسوأ الحالات ، فإن عمق المكدس سيزداد إلى O (n). في هذا الوقت ، لا يمكن تجاهل التعقيد المكاني الناتج عن مساحة المكدس. إذا تمت إضافة النفقات العامة للمتغيرات الإضافية ، فقد تصل إلى تعقيد الفضاء O (n^2) المرعب هنا. لذلك ، فإن أسوأ التعقيد المكاني للفرز السريع ليس قيمة ثابتة ، وقد لا يكون في نفس المستوى.
لحل هذه المشكلة ، يمكننا مقارنة أطوال النهايات بعد كل قسم وفرز التسلسلات القصيرة أولاً (الغرض من ذلك هو إنهاء هذه المداخن أولاً لتحرير المساحة) ، والتي يمكن أن تقلل من الحد الأقصى للعمق إلى مستوى O (n).
فيما يلي ثلاث أفكار تحسين للفرز السريع:
بالنسبة للصفائف الصغيرة ، يمكن استخدام فرز الإدراج لتجنب المكالمات العودية. على سبيل المثال ، عندما (مرحبًا <= lo + m) ، يمكنك الذهاب إلى إدراج نوع.
استخدم وسيط سفر تحت صفيف شريحة الصفيف. يؤدي هذا إلى تقطيع أفضل ، ولكن على حساب حساب الوسيط.
إذا كانت الصفيف تحتوي على عدد كبير من العناصر المتكررة ، فيمكن استخدام تقطيع ثلاثي الاتجاه. قسّم الصفيف إلى ثلاثة أجزاء ، المقابلة لعناصر الصفيف الأصغر من ، وأكبر من عناصر التقطيع على التوالي. تطبيق الكود كما يلي:
private static void sort1 (int [] a ، int lo ، int hi) {if (hi <= lo) return ؛ int lt = lo ، i = lo + 1 ، gt = hi ؛ int v = a [lo] ؛ بينما (i <= gt) {if (a [i] <v) {swap (a ، lt ++ ، i ++) ؛ } آخر إذا (a [i]> v) {swap (a ، i ، gt--) ؛ } آخر {i ++ ؛ } sort (a ، lo ، lt - 1) ؛ فرز (A ، GT + 1 ، مرحبًا) ؛ }}