ملخص خوارزميات جافا الكلاسيكية: فرز الفقاعات

المبدأ: قارن عنصرين مجاورتين وعناصر التبادل مع قيم كبيرة إلى الطرف الأيمن.

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

على سبيل المثال: لفرز الصفيف: 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+"") ؛ }}}