ملخص نقاط معرفة جافا حول فرز دلو

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

0. فهارس خوارزمية الفرز الأخرى

//www.vevb.com/article/120879.htm

1. فكرة فرز الجرافة

مثال بسيط:

فرز درجات اختبار اللغة الإنجليزية من 6 أشخاص (1 ~ 10 نقاط). إذا كانت النتيجة [6 ، 5 ، 8 ، 10 ، 10 ، 9] ، فإن فكرة الفرز بالدلاء هي إعداد 10 دلو ، والأرقام هي 1 ~ 10 في التسلسل ، ويتم وضع الدرجات في الدلو المقابل ، مثل 6 نقاط في الدلو رقم 6 ، و 8 نقاط 8 في الدلو رقم 8 ... ثم إخراجها واحدة بنسبة واحدة لترتيب الجرلب (إذا كان هناك ، هذه هي الفكرة الأساسية لفرز دلو.

في الواقع ، هذا مجرد نسخة بسيطة. فقط تخيل ، إذا كان نطاق العناصر الممتدة المراد فرزه كبيرًا نسبيًا ، مثل 10،000 ~ 10،000 ، هل تحتاج إلى 10000 دلو؟ في الواقع ، في هذه الحالة ، لا يتم وضع عنصر واحد دائمًا في دلو ، ولكن يتم وضع عناصر متعددة عدة مرات في دلو. في الواقع ، فإن فرز دلو حقيقي وقائمة التجزئة لهما نفس المبدأ.

في الفرز الفعلي ، عادة ما يتم فرز العناصر الموجودة في كل دلو باستخدام خوارزميات الفرز الأخرى ، لذلك في كثير من الأحيان ، يتم استخدام فرز الجرافة مع خوارزميات الفرز الأخرى.

2. رمز الفرز دلو

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

 دلاء الفئة العامة {private int [] دلاء ؛ int private [] Array ؛ bucketsort العامة (int range ، int [] array) {this.buckets = new int [range] ؛ this.array = صفيف ؛ } /*sorting* / public void sort () {if (Array! = null && array.length> 1) {for (int i = 0 ؛ i <array.length ؛ i ++) {buckets [array [i]] ++ ؛ }}}/*فرز الإخراج*/public void sortout () {// عكس بيانات الإخراج (int i = buckets.length-1 ؛ I> = 0 ؛ }}}}

رمز الاختبار:

 الفئة العامة sorttest {public static void main (string [] args) {testbucketssort () ؛ } private static void testbucketssort () {int [] Array = {5،7،3،5،4،8،6،4،1،2} ؛ BucketSort BS = New BucketSort (10 ، Array) ؛ Bs.Sort () ؛ bs.sortout () ؛ // الإخراج طباعة الفرز}}}

3. خصائص أداء فرز الجرافة

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

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

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

4. فرز دلو سيناريوهات قابلة للتطبيق

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