الأفكار الأساسية
تم تطوير RadixSort استنادًا إلى فرز الجرافات ، وكلا الفرزان هو تطبيقات متقدمة لتخصيص الفرز. الفكرة الأساسية للتوزيعات: لا تتطلب عملية الفرز مقارنة الكلمات الرئيسية ، ولكنها تنفذ الفرز من خلال عمليات "التوزيع" و "جمع". يمكن أن يصل تعقيد الوقت إلى ترتيب خطي: O (N).
فرز Cardinality هو خوارزمية فرز مستقرة ، ولكن لها قيود معينة:
1. يمكن تحلل الكلمات الرئيسية.
2. عدد الكلمات الرئيسية المسجلة أصغر ، وهو أفضل إذا كانت كثيفة. 3. إذا كان الرقم ، فمن الأفضل أن تكون غير موقعة ، وإلا فسيتم زيادة تعقيد التعيين المقابل. يمكنك أولا فرزها بشكل منفصل.
دعنا نلقي نظرة على فرز الجرافة (RadixSort).
يسمى فرز دلو أيضًا فرز الصندوق (Binsort). فكرتها الأساسية هي إعداد العديد من الجرافات ، ومسح السجلات المراد فرزها R [0] ، R [1] ، ... ، R [N-1] ، تحميل جميع السجلات مع الكلمات الرئيسية في نطاق معين في دلو KTH (مخصص) ، ثم توصيل رؤوس وذيل كل دلو غير فارغ بالتسلسل (جمع) وفقًا لرقم التتابع.
على سبيل المثال ، لفرز 52 أوراق لعب من خلال النقاط A <2 <... <j <q <k ، يجب تعيين 13 "دلاء". عند الفرز ، يتم وضع كل بطاقة في الدلو المقابل بواسطة نقاط ، ثم يتم توصيل الدلاء بالتسلسل للحصول على مجموعة من البطاقات مرتبة بترتيب تدريجي للنقاط.
في فرز الجرافة ، يعتمد عدد الدلاء على نطاق القيمة للكلمة الرئيسية. لذلك ، يتطلب فرز الجرافة أن يكون نوع الكلمة الرئيسية محدودًا ، وإلا فقد تكون هناك حاجة إلى دلو غير محدود.
بشكل عام ، لا يمكن التنبؤ بعدد السجلات ذات الكلمات الرئيسية نفسها في كل دلو ، لذلك يجب تصميم نوع الجرافة كقائمة مرتبطة.
للتأكد من أن الفرز مستقر ، يجب إجراء الاتصالات أثناء عملية التعبئة والتجميع وفقًا لمبدأ الأول في الأول.
بالنسبة لفرز الجرافة ، يكون وقت عملية التخصيص هو o (n) ؛ وقت عملية التجميع هو O (M) (يتم استخدام قائمة مرتبطة لتخزين المدخلات المراد فرزها) أو O (M+N). لذلك ، فإن وقت فرز الجرافة هو O (M+N). إذا كان ترتيب عدد الدلاء M هو O (n) ، فإن وقت فرز الجرافة خطي ، أي O (n).
معظم التعقيد الزمني لخوارزميات الفرز الرئيسية المذكورة أعلاه هو O (N2) ، وبعض خوارزميات الفرز هي O (nlogn). لكن فرز البرميل يمكن أن يحقق التعقيد الزمني لـ O (N). ومع ذلك ، فإن عيوب فرز الجرافة هي: أولاً وقبل كل شيء ، تعقيد الفضاء مرتفع نسبيًا ويحتاج النفقات العامة الإضافية. يحتوي الفرز على صفيفان من الفضاء العلوي ، أحدهما يخزن الصفيف المراد فرزه ، والآخر هو ما يسمى الجرافة. على سبيل المثال ، تكون القيمة المراد فرزها من 0 إلى M-1 ، ثم تتطلب الدلاء M ، وتتطلب مجموعة الجرافة هذه مساحة على الأقل. ثانياً ، يجب أن تكون العناصر المراد فرزها ضمن نطاق معين ، إلخ.
يعد فرز Cardinality تحسنًا في فرز الجرافات ، مما يجعل "فرز الجرافات" مناسبًا لمجموعات أكبر من قيم العناصر بدلاً من تحسين الأداء.
دعنا نستخدم مثال أوراق اللعب لتوضيح. تتكون البطاقة من كلمات رئيسية: بدلة (peach <heart <mei <square) + القيمة الاسمية (a <2 <3 <4 <... <k). إذا تم تحديد حجم البطاقة بواسطة الدعوى أولاً ، ويتم تحديد بطاقات نفس الدعوى بواسطة الرقم. لدينا خوارزميات لحل هذه المشكلة.
وهذا هو ، إذا كانت البدلات مختلفة ، بغض النظر عن القيمة الاسمية ، فإن البطاقة التي لديها لون بدلة منخفضة أصغر من لون البدلة بلون بدلة أعلى. فقط في نفس لون الدعوى ، يتم تحديد علاقة الحجم حسب حجم القيمة الاسمية. هذا هو ترتيب رموز المفاتيح المتعددة.
للحصول على نتائج الفرز ، نناقش طريقتين للفرز.
الطريقة 1: فرز الدعاوى والألوان أولاً وتقسيمها إلى 4 مجموعات ، وهي مجموعة زهر البرقوق ، ومجموعة مربعة ، ومجموعة القلب الأحمر ، ومجموعة القلب الأسود. ثم قم بفرز كل مجموعة حسب القيمة الاسمية ، وأخيراً ، قم بتوصيل المجموعات الأربع معًا.
الطريقة 2: أولاً ، أعط 13 مجموعة أرقام (رقم 2 ، 3 ، ... ، أ) وفقًا لما 13 قيم الوجه ، ضع البطاقات في مجموعات الأرقام المقابلة بالترتيب لقيم الوجه ، وقم بتقسيمها إلى 13 أكوامًا. بعد ذلك ، أعط 4 مجموعات ترقيم (أزهار البرقوق ، المربعات ، القلوب الحمراء ، القلوب السوداء) ، قم بإخراج البطاقات في المجموعة 2 ووضعها في مجموعة الألوان المقابلة ، ثم قم بإخراج البطاقات في المجموعة 3 ووضعها في مجموعة الألوان المقابلة ، ... وبهذه الطريقة ، يتم طلب جميع مجموعات الألوان الأربعة وفقًا للقيمة الاسمية ، ثم توصيل مجموعات الألوان الأربعة بالسلسلة.
يتم فرز فرز التعليمات البرمجية متعددة المفاتيح بالترتيب من رمز المفتاح الرئيسي إلى رمز المفتاح الثاني أو من المفتاح الثاني إلى رمز المفتاح الرئيسي ، ويتم تقسيمه إلى طريقتين:
أهم طريقة أولوية بت (معظمها issignaNtDigitFirst) ، يشار إليها باسم طريقة MSD:
1) الفرز الأول وتجميعها بواسطة K1 ، يقسم التسلسل إلى عدة متسلسلات. في سجلات نفس المجموعة من التسلسل ، تكون الرموز الرئيسية K1 متساوية.
2) ثم فرز كل مجموعة إلى مجموعات فرعية بواسطة K2. بعد ذلك ، استمر في فرز رموز المفاتيح التالية بهذه الطريقة حتى يتم فرز كل مجموعة فرعية بواسطة رمز المفتاح الثانوي KD.
3) ثم قم بتوصيل المجموعات للحصول على تسلسل مرتبة. الطريقة التي تم تقديمها في بطاقات الفرز بواسطة الدعاوى وقيم الوجه هي طريقة MSD.
الطريقة الأقل أهمية ، يشار إليها باسم طريقة LSD:
1) ابدأ الفرز من KD ، ثم فرز KD-1 ، مع التكرار بدوره حتى يتم تقسيمه إلى أصغر بعدًا وفقًا لـ K1.
2) أخيرًا ، قم بتوصيل كل التسلسل الفرعي للحصول على تسلسل مرتبة. الطريقة الثانية التي تم تقديمها في بطاقات الفرز حسب الدعوى والقيمة الاسمية هي طريقة LSD.
يمكن اعتبار كلمة رئيسية واحدة من نوع الرقم أو الحرف كلمة متعددة المفاتيح تتكون من أرقام متعددة أو أحرف متعددة. في هذا الوقت ، يمكن استخدام طريقة "التخصيص" لفرزها. تسمى هذه العملية طريقة فرز Cardinality ، حيث يسمى عدد القيم المحتملة لكل رقم أو حرف. على سبيل المثال ، تكون قاعدة بدلات اللعب هي 4 وقاعدة القيمة الاسمية هي 13. عند فرز أوراق اللعب ، يمكنك تنظيمها حسب الأسلوب أولاً أو بالقيمة الاسمية أولاً. عند الفرز وفقًا للألوان ، قم بتقسيمه أولاً إلى 4 أكوام (توزيعات) بترتيب أحمر ، أسود ، مربع وزهور ، ثم تكدسها معًا (جمع) بالترتيب ، ثم تقسمها إلى 13 مكدسات (توزيعات) بترتيب القيمة الاسمية ، ثم تكدسها معًا (جمع) في هذا الترتيب. وبهذه الطريقة ، يمكن للتخصيص والتجميع الثانوي ترتيب أوراق اللعب بطريقة منظمة.
أثناء عملية "التخصيص" ، يجب ضمان استقرار الفرز.
تتمثل فكرة فرز CADRINALITY في دلو كل مجموعة من الكلمات الرئيسية في البيانات المراد فرزها بالتسلسل. على سبيل المثال ، التسلسل التالي المراد فرزه:
135 ، 242 ، 192 ، 93 ، 345 ، 11 ، 24 ، 19
نقسم الفردية ، عشرة ومئات من الأرقام من كل قيمة إلى ثلاث كلمات رئيسية ، على سبيل المثال:
135-> K1 (أرقام مفردة) = 5 ، K2 (عشرة أرقام) = 3 ، K3 (مائة أرقام) = 1.
ثم ابدأ من أدنى عدد واحد (بدءًا من الكلمة الرئيسية الأخيرة) ، يتم تخصيص جميع الكلمات الرئيسية K1 لجميع البيانات (لأن كل رقم هو 0-9 ، وبالتالي فإن حجم الجرافة هو 10) ، ثم إخراج البيانات في الدلو بالتسلسل للحصول على التسلسل التالي.
(11) ، (242 ، 192) ، (93) ، (24) ، (135 ، 345) ، (19) (فرز بدءًا من أكثر الكلمة الرئيسية ، متجاهلاً مائة وعشرة أرقام ، وتخصيص الأرقام على الأرقام المفردة)
ثم يتم تخصيص التسلسل أعلاه لـ K2 ، وتسلسل الإخراج هو:
(11 ، 19) ، (24) ، (135) ، (242 ، 345) ، (192 ، 93) (راجع أكثر الكلمة الرئيسية لفرز الكلمة الرئيسية الثانية ، وتجاهل الأرقام المئة والفردية ، وتخصيصها وفقًا للرقم على الأرقام العشرة)
أخيرًا ، لتخصيص دلو K3 ، يكون تسلسل الإخراج هو:
(011 ، 019 ، 024 ، 093) ، (135 ، 192) ، (242) ، (345) (راجع الكلمة الرئيسية الثانية لفرز أعلى الكلمة الرئيسية ، وتجاهل الأرقام العشرة والفردية ، وتخصيصها وفقًا للأرقام على المائة رقم)
الفرز مكتمل.
تنفيذ جافا
public void radixsort () {int max = array [0] ؛ لـ (int i = 0 ؛ i <array.length ؛ i ++) {// ابحث عن القيمة القصوى في الصفيف if (array [i]> max) {max = array [i] ؛ }} int keysnum = 0 ؛ . Keysnum ++ ؛ } قائمة <ArrayList <Integer>> buckets = new ArrayList <ArrayList <Integer >> () ؛ لـ (int i = 0 ؛ i <10 ؛ i ++) {// الرقم المحتمل لكل رقم هو 0 ~ 9 ، لذلك قم بتعيين 10 دلاء. // يتكون الدلو من arraylist <integer>} لـ (int i = 0 ؛ i <keysnum ؛ i ++) {// ابدأ بأحدث كلمة رئيسية ، قم بتعيينها وفقًا للكلمات الرئيسية بدورها (int j = 0 ؛ j <arry.length ؛ j ++) مثل 258. الآن تحتاج إلى إخراج الرقم على الأرقام العشرة ، 258 ٪ 100 = 58،58/10 = 5 int مفتاح = صفيف [j] ٪ (int) math.pow (10 ، i+1)/(int) math.pow (10 ، i) ؛ buckets.get (key) .add (Array [J]) ؛ // ضع هذا العنصر في دلو مع مفتاح الكلمة الرئيسية} // بعد تخصيص ، انسخ العناصر الموجودة في الدلو إلى عداد الصفيف int = 0 ؛ // element counter for (int j = 0 ؛ j <10 ؛ j ++) {ArrayList <integer> bucket = buckets.get (j) ؛ // دلو مع الكلمة الرئيسية J بينما (bucket.size ()> 0) {array [counter ++] = bucket.remove (0) ؛ // انسخ العنصر الأول في الدلو إلى الصفيف وإزالة}} system.out.print ("Thread"+(i+1)+"sort:") ؛ عرض()؛ }}نتائج الطباعة هي كما يلي:
تحليل الخوارزمية
للوهلة الأولى ، يبدو أن كفاءة التنفيذ في فرز Cardinality جيد ومن غير المعقول أن كل ما عليك فعله هو نسخ عناصر البيانات الأصلية من الصفيف إلى القائمة المرتبطة ثم نسخها مرة أخرى. إذا كان هناك 10 عناصر بيانات ، فهناك 20 نسخة متماثلة ، تكرار العملية لكل بت. على افتراض أن الأرقام المكونة من 5 أرقام يتم فرزها ، 20*5 = 100 نسخة مطلوبة. إذا كان هناك 100 عنصر بيانات ، فهناك 200*5 = 1000 نسخة. يتناسب عدد النسخ مع عدد عناصر البيانات ، أي O (N). هذه هي خوارزمية الفرز الأكثر كفاءة التي رأيناها.
لسوء الحظ ، كلما زاد عدد عناصر البيانات ، هناك حاجة إلى كلمات رئيسية أطول. إذا تم زيادة عناصر البيانات بمقدار 10 مرات ، فيجب إضافة الكلمة الرئيسية بواسطة واحدة (جولة أخرى من الفرز). يتناسب عدد النسخ وعدد عناصر البيانات مع طول الكلمة الرئيسية ، ويمكن اعتبار أن طول الكلمة الرئيسية هو لوغاريتم N. لذلك ، في معظم الحالات ، يتم عكس كفاءة تنفيذ الفرز الكاردينال إلى O (N*logn) ، والتي هي تقريبًا مثل الفرز السريع.
لخص
ما سبق هو المحتوى الكامل لهذه المقالة حول مقدمة فرز Cardinality وتنفيذ لغة Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها.