فرز سريع ، والمعروف أيضا باسم التقسيم وفرز المبادلة. خوارزمية الفرز السريعة التي تم تنفيذها مع استراتيجية التقسيم والقهر.
تتحدث هذه المقالة بشكل أساسي عن استخدام JavaScript لتنفيذ الفرز السريع للأفكار الموجودة في مكانها
تقسيم الأساليب والعلاج:
في علوم الكمبيوتر ، تعد طريقة التقسيم والقهر نموذجًا مهمًا للغاية خوارزمية يعتمد على عودية فرع متعددة. التفسير الحرفي هو "تقسيم وقهر" ، مما يعني تقسيم مشكلة معقدة إلى مشكلتين فرعيتين أو أكثر مماثلة أو مماثلة حتى يمكن حل نهاية المشكلات الفرعية ببساطة ومباشرة ، ومحل المشكلة الأصلية هو دمج حلول المشكلات الفرعية. (مقتطفات من ويكيبيديا)
فكرة فرز سريعة
حدد عنصرًا في المصفوفة كمسطرة ، ضع أكبر منه ووضع أصغر منه قبل العنصر ، كرر ذلك حتى يتم ترتيب الجميع بالترتيب الإيجابي.
يتم تقسيم الفرز السريع إلى ثلاث خطوات:
حدد معيارًا: حدد عنصرًا كمعيار في بنية البيانات (PIVOT)
القسم: ارجع إلى حجم قيمة العنصر المرجعي ، قسّم المنطقة غير المرتبة. يتم وضع جميع البيانات الأصغر من العنصر المرجعي في فاصل واحد ، ويتم وضع جميع البيانات أكبر من العنصر المرجعي في فاصل آخر. بعد اكتمال عملية التقسيم ، يكون موضع العنصر المرجعي هو الموضع الذي يجب أن يكون فيه بعد الفرز النهائي.
العودية: اتصل بشكل متكرر بالخوارزميات في الخطوة 1 والخطوة 2 لأول مرة حتى يكون هناك عنصر واحد فقط في جميع الفواصل الزمنية غير المرتبة.
الآن دعنا نتحدث عن طرق التنفيذ المشتركة (لا يتم استخدام خوارزمية في مكانها)
وظيفة QuickSort (arr) {if (arr.length <= 1) return ؛ // إرضاء معيار الرقم الأقرب إلى منتصف الصفيف ، والأرقام الفردية والأرقام حتى تأخذ القيم مختلفة ، لكنني لا أعتقد ذلك. بالطبع ، يمكنك اختيار الرقم الأول أو الأخير كمعيار ، ولا يوجد الكثير من الوصف هنا var pivotindex = math.floor (arr.length/2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] (var i = 0 ؛ i <arr.length ؛ i ++) {console.log ('' + (i + 1) + 'loop of partition Operation:') ؛ {right.push (arr [i]) ؛ console.log ('اليمين:' + (arr [i]))}} // يتم استخدام المشغل المتسابق هنا لربط الفاصل الزمني الأيسر ، المرجع ، والفاصل الزمني الأيمن في صفيف جديد // ثم خطوات واحدة متكررة حتى جميع الفواصل غير المرتبة لها عنصر واحد يسار ، وتراجع الطرف المتكرر (اليسار). Quicksort (يمين)) ؛} var arr = [14 ، 3 ، 15 ، 7 ، 2 ، 76 ، 11] ؛ console.log (Quicksort (ARR)) ؛/** عندما تكون القاعدة 7 ، يتم الحصول على القسم الأول مع اثنين من المجموعتين الفرعيتين على اليسار واليمين [3 ،] 7 [14 ، 15 ، 76 ، 11] ينتهي فرز المجموعة الفرعية اليسرى* مع المرجع كـ 76 ، يتم تقسيم المجموعة الفرعية اليمنى وفرزها للحصول على [14 ، 15 ، 11] [14 ، 11] يتم تقسيمها وتصنيفها إلى ما ورد أعلاه [11] مقسمة إلى القاعدة 11 ، 11 [14]*لم يتبق سوى عنصر واحد في جميع الفواصل الزمنية غير المرتبة ، والنهاية العودية **/من خلال تصحيح الأخطاء ، يمكن الحصول على النتائج.
عيوب:
يتطلب مساحة تخزين إضافية من ω (n) ، والتي هي سيئة مثل الفرز دمج. في بيئة الإنتاج ، مطلوب مساحة ذاكرة إضافية ، مما يؤثر على الأداء.
في الوقت نفسه ، يعتقد الكثير من الناس أن ما سبق هو نوع سريع حقيقي. لذلك ، فيما يلي ، من الضروري التوصية بالفرز السريع للخوارزمية في مكانها
للحصول على معلومات حول خوارزمية في الموقع ، يرجى الرجوع إلى ويكيبيديا. الطلاب الذين هم تحت الحائط يشبهون بايدو.
في مكان
يتم تنفيذ الفرز السريع بشكل عام مع العودية. الشيء الأكثر أهمية هو وظيفة تجزئة التقسيم ، التي تقسم الصفيف إلى جزأين ، واحد أصغر من المحور والآخر أكبر من المحور. تم ذكر المبدأ المحدد أعلاه
الوظيفة QuickSort (arr) {// swap swip swap (arr ، a ، b) {var temp = arr [a] ؛ arr [a] = arr [b] ؛ arr [b] = temp ؛} // partition partition function (arr ، land ، right) {/*** في البداية ، لا تعرف موقع التخزين النهائي ، يمكنك التباطؤ على pivot first* arr [right] ؛/*** عند تخزين العناصر الأصغر من المحور ، فهي بجوار العنصر السابق ، وإلا فإن العنصر المخزن في الفجوة قد يكون أكبر من المحور ، لذلك ، يتم الإعلان عن متغير StoreIndex وتهيئته إلى اليسار لتخزين عناصر أصغر من المحور بجوار بعضها البعض. ام تم تبديل*/swap (arr ، storeindex ، i) ؛ storeindex ++ ؛}} // أخيرًا: تبديل المحور إلى storeindex ، ضع عنصر القياس في تبادل الموضع الصحيح النهائي (arr ، يمين ، storeindex) ؛ عودة storeend ؛ 1) ؛ sort (arr ، storeindex + 1 ، يمين) ؛} الفرز (arr ، 0 ، arr.length - 1) ؛ return arr ؛} console.log (Quicksort ([8 ، 4 ، 90 ، 8 ، 34 ، 67 ، 1 ، 26 ، 17])) ؛تحسين التقسيم
قد يسأل الطلاب المؤكدون هنا ما إذا كان سيكون هناك أداء مختلف للأداء عند اختيار معايير مختلفة. الجواب نعم ، لكن لأنني شخص أمامي ولا أعرف الكثير عن الخوارزمية ، لذلك يتم ترك هذه الحفرة للأشخاص الأقوياء لملءها.
تعقيد
الفرز السريع هو أسرع خوارزمية الفرز ، وتعقيدها الزمني هو o (log n)
في الوضع المتوسط ، يتطلب ترتيب العناصر n (n log n) مقارنات. في أسوأ الحالات ، مطلوب مقارنات (N2).
https://github.com/lyz0106/
ما ورد أعلاه هو طريقة الفرز السريع لتنفيذ JavaScript في المواقع التي قدمها المحرر. آمل أن يكون ذلك مفيدًا للجميع. إذا كان لديك أي أسئلة ، يرجى ترك رسالة لي. سوف يرد المحرر لك في الوقت المناسب. شكرًا جزيلاً على دعمكم لموقع Wulin Network!