تبادل الخبرات في تنفيذ فرز جافا

1. نظرة عامة

يعد الفرز والبحث مشكلتين أساسيتين للغاية في البرمجة، وهناك العديد من الخوارزميات الكلاسيكية المستخدمة لحل هذين النوعين من المشاكل. تجري هذه المقالة بشكل أساسي مناقشة أساسية حول تنفيذ خوارزميات الفرز في Java، على أمل أن تكون بمثابة نقطة بداية. دور. قبل ذلك، اسمحوا لي أولاً أن أطرح عليك بعض الأسئلة: هل يمكنك كتابة فرز سريع صحيح؟ تحت أي ظروف يكون الفرز السريع سريعًا حقًا؟ هل قائمة الانتظار السريعة الخاصة بك سريعة بما فيه الكفاية؟ هل يمكن تحسينها بشكل أكبر؟ مع هذه الأسئلة، دعونا نلقي نظرة على كيفية تنفيذ الفرز السريع في jre7.

فئة تنفيذ الفرز في Jre7 هي DualPivotQuickSort.java. بالمقارنة مع jre6، هناك بعض التغييرات، بشكل رئيسي في مكانين: أحدهما هو تنفيذ فرز الإدراج، والآخر هو أن المحور في تنفيذ QuickSort يتغير من واحد إلى اثنين . لنأخذ مصفوفة من النوع int كمثال. هناك طريقة أساسية لفرز التنفيذ في هذه الفئة. النموذج الأولي لهذه الطريقة هو

انسخ رمز الكود كما يلي:

فرز باطل (int[] a، int يسار، int يمين، منطقي في أقصى اليسار)

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

المصفوفة: [2، 4، 8، 5، 6، 3، 0، -3، 9] يمكن تقسيمها إلى ثلاث فترات (2، 4، 8){5، 6<3، 0، -3، 9>

بالنسبة للفاصل الزمني ()، اليسار = 0، اليمين = 2، أقصى اليسار = صحيح

بالنسبة للفاصل الزمني {}، يسار = 3، يمين = 4، أقصى اليسار = خطأ، يمكن الحصول على المعلمات المقابلة للفاصل الزمني <> بنفس الطريقة.

عندما يكون طول الفاصل الزمني أقل من 47، ستستخدم هذه الطريقة الفرز بالإدراج؛ وإلا سيتم استخدام الفرز السريع.

2. تنفيذ نوع الإدراج

عندما يكون أقصى اليسار صحيحًا، فإنه سيستخدم فرز الإدراج التقليدي، ويكون الكود بسيطًا نسبيًا، وتشبه العملية عملية التقاط البطاقات وإدخالها عند لعب الورق:

انسخ رمز الكود كما يلي:

لـ (int i = left, j = i; i < right; j = ++i) {

int ai = a[i + 1];

بينما (آي <أ[ي]) {

أ[ي + 1] = أ[ي];

إذا (ي-- == اليسار) {

استراحة؛

}

}

أ[ي + 1] = منظمة العفو الدولية؛

}

رمز فرز الإدراج التقليدي

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

انسخ رمز الكود كما يلي:

for (int k = left; ++left <= right; k = ++left) {

int a1 = a[k], a2 = a[left];

إذا (أ1 <أ2) {

a2 = a1; a1 = a[يسار];

}

بينما (a1 < أ[--ك]) {

أ[ك + 2] = أ[ك]؛

}

أ[++ك + 1] = a1;

بينما (a2 <أ[--ك]) {

أ[ك + 1] = أ[ك]؛

}

أ[ك + 1] = أ2؛

}

الآن هناك سؤال: لماذا يستخدم النطاق الموجود في أقصى اليسار فرز الإدراج التقليدي، بينما يستخدم النطاق الآخر فرز الإدراج الزوجي؟ ما هي المشاكل التي ستنشأ إذا استبدلنا رمز فرز الإدراج التقليدي برمز فرز الإدراج الزوجي أعلاه؟ آمل أن تجيبوا جميعا على ذلك بنفسك. . .

3. تنفيذ الفرز السريع

تم أيضًا تحسين الفرز السريع في Jre7. يحدد الفرز السريع التقليدي محورًا (تتمثل طرق تحديد المحور jre6 في تحديد العناصر الموجودة في المواضع الموجودة في أقصى اليسار والوسط وأقصى اليمين في المصفوفة، وترتيب العناصر ذات القيم الوسطى على أنها المحور)، ثم اجتاز من كلا الطرفين إلى المنتصف، ثم ضع الكائنات التي تمت مواجهتها أثناء الاجتياز الأيسر يتم تبادل القيمة الأكبر من المحور مع القيمة الأقل من أو تساوي المحور الذي تم مواجهته في الاجتياز على اليمين، وعندما يواجه الاجتياز، يتم إدراج قيمة المحور، وهذا يجعل القيم الموجودة على يسار المحور أقل من أو يساوي المحور، والقيمة الموجودة على يمين المحور أكبر من المحور؛ تابع بعد ذلك، استخدم العودية لفرز الجانبين الأيسر والأيمن على التوالي.

من خلال التحليل أعلاه، يمكننا أن نرى ما يلي: كل خطوة من خطوات فرز الإدراج هي جعل نطاق فرعي من المصفوفة مرتبة تمامًا، وجوهر كل دورة هو توسيع هذا النطاق الفرعي بشكل مستمر، لذلك يمكننا أن نرى أن اتجاه التحسين هو جعل كل اجتياز حلقة يجعل النطاق الفرعي يتوسع في أسرع وقت ممكن، لذلك تم تحسين التحسين المذكور أعلاه لإدراج عنصر واحد لكل اجتياز لإدراج عنصرين في وقت واحد. وبالطبع سيتساءل أحدهم بالتأكيد، لماذا لا نجعل هذا الرقم أكبر؟ على سبيل المثال، يتم إدراج 5 أو 10 في كل مرة يتم اجتيازها. . . من الواضح أن هذا غير ممكن، والحالة القصوى هي إدراج عناصر n (n هو طول المصفوفة) في كل مرة يتم اجتيازها. . . أما لماذا فيمكن للجميع الإجابة عن أنفسهم.

بالنسبة للفرز السريع، فإن ما تفعله كل عملية عودية هو جعل النطاقات الفرعية التي تحتاج إلى الفرز أكثر ترتيبًا، وليس مرتبة تمامًا؛ لذلك بالنسبة للفرز السريع، يعتمد أدائه على كيفية قيام كل عملية متكررة بفرز النطاق الفرعي بشكل أكثر تنظيمًا إن العامل المحدد لدرجة ترتيب الفترة الفرعية هو بالطبع عدد التكرارات. مفتاح الفرز السريع لجعل الفترة الفرعية منظمة نسبيًا هو المحور، لذا يجب أن يكون اتجاه التحسين لدينا هو المحور أيضًا، ثم قم بزيادة عدد المحاور، ويمكننا أن نجد أن زيادة عدد المحاور لا يؤثر على عدد المحاور سيكون لها تأثير كبير، وفي بعض الأحيان يمكن أن تقلل من عدد التكرارات. سؤال مشابه لإدراج الفرز هو، كم عدد المحاور التي يجب زيادتها؟ من الواضح أن قيمة المحور لا يمكن أن تكون كبيرة جدًا، تذكر أن أي تحسين له تكلفة، وتكلفة زيادة المحور مخفية في عملية تبادل موضع العناصر في كل مرة. يبدو أن Guanzi قد تم بيعه كثيرًا. . . دعونا نلقي نظرة على كيفية تنفيذ الفرز السريع عندما تكون القيمة المحورية 2. في الواقع ليس من الصعب فهم عملية تنفيذها:

1. حدد أولاً محورين. تتمثل طريقة الاختيار المحوري في تقسيم المصفوفة إلى ستة أجزاء متساوية الطول. يتم فصل هذه الأجزاء الستة في الواقع عن طريق 5 عناصر الرابع، كمحور 1 ومحور 2 على التوالي؛

2. بعد تحديد المحور، قم بالاجتياز من الأطراف اليسرى واليمنى إلى المنتصف، شرط التوقف للاجتياز الأيسر هو مواجهة قيمة أكبر من أو تساوي المحور1، ووضع علامة على هذا الموضع على أنه أقل من شرط التوقف لليمين الاجتياز هو مواجهة قيمة أقل من أو تساوي قيمة Pivot2 ووضع علامة على هذا الموضع على أنه رائع

3. ثم قم بالاجتياز للخلف من الموضع الأقل الذي يتم تمثيله بالرمز k. سوف تواجه المواقف التالية:

أ. إذا كانت قيمة الموضع k أصغر من المحور 1، فقم بتبديل قيم الموضع k والموضع الأصغر، وأضف 1 إلى القيمة الأقل؛ وهذا سيجعل القيم على يسار موضع أقل أصغر من Pivot1، والقيم بين الموضع الأقل والموضع k ستكون القيمة أكبر من أو تساوي Pivot1

ب. إذا كانت القيمة عند الموضع k أكبر من Pivot2، فانتقل من الموضع الكبير إلى اليسار. شرط التوقف للاجتياز هو مواجهة قيمة أقل من Pivot2 أو تساويها. إذا كانت هذه القيمة أقل من Pivot1، فاكتب هذه القيمة إلى الموضع الأقل، واكتب القيمة في الموضع الأقل، تتم كتابة القيمة كموضع k، ويتم كتابة قيمة الموضع k كموضع رائع، وأخيرًا أقل ++، أضف هذه القيمة لتكون أكبر من أو تساوي Pivot1، استبدل موضع k والموضع الكبير، ثم عظيم-

4. بعد الانتهاء من العملية المذكورة أعلاه، يتم تقسيم الفاصل الزمني الفرعي المصنف إلى ثلاثة أجزاء (<pivot1, Pivot1<=&&<=pivot2,>pivot2)، وأخيرًا، يتم استخدام التكرار لهذه الأجزاء الثلاثة.

انسخ رمز الكود كما يلي:

/*

*التقسيم:

*

* الجزء الأيسر الجزء الأوسط الجزء الأيمن

* +------------------------------------------------ ---------------+

* | < المحور 1 |. المحور 1 <= المحور 2 |

* +------------------------------------------------ ---------------+

* ^ ^ ^

* |

* أقل ك عظيم

*

* الثوابت:

*

* الكل في (يسار، أقل) <Pivot1

* Pivot1 <= الكل في [أقل، ك) <= Pivot2

* الكل في (عظيم، يمين)> Pivot2

*

* المؤشر k هو الفهرس الأول لـ ?-part.

*/

المحتوى الأساسي لتنفيذ الفرز في Jre7 هو كما هو مذكور أعلاه للحصول على تفاصيل محددة، يرجى الرجوع إلى الكود الموجود في الفئة المقابلة. إذا وجدت أي أخطاء أو أوجه قصور، فيرجى تصحيحها.