فكرة "الفرز السريع" بسيطة للغاية ، وتتطلب عملية الفرز بأكملها ثلاث خطوات فقط:
(1) في مجموعة البيانات ، حدد عنصرًا كـ "قاعدة" (محور).
(2) يتم نقل جميع العناصر الأصغر من "المرجع" إلى يسار "المرجع" ؛ يتم نقل جميع العناصر الأكبر من "المرجع" إلى يمين "المرجع".
(3) بالنسبة للمجموعتين الفرعيتين على اليسار واليمين من "خط الأساس" ، كرر الخطوتين الأول والثاني حتى يكون هناك عنصر واحد فقط في جميع المجموعات الفرعية.
على سبيل المثال ، هناك الآن مجموعة بيانات {85 ، 24 ، 63 ، 45 ، 17 ، 31 ، 96 ، 50}. كيف ترسلها؟
في الخطوة الأولى ، حدد العنصر الوسيط 45 كـ "قاعدة". (يمكن تحديد القيمة المرجعية بشكل تعسفي ، ولكن اختيار القيمة الوسيطة أسهل في الفهم.)
والخطوة الثانية هي مقارنة كل عنصر بـ "القاعدة" من أجل تكوين مجموعتين فرعيتين ، واحد هو "أقل من 45" والآخر "أكبر من أو يساوي 45".
والخطوة الثالثة هي تكرار الخطوتين الأولى والثانية للمجموعتين الفرعيتين حتى يكون هناك عنصر واحد فقط في جميع المجموعات الفرعية.
فيما يلي إشارة إلى المعلومات عبر الإنترنت (هنا وهنا) لتنفيذ الخوارزمية أعلاه بلغة JavaScript.
أولاً ، حدد وظيفة Quicksort التي تكون معلماتها صفيفًا.
var QuickSort = function (arr) {} ؛بعد ذلك ، تحقق من عدد العناصر الموجودة في الصفيف ، وإذا كان أقل من أو يساوي 1 ، فسيتم إرجاعه.
var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ }} ؛بعد ذلك ، حدد "Pivot" وفصله عن الصفيف الأصلي ، ثم حدد صفيفتين فارغتين لتخزين مجموعتين فرعيتين من اليسار وواحد يمين.
var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } var pivotindex = math.floor (arr.length / 2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] ؛ var left = [] ؛ var right = [] ؛} ؛بعد ذلك ، ابدأ في عبور الصفيف ، ووضع العناصر أصغر من "القاعدة" في المجموعة الفرعية على اليسار ، والعناصر أكبر من القاعدة في المجموعة الفرعية على اليمين.
var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } var pivotindex = math.floor (arr.length / 2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] ؛ var left = [] ؛ var right = [] ؛ لـ (var i = 0 ؛ i <arr.length ؛ i ++) {if (arr [i] <pivot) {left.push (arr [i]) ؛ } آخر {right.push (arr [i]) ؛ }}} ؛أخيرًا ، كرر هذه العملية بشكل مستمر باستخدام العودية للحصول على الصفيف المرتبة.
var QuickSort = function (arr) {if (arr.length <= 1) {return arr ؛ } var pivotindex = math.floor (arr.length / 2) ؛ var pivot = arr.splice (pivotindex ، 1) [0] ؛ var left = [] ؛ var right = [] ؛ لـ (var i = 0 ؛ i <arr.length ؛ i ++) {if (arr [i] <pivot) {left.push (arr [i]) ؛ } آخر {right.push (arr [i]) ؛ }} إرجاع Quicksort (يسار) .concat ([pivot] ، Quicksort (يمين)) ؛} ؛عند استخدامه ، ما عليك سوى استدعاء QuickSort ().
ما سبق هو شرح مفصل لمثال خوارزمية Quicksort لسلسلة خوارزمية JavaScript التي قدمها المحرر. آمل أن يكون ذلك مفيدًا لك. إذا كان لديك أي أسئلة ، فيرجى ترك رسالة لي وسوف يرد المحرر إليك في الوقت المناسب. شكرا جزيلا لدعمكم لموقع wulin.com!