مبدأ Java Quicksort ورمز التنفيذ

Quicksort هي خوارزمية فرز شائعة الاستخدام وأكثر كفاءة ، وغالبًا ما يتم ذكرها أثناء عملية المقابلة. دعنا نوضح مبادئها بالتفصيل ونقدم تطبيق إصدار Java.

فكرة فرز سريعة:

يتم تقسيم جزأين مستقلين عن طريق فرز مجموعة عنصر البيانات RN في رحلة واحدة. جزء واحد من الكلمة الرئيسية أصغر من الجزء الآخر. ثم قم بفرز الكلمات الرئيسية للجزأين واحدًا تلو الآخر حتى يكون هناك عنصر مستقل واحد فقط ، ومجموعة العناصر بأكملها بالترتيب.

عملية الفرز السريع - طريقة حفر الثقوب وأرقام التعبئة (هذا اسم حيوي للغاية) ، لمجموعة العناصر R [منخفض ... مرتفع] ، أولاً ، خذ رقمًا (عادةً R [منخفض]) كمرجع و r [منخفض] يعيد ترتيب جميع العناصر كمعيار.

يتم وضع كل من أصغر من R [منخفض] في المقدمة ، يتم وضع كل من أكبر من R [منخفضة] في الخلف ، ثم يتم استخدام R [منخفض] كحدود ، و R [منخفض ... مرتفع] مقسمة إلى مجموعتين فرعيتين ثم مقسمة. حتى انخفاض> = مرتفع.

على سبيل المثال: عملية تنفيذ فرز سريع لـ r = {37 ، 40 ، 38 ، 42 ، 461 ، 5 ، 7 ، 9 ، 12} هي كما يلي (ملاحظة: يبدأ الجدول التالي للعناصر الموضحة أدناه من 0):

ابدأ في تحديد القاعدة الأساسية = 37 ، الجدول أدناه منخفض = 0 ، مرتفع = 8 ، يبدأ من ارتفاع = 8 ، إذا كان r [8] <قاعدة ، اكتب المحتوى في الموضع العالي إلى r [منخفض] ، ثم عالية الموضع فارغ ، منخفض = منخفض +1 ؛

ابدأ بالتحقيق من Low ، نظرًا لأن Low = 1 ، r [low]> base ، اكتب r [low] إلى r [high] ، High = High -1 ؛

تم اكتشاف Low <High ، لذلك لا يزال أول فرز سريع يحتاج إلى المتابعة:

في هذا الوقت منخفض = 1 ، مرتفع = 7 ، لأن r [عالية] <base ، r [عالية] مكتوبة في r [low] ، low = low + 1 ؛

بدء الكشف عن قاعدة منخفضة ، منخفضة = 2 ، r [low]> ، لذلك R [low] مكتوبة إلى r [عالية] ، عالية = عالية 1 ؛

الاستمرار في اكتشاف انخفاض أقل من ارتفاع

في هذا الوقت منخفض = 2 ، مرتفع = 6 ، وبالمثل ، r [عالية] <base ، اكتب r [عالية] إلى r [low] ، low = low+1 ؛

استمر في الكشف عن قاعدة منخفضة ، منخفضة = 3 ، عالية = 6 ، r [منخفض]> ، اكتب r [low] إلى r [عالية] ، عالية = عالية 1 ؛

الاستمرار في اكتشاف أن أدنى مستوى أقل من ارتفاع

في هذا الوقت منخفض = 3 ، مرتفع = 5 ، وبالمثل ، r [high] <base ، اكتب r [عالية] إلى r [low] ، low = low +1 ؛

استمر في التحقيق من منخفض ، منخفض = 4 ، مرتفع = 5 ، لأن r [low]> base ، اكتب r [low] إلى r [عالية] ، عالية = عالية -1 ؛

في هذا الوقت ، يتم اكتشاف منخفض == == 4 ؛

ثم قم بفرز سريع من المتابعات RS1 = {12،9،7،5} و RS2 = {461،42،38،40} حتى يكون هناك عنصر واحد فقط في RSI ، أو بدون عنصر.

(ملاحظة: في النموذج أعلاه ، يمكنك أن ترى أن هناك بعض البيانات المكررة في الفرز (لا توجد بيانات مكررة في البيانات الأصلية). وذلك لأن البيانات الموجودة في هذا الموقع لم يتم مسحها. ننظر إلى بيانات الذاكرة حظر في وقت محدد.

تطبيق Java السريع:

نسخة الكود كما يلي:

isempty الثابتة الخاصة (int [] n) {

إرجاع n == null || n.length == 0 ؛

}

// ///////////////////////////////////////////////////////// ///

/**

* فكرة خوارزمية الفرز السريع - طريقة حفر الثقوب والملء:

*

* @param n array ليتم فرزها

*/

Quicksort Quicksort Quickors (int [] n) {

إذا (isempty (n))

يعود؛

QuickSort (n ، 0 ، n.length - 1) ؛

}

Quicksort Quicksort Quickors (int [] n ، int l ، int h) {

إذا (isempty (n))

يعود؛

if (l <h) {

int pivot = partition (n ، l ، h) ؛

Quicksort (n ، l ، pivot - 1) ؛

Quicksort (n ، pivot + 1 ، h) ؛

}

}

Private Static Int Partition (int [] n ، int start ، int int) {

int tmp = n [start] ؛

بينما (ابدأ <end) {

بينما (n [end]> = tmp && start <end)

نهاية--؛

إذا (ابدأ <end) {

n [start ++] = n [end] ؛

}

بينما (n [ابدأ] <tmp && ابدأ <end)

ابدأ ++ ؛

إذا (ابدأ <end) {

n [end--] = n [start] ؛

}

}

n [start] = tmp ؛

ابدأ العودة ؛

}

هناك وظيفة مثل هذه في الكود:

نسخة الكود كما يلي:

QuicksorStswap الفراغ العام (int [] n ، int l ، int h)

يمكن تنفيذ هذه الوظيفة لفرز عناصر البيانات في العنصر المحدد بين مواضع L و H محددة.

هذا كل شيء للفرز السريع.