نوع الفقاعة:
إنه لمقارنة عنصرين متجاورتين على التوالي وفقًا للمؤشر. إذا كانت أكبر من/أقل من (اعتمادًا على ما إذا كانت بحاجة إلى تصاعدي أو تنازلي) ، فسيتم استبدالها. خلاف ذلك ، لن تكون هناك تغييرات في هذا الطريق. بعد مقارنة N-1 مرات ، N يساوي عدد العناصر ؛ N-2 ، N-3 ... حتى الجولة الأخيرة ، تتم مقارنتها مرة واحدة ، وبالتالي فإن عدد المقارنات يتناقص: من N-1 إلى 1
ثم العدد الإجمالي للمقارنات هو: 1+2+3+...+(N-1) ، محسوب بواسطة الصيغة الحسابية: (1+N-1)/2*(N-1) ==> N/2*(N-1) ==> (N^2-N)*0.5
يتم التعبير عن التعقيد الزمني للخوارزمية بواسطة O: O (n^2) ، ويتم تجاهل المعامل 0.5 و thestal -n.
الفئة العامة bubblesort {public static void main (string [] args) {int len = 10 ؛ int [] ary = new int [len] ؛ عشوائي عشوائي = جديد عشوائي () ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {ary [j] = random.nextint (1000) ؛ } system.out.println ("-----------------") ؛ لـ (int j = 0 ؛ j <ary.length ؛ j ++) {system.out.print (ary [j]+"") ؛ }/** ترتيب تصاعدي ، ASC1 و ASC2 تحسين عدد المقارنات للحلقات الداخلية ، والتي هي أفضل* مقارنات إجمالية:* ASC1 ، ASC2: (1+N-1)/2* (N-1) ==> n/2* (n-1) ==> n* (n-1)/2 ==-n)/2* // orderasc2 (ary) ؛ Orderasc1 (ary) ؛ // ترتيب تنازلي ، فقط بحاجة إلى استبدال حجم الحكم} static void orderasc (int [] ary) {int count = 0 ؛ // عدد المقارنات int len = ary.length ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {// عدد الدورات الثابتة الخارجية لـ (int k = 0 ؛ k <len - 1 ؛ k ++) {// عدد الحلقات الثابتة الداخلية الداخلية إذا (ary [k]> ary [k + 1]) القيم * a = a+b * b = ab * a = ab */} count ++ ؛ }} system.out.println ("/n ------ OrderAsc بعد الفرز بترتيب تصاعدي --------- عدد المرات:" + count) ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {system.out.print (ary [j]+"") ؛ }} static void orderasc1 (int [] ary) {int count = 0 ؛ // عدد المقارنة int len = ary.length ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {// عدد الحلقات الثابتة في الطبقة الخارجية لـ (int k = len - 1 ؛ k> j ؛ k--) {// عدد المقارنات في الطبقة الداخلية من المزيد إلى أقل (ary [k] <ary [k - 1]) {ary [k] = ary [k - 1] Exchange} count ++ ؛ }} System.out.println ("/n ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.print (ary [j] + "") ؛ 0 ؛ order ------ عدد المرات:مطبعة
------- قبل الفرز -------- 898 7 862 286 879 660 433 724 316 737 ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
فرز الفقاعة ثنائية الاتجاه
فرز Bubble Sorting_Cocktail هو فرز الفقاعات ثنائية الاتجاه.
الفرق بين هذه الخوارزمية وفرز الفقاعات هو أنه عند الفرز ، يتم فرزه في اتجاهين في التسلسل ، والطبقة الخارجية تقارن الحدود اليسرى واليمنى l <r ،
تتناسب دورة في الطبقة الداخلية من اليسار إلى اليمين ، ويتم تعيين القيمة العالية بعد ؛ تعتمد الدورة على اليمين إلى اليسار ، ويتم تعيين القيمة المنخفضة من قبل ؛
من حيث الكفاءة ، O (n^2) ، ليست أسرع من الفقاعات العادية
الفئة العامة bubble_cocktailsort {public static void main (string [] args) {int len = 10 ؛ int [] ary = new int [len] ؛ عشوائي عشوائي = جديد عشوائي () ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {ary [j] = random.nextint (1000) ؛ }/** الحد الأدنى لعدد البورصات هو وقت واحد ، والرقم الأقصى هو (n^2-n)/2 مرات* // ary = new int [] {10،9،8،7،6،5،4،3،2،1} ؛ // اختبر عدد التبادلات // ary = new int [] {1،2،3،4،5،6،7،8،10،9} ؛ // Test Exchangees System.out.println ("---------------------------") ؛ لـ (int j = 0 ؛ j <ary.length ؛ j ++) {system.out.print (ary [j]+"") ؛ } orderasc1 (ary) ؛ // orderasc2 (ary) ؛ // اعتمادًا على الترتيب ، فقط بحاجة إلى استبدال حجم الحكم} static void orderasc1 (int [] ary) {int compareCount = 0 ؛ // قارن الأوقات int changeCount = 0 ؛ // عدد التبادلات int len = ary.length ؛ int left = 0 ، يمين = len -1 ، tl ، tr ؛ بينما (يسار <يمين) {// عدد الدورات الثابتة للطبقة الخارجية tl = left + 1 ؛ tr = right - 1 ؛ لـ (int k = يسار ؛ k <يمين ؛ k ++) {// عدد المقارنات للطبقة الداخلية من أكثر إلى أقل ، من اليسار إلى اليمين إذا (ary [k]> ary [k + 1]) {// الجبهة أكبر من الظهر ، ary [k] = ary [k + 1] + (ary [k + 1] = ary [k]) * 0 ؛ tr = k ؛ // يتم إعطاء الفهرس الذي يوجد فيه K إلى TR ، ويمثل TR قيمة فهرس النهاية للمقارنة اللاحقة ، بعد المقارنة من اليسار إلى اليمين ، يمثل K الفهرس على اليسار} المقارن ++ ؛ } اليمين = tr ؛ من أجل (int k = يمين ؛ k> يسار ؛ k--) {// يتم تقليل عدد المقارنات في الطبقة الداخلية من أكثر إلى أقل ، من اليمين إلى اليسار إذا (ary [k] <ary [k-1]) {// الأخير أقل من ary ary [k] = ary [k-1]+(ary [k-1] = ary [k] ؛ tl = k ؛ // في المقارنة الأخيرة في جولة ، قم بتعيين الفهرس حيث يوجد K في TL ، تمثل TL قيمة فهرس البدء للمقارنة اللاحقة. بعد المقارنة من اليمين إلى اليسار ، يمثل K الفهرس على اليمين} المقارن ++ ؛ } اليسار = tl ؛ } System.out.println ("/n ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- لـ (l <r ؛) {// عدد الدورات الثابتة الخارجية tl = l + 1 ؛ +1] ؛ ary [k - 1] = temp - ary [k - 1] ؛ ary [k] = temp - ary [k - 1] ؛ ChangeCount ++ ؛ tl = k ؛ } المقارنة ++ ؛ } l = tl ؛ } system.out.println ("/n ----- orderasc2 بعد الفرز بالترتيب الصاعد ------- عدد المقارنات:" + المقارنة + "، التبادلات:" + ChangeCount) ؛ لـ (int j = 0 ؛ j <len ؛ j ++) {system.out.print (ary [j]+"") ؛ }}}مطبعة
-------- قبل الفرز -------- 783 173 53 955 697 839 201 899 680 677 ----------------------------------------------------------------------------------------------------------------------------------------------