شرح مفصل لطريقة استخدام الأدوية الجينية لتنفيذ خوارزمية الفرز السريع في جافا

مفهوم خوارزمية الفرز السريع
يعتمد الفرز السريع بشكل عام على التنفيذ العودية. الفكرة هي كما يلي:
1. حدد قيمة مناسبة (القيمة المثالية هي الأفضل ، ولكن القيمة الأولى في الصفيف تستخدم عمومًا في التنفيذ) ، والتي تسمى "Pivot".
2. بناءً على هذه القيمة ، قسّم الصفيف إلى جزأين ، الجزء الأصغر على اليسار والجزء الأكبر على اليمين.
3. من المؤكد أنه بعد هذه الجولة ، يجب أن يكون موضع هذا المحور في الموضع النهائي.
4. كرر العملية أعلاه للبطلين الفرعيين حتى يكون هناك عنصر واحد فقط لكل صفيف.
5. يتم الانتهاء من الفرز.

طريقة التنفيذ الأساسية:

 Quicksort QuickSort static static static (int [] arr) {qsort (arr ، 0 ، arr.length-1) ؛} private static void qsort (int [] arr ، int low ، int high) {if (low <high) {int pivot = partition (arr ، high ، high) ؛ // قسّم الصفيف إلى جزأين QSort (arr ، low ، pivot-1) ؛ // فرز المسجل الفرعي الأيسر QSort (ARR ، PIVOT+1 ، High) ؛ // فرز المسجل الفرعي الأيمن بشكل متكرر}} قسم int ثابت خاص (int [] arr ، int low ، int high) {int pivot = arr [low] ؛ // سجل Pivot بينما (منخفض <عالية) {بينما (low <High && arr [High]> = pivot) -عالية ؛ arr [low] = arr [high] ؛ // Swap Records أصغر من المحور إلى اليسار بينما (منخفض <high ​​&& arr [low] <= pivot) ++ low ؛ arr [high] = arr [low] ؛ // سجلات SWAP أصغر من المحور إلى الطرف الأيمن} // تم الانتهاء من المسح الضوئي ، والمحور موجود في مكانه [low] = pivot ؛ // إرجاع موضع المحور إلى مستوى العودة ؛}

استخدم الأدوية الجينية لتنفيذ خوارزمية الترتيب السريع

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

تم استخدام خوارزمية فرز الصف السريع الأساسي ولم يتم إجراء معالجة التحسين.

رمز المصدر كما يلي:

 استيراد java.util.linkedList ؛ استيراد java.util.list ؛ استيراد java.util.listIterator ؛ استيراد java.util.random ؛ الفئة العامة QuickSort {suppressWarnings ("غير محدد") // تعديل النموذج الأولي للدالة السريعة المذكورة أعلاه بحيث يمكن فرز صفائف من أي نوع كائن. يتم استخدام هذه الوظيفة داخليًا ، وواجهة وظيفة الفرز الخارجية هي Sort (). تتطلب دالة الفرز أن الكائن يجب أن ينفذ الواجهة المماثلة ، والتي يمكن أن توفر الكشف عن نوع وقت الترجمة ، راجع المقالة التالية. Quicksort QuickSort static static (الكائن [] في ، int ، int end) {if (start == end || start == (end-1)) return ؛ الكائن p = في [start] ؛ int a = start +1 ؛ int b = a ؛ لـ (؛ b <end ؛ b ++) {// يجب أن تنفذ صفيف نوع الكائن هذا الواجهة المماثلة بحيث يمكنك استخدام وظيفة المقارنة للمقارنة إذا (((((كائن>) في [b]). المقارنة (p) <0) {if (a == b) {a ++ ؛ متابعة ؛} الكائن temp = in [a] ؛ في [A] = في [B] ؛ في [ب] = درجة الحرارة ؛ A ++ ؛ }} في [start] = in [a-1] ؛ في [A-1] = P ؛ if (a-1> start) {QuickSort (in ، begin ، a) ؛ } if (end-1> a) {QuickSort (in ، a ، end) ؛ } يعود؛ } // استخدم generics لفرز أي صفيف كائن ، يجب على صفيف نوع الكائن تطبيق الواجهة المماثلة الثابتة العامة <t يمتد قابلة للمقارنة <؟ Super t >> void sort (t [] input) {QuickSort (input ، 0 ، input.length) ؛ } // إضافة وظيفة كائنات قائمة الفرز ، راجع وظيفة SORT () لفئة java.util.collections في java public static <t يمتد قابلة للمقارنة <؟ super t >> فرز void (قائمة <T> قائمة) {object [] t = list.toarray () ؛ // تحويل القائمة إلى صفيف Quicksort (t ، 0 ، t.length) ؛ // فرز المصفوفة // بعد اكتمال فرز الصفيف ، اكتب مرة أخرى إلى ListiTiTerator <T> i = list.listiterator () ؛ لـ (int j = 0 ؛ j <t.length ؛ j ++) {i.next () ؛ i.set ((t) t [j]) ؛ }} // لأنه لا يمكن استخدام الأدوية الجيرية في Java ، وأنواع البيانات البدائية (int ، double ، byte ، إلخ) ، يمكنك فقط استخدام آلية التحميل الزائد للوظيفة لفرز هذه المصفوفات البدائية (int [] ، double [] ، byte [] ، إلخ). من أجل مشاركة وظيفة الفرز نفسها ، يتم استخدام آلية النوع الأصلي (autoboxing ، unboxing) لتغليفها في نوع الكائن المقابل ، وتشكيل صفيف كائن جديد ، وفرزه ثم إزالة التكلفة. عيب ذلك هو أنه يتطلب خطوات تحويل إضافية ومساحة إضافية لحفظ الصفيف المغلف. طريقة أخرى هي نسخ رمز الفرز في كل وظيفة محملة. تستخدم وظيفة SORT () في فئة java.util.arrays في واجهة برمجة التطبيقات الرسمية هذه الطريقة ، والتي يمكن رؤيتها من الكود المصدري لفئة المصفوفات. فرز الفراغ الثابت العام (int [] input) {integer [] t = new integer [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ // alsapsulation} Quicksort (t ، 0 ، t.length) ؛ // forting for (int i = 0 ؛ i <input.length ؛ i ++) {input [i] ؛ الإدخال) {double [] t = new double [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {input [i] = t [i] ؛ }} // دالة التحميل الزائد لـ byte [] Array public static void sort (byte [] input) {byte [] t = new byte [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length) ؛ input.length ؛ i ++) {input [i] = t [i] ؛ }} // Short [] وظيفة الحمل الزائد الفراغ الثابتة الثابتة (قصيرة [] إدخال) {Short [] t = new Short [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {input [i] = t [i] ؛ }} // Short [] وظيفة overload public static void sort (char [] input) {character [] t = new حرف [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {input [i] = t [i] ؛ }} // وظيفة الحمل الزائد من عطف [] صفيف الفراغ الثابت العام (float [] input) {float [] t = new float [input.length] ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {t [i] = input [i] ؛ } QuickSort (t ، 0 ، t.length) ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {input [i] = t [i] ؛ }} // الوظيفة الرئيسية لاختبار الفراغ الثابت العام (سلسلة [] args) {// تنتج صفيف int [] يتكون من أرقام عشوائية لاختبار int len ​​= 10 ؛ int [] input = new int [len] ؛ عشوائي R = جديد عشوائي () ؛ System.out.print ("int [] قبل الفرز:") ؛ لـ (int i = 0 ؛ i <input.length ؛ i ++) {input [i] = r.nextint (10*len) ؛ system.out.print (input [i] + "") ؛ } system.out.println () ؛ System.out.print ("int [] بعد الفرز:") ؛ فرز (إدخال) ؛ لـ (int i: input) {system.out.print (i + "") ؛ } system.out.println () ؛ // إنشاء مجموعة من السلاسل لاختبار سلسلة [] s = new string [] {"b" ، "a" ، "e" ، "d" ، "f" ، "c"} ؛ System.out.print ("String [] قبل الفرز:") ؛ لـ (int i = 0 ؛ i <s.length ؛ i ++) {system.out.print (s [i]+"") ؛ } system.out.println () ؛ System.out.print ("String [] بعد الفرز:") ؛ الفرز (s) ؛ لـ (int i = 0 ؛ i <s.length ؛ i ++) {system.out.print (s [i]+"") ؛ } system.out.println () ؛ // إنشاء قائمة من السلاسل لاختبار قائمة <string> l = new LinkedList <String> () ؛ s = new string [] {"b" ، "a" ، "e" ، "d" ، "f" ، "c"} ؛ System.out.print ("LinkedList <string> قبل الفرز:") ؛ لـ (int j = 0 ؛ j <s.length ؛ j ++) {l.add (s [j]) ؛ system.out.print (s [j] + "") ؛ } system.out.println () ؛ فرز (ل) ؛ System.out.print ("LinkedList <string> بعد الفرز:") ؛ لـ (string ts: l) {system.out.print (ts + "") ؛ } system.out.println () ؛ }}

قم بتشغيل اختبار الوظيفة الرئيسي ، ومن الإخراج ، يمكنك أن ترى أن فئة Quicksort تعمل بشكل طبيعي:

 int [] قبل الفرز: 65 48 92 26 3 8 59 21 16 45int [] بعد الفرز: 3 8 16 21 26 45 48 59 65 92String [] قبل الفرز: Baedfc String [] بعد الفرز: ABCDEF LinkedList <string> قبل الفرز: BAEDFC LinkedList <String> بعد الفرز: