مبدأ
من المحتمل أن يكون فرز الفقاعات خوارزمية يمكن لجميع المبرمجين استخدامها وهي أيضًا واحدة من أكثر الخوارزميات المألوفة.
أفكارها ليست معقدة:
لنفترض أن صفيف ARR [] تم فرزه الآن ، وله عناصر n.
1. إذا ن = 1: من الواضح ، ليست هناك حاجة إلى الانتظار. (في الواقع ، يبدو أن هذه المناقشة غير ضرورية)
2. إذا n> 1:
(1) نبدأ بالعنصر الأول ومقارنة كل عنصرين مجاورين. إذا كان العنصر السابق أكبر من العنصر التالي ، فسيتم بالتأكيد تصنيف الأول في النتيجة النهائية. لذلك ، نتبادل هذين العنصرين. ثم قارن العنصرين المجاورة التاليين. وبهذه الطريقة ، حتى تتم مقارنة زوج العناصر الأخير ، يتم الانتهاء من الجولة الأولى من الفرز. من المؤكد أن العنصر الأخير يجب أن يكون الأكبر في الصفيف (لأنه يتم وضع العنصر الكبير نسبيًا في الخلف في كل مرة).
(2) كرر العملية أعلاه ، هذه المرة لسنا بحاجة إلى النظر في آخر عملية لأنها مرتبة بالفعل.
(3) لذلك حتى يتبقى عنصر واحد فقط ، يجب أن يكون العنصر هو الأصغر ، ثم يمكن أن ينتهي فرزنا. على ما يبدو ، تم تنفيذ N-1 الفرز.
في العملية أعلاه ، في كل مرة (أو "العجلة" ، سوف يطفو الرقم ببطء من موضع معين إلى الموضع النهائي (ارسم مخططًا تخطيطيًا ورسم المصفوفة رأسياً) ، تمامًا مثل الفقاعات ، لذلك يطلق عليه "طريقة فرز الفقاعات".
تنفيذ الكود:
الفئة العامة bubblesort {public static void main (string [] args) {int score [] = {67 ، 69 ، 75 ، 87 ، 89 ، 90 ، 99 ، 100} ؛ لـ (int i = 0 ؛ i <score.length -1 ؛ i ++) {// لا تطلب فقط n -1 لترتيب (int j = 0 ؛ j <score.length -i -1 ؛ j ++) {// فرز درجة الفاصل الزمني الحالي [0 ...... length -i -1] في وقت لاحق int temp = score [j] ؛ النتيجة [j] = النتيجة [j + 1] ؛ النتيجة [j + 1] = temp ؛ }} system.out.print ("th" + (i + 1) + "نتيجة فرز التسلسل:") ؛ لـ (int a = 0 ؛ a <score.length ؛ a ++) {system.out.print (score [a]+"/t") ؛ } system.out.println ("") ؛ } system.out.print ("نتيجة الفرز النهائي:") ؛ لـ (int a = 0 ؛ a <score.length ؛ a ++) {system.out.print (score [a]+"/t") ؛ }}}
أداء الخوارزمية/التعقيد
نتجاهل الوقت الذي يتم فيه زيادة وتهيئة متغيرات الحلقة تلقائيًا. أول تحليل عدد مقارنات الخوارزمية. من السهل أن نرى أن فرز الفقاعة أعلاه دون أي تحسين سيتم تنفيذه في جولات N-1 بغض النظر عن بيانات الإدخال ، وعدد المرات التي يجب مقارنتها في كل جولة من الفرز من N-1 إلى 0. ثم ، العدد الإجمالي للمقارنات هو (N-1)+(N-2)+... (بما أنني لا أعرف كيفية صنع المربعات هنا ، هنا ، أستخدم n^2 لتمثيل المربعات ، نفس الشيء أدناه)
دعونا نلقي نظرة على عدد المهام. تشير المهمة هنا إلى عملية التبادل. بالنسبة للرمز أعلاه ، فإن 1 تبادل يساوي ثلاث مهام. نظرًا لأنه ليس في كل مرة يكون من الضروري تبادل ، فإن عدد عمليات المهمة مرتبط ببيانات الإدخال. في أفضل الحالة ، يكون ذلك ، عندما يكون الطلب في البداية ، عدد المهام هو 0. في أسوأ الحالات ، يكون عدد المهام (N-1) n/2. على افتراض أن بيانات الإدخال هي توزيع متوسط (أو "عشوائي تمامًا") ، ثم حوالي نصف عدد البورصات. من النتائج المذكورة أعلاه ، يمكننا الحصول على متوسط الحالة ، مع عدد المهام 3/2 * (n^2)/2 = 3/4 * (n^2).
باختصار ، على أي حال ، فإن تعقيد مساحة فرز الفقاعات (مساحة إضافية) هو دائمًا O (1).
يحسن
يتم عرض تعقيد الوقت الأمثل عندما يتم طلب البيانات بالكامل ، وهو O (N). في حالات أخرى ، يكون دائمًا O (n^2). لذلك ، تعمل الخوارزمية بشكل أفضل عندما يتم طلب البيانات بشكل أساسي.
ومع ذلك ، كيف يمكن للرمز أعلاه أن يكون التعقيد o (n)؟ في الواقع ، لأن ما سبق يركز على الأفكار الأساسية ، فهي مجرد أبسط حالة. لجعل الخوارزمية لها تعقيد O (n) في أفضل حالة ، يجب إجراء بعض التحسينات. الرمز المحسن هو:
publesort الفراغ الثابت العام (int [] arr) {int temp = 0 ؛ مبادلة منطقية لـ (int i = arr.length -1 ؛ i> 0 ؛ -i) {// يجب أن يكون طول كل نوع المبادلة = false ؛ لـ (int j = 0 ؛ j <i ؛ ++ j) {// من العنصر الأول إلى العنصر i-th if (arr [j]> arr [j +1]) {temp = arr [j] ؛ arr [j] = arr [j + 1] ؛ arr [j + 1] = temp ؛ مبادلة = صواب ؛ }} // loop j if (swap == false) {break ؛ }} // loop i} // method bubblesortفي الواقع ، نظرًا لأن فرز الفقاعات بالكاد يستخدم في حالة كميات كبيرة من البيانات ، فإن المتغيرات المنطقية المضافة عند استخدام البيانات الصغيرة ستؤدي فعليًا إلى إضافات إضافية. لذلك أنا شخصياً أعتقد أن الخوارزمية المحسنة أعلاه هي نظرية بحتة فقط. عادة ، فقط اكتب واحدة من خلال فرز الفقاعات.
خوارزمية الاستقرار
من السهل أن نرى أنه عندما تكون العناصر المجاورة متساوية ، فإننا لا نحتاج إلى تبديل مواقفها ، لذلك يعد نوع الفقاعة نوعًا مستقرًا.
خوارزمية سيناريوهات قابلة للتطبيق
فكرة فرز الفقاعات بسيطة والرمز بسيط ، وهو مناسب بشكل خاص لفرز البيانات الصغيرة. ومع ذلك ، نظرًا للتعقيد العالي للخوارزمية ، فإنه غير مناسب للاستخدام عندما يكون حجم البيانات كبيرًا. إذا كان يجب عليك استخدامه عندما يكون هناك المزيد من البيانات ، فمن الأفضل تحسين الخوارزمية ، مثل اختيار طريقة الفرز.