المبدأ: قارن عنصرين مجاورتين وعناصر التبادل مع قيم كبيرة إلى الطرف الأيمن.
الفكرة: قارن رقمين مجازين في التسلسل ، ضع العشرية في المقدمة والأعداد الكبيرة في الخلف. هذا هو ، في الرحلة الأولى: قارن أولاً الرقمين الأول والثاني ، وضع العشري من قبل والأعداد الكبيرة بعد. ثم قارن الرقم الثاني والرقم الثالث ، وضع العشري قبل وبعد الرقم الكبير ، استمر في ذلك حتى تتم مقارنة الرقمين الأخيرين ، ضع العشرية قبل وبعد الرقم الكبير. كرر الخطوة الأولى حتى يكتمل كل الفرز.
على سبيل المثال: لفرز الصفيف: int [] arr = {6،3،8،2،9،1} ؛
الترتيب الأول:
النوع الأول: 6 و 3 مقارنة ، 6 أكبر من 3 ، وضع المبادلة: 368291
النوع الثاني: 6 و 8 مقارنة ، 6 أقل من 8 ، لا يوجد موضع تبادل: 368291
الترتيب الثالث: 8 و 2 مقارنة ، 8 أكبر من 2 ، وضع المبادلة: 362891
الطلب الرابع: 8 و 9 مقارنة ، 8 أقل من 9 ، لا يوجد موضع تبادل: 362891
الترتيب الخامس: 9 و 1 مقارنة: 9 أكبر من 1 ، وضع المبادلة: 362819
تمت مقارنة الرحلة الأولى في إجمالي 5 مرات ، فرز النتائج: 362819
---------------------------------------------------------------
الترتيب الثاني:
الفرز الأول: 3 و 6 مقارنة ، 3 أقل من 6 ، لا يوجد موضع تبادل: 362819
النوع الثاني: 6 و 2 مقارنة ، 6 أكبر من 2 ، وضع المبادلة: 326819
الترتيب الثالث: 6 و 8 مقارن ، 6 أكبر من 8 ، لا يوجد موضع تبادل: 326819
الترتيب الرابع: 8 و 1 مقارنة ، 8 أكبر من 1 ، وضع المبادلة: 326189
تمت مقارنة الرحلة الثانية في المجموع ، وكانت نتيجة الفرز: 326189
---------------------------------------------------------------
الترتيب الثالث:
النوع الأول: 3 و 2 مقارنة ، 3 أكبر من 2 ، وضع المبادلة: 236189
النوع الثاني: 3 و 6 مقارنة ، 3 أقل من 6 ، لا يوجد موضع تبادل: 236189
الترتيب الثالث: 6 و 1 مقارنة ، 6 أكبر من 1 ، وضع المبادلة: 231689
تمت مقارنة الرحلة الثانية في المجموع ، وكانت نتيجة الفرز: 231689
---------------------------------------------------------------
الترتيب الرابع:
الفرز الأول: 2 و 3 مقارنة ، 2 أقل من 3 ، لا يوجد موضع تبادل: 231689
النوع الثاني: 3 و 1 مقارنة ، 3 أكبر من 1 ، وضع المبادلة: 213689
تمت مقارنة الرحلة الثانية في المجموع ، وكانت نتيجة الفرز: 213689
---------------------------------------------------------------
الترتيب الخامس:
النوع الأول: 2 و 1 مقارنة ، 2 أكبر من 1 ، وضع المبادلة: 123689
تمت مقارنة الرحلة الثانية في المجموع ، وكانت نتيجة الفرز: 123689
---------------------------------------------------------------
النتيجة النهائية: 123689
---------------------------------------------------------------
من هذا يمكننا أن نرى أن الأرقام N تحتاج إلى فرز ، ويتم فرز N-1 مرات في المجموع. عدد أوقات الفرز لكل pass هو (NI) ، بحيث يمكنك استخدام عبارة حلقة مزدوجة للتحكم في عدد المرات التي ستتحكم فيها الطبقة الخارجية في عدد المرات لكل رحلة ، أي ، أي ،
لـ (int i = 1 ؛ i <arr.length-1 ؛ i ++) {for (int j = 1 ؛ j <arr.length-1-i ؛ j ++) {// swap position}مزايا فرز الفقاعة: في كل مرة تقوم فيها بالفرز ، ستقارن أقل ، لأنه في كل مرة تقوم فيها بفرز ، ستجد قيمة أكبر. كما ذكر أعلاه: بعد المقارنة الأولى ، يجب أن يكون الرقم الأخير هو الرقم الأكبر. عند فرز المرة الثانية ، تحتاج فقط إلى مقارنة الأرقام الأخرى بخلاف الرقم الأخير ، ويمكنك أيضًا العثور على أن أكبر رقم يتم تصنيفه بعد الرقم المشارك في المقارنة الثانية. عند مقارنة المرة الثالثة ، تحتاج فقط إلى مقارنة الأرقام الأخرى بخلاف الرقمين الأخيرين ، وما إلى ذلك ... وبعبارة أخرى ، إذا لم تقارن مقارنة ، في كل مرة تقارنها مرة واحدة ، مما يقلل من كمية الخوارزمية إلى حد ما.
من حيث التعقيد الوقت:
1. إذا كانت بياناتنا في حالة جيدة ، فنحن بحاجة فقط إلى القيام برحلة لإكمال الفرز. العدد المطلوب من المقارنات وحركات السجلات هي الحد الأدنى للقيمة ، أي: cmin = n-1 ؛ mmin = 0 ؛ لذلك ، فإن أفضل تعقيد للوقت لفرز الفقاعات هو O (N).
2. إذا للأسف ، فإن بياناتنا هي ترتيب عكسي ، مطلوب طلب N-1. يجب مقارنة كل أمر (1≤I≤N-1) ، ويجب نقل كل مقارنة إلى السجل ثلاث مرات للوصول إلى موضع سجل التبادل. في هذه الحالة ، تصل كل من أوقات المقارنة والحركة إلى الحد الأقصى: أسوأ تعقيد الوقت من نوع الفقاعة هو: O (N2).
لتلخيص: إجمالي متوسط تعقيد الوقت من نوع الفقاعة هو: O (N2).
تنفيذ الكود:
/ * * bubble sort */public class bubblesort {public static void main (string [] args) {int [] arr = {6،3،8،2،9،1} ؛ System.out.println ("الصفيف قبل الفرز هو:") ؛ لـ (int num: arr) {system.out.print (num+"") ؛ } لـ (int i = 1 ؛ i <arr.length ؛ i ++) {// تتحكم الحلقة الخارجية في عدد أوقات الفرز لـ (int j = 1 ؛ j <arr.length-i ؛ j ++) {// تحكم الحلقة الداخلية في عدد المرات في كل مرة يتم فرزها إذا (arr [j-1]> arr [j]) arr [j] = arr [j-1] ؛ arr [j-1] = temp ؛ }}} system.out.println () ؛ System.out.println ("الصفيف المرتبة هو:") ؛ لـ (int num: arr) {system.out.print (num+"") ؛ }}}