การเรียงลำดับฟอง:
มันคือการเปรียบเทียบสององค์ประกอบที่อยู่ติดกันอย่างต่อเนื่องตามดัชนี หากพวกเขามีค่ามากกว่า/น้อยกว่า (ขึ้นอยู่กับว่าพวกเขาจำเป็นต้องจัดเรียงขึ้นหรือลง) พวกเขาจะถูกแทนที่ มิฉะนั้นจะไม่มีการเปลี่ยนแปลงในลักษณะนี้ หลังจากเปรียบเทียบ 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 และค่าคงที่ -n จะถูกละเว้น
Bubblesort ระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int len = 10; int [] ary = new int [len]; สุ่มสุ่ม = ใหม่สุ่ม (); สำหรับ (int j = 0; j <len; j ++) {ary [j] = random.nextint (1,000); } 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-n)/2-n) // orderasc2 (ary); OrderAsc1 (ARY); // คำสั่งจากมากไปน้อยเพียงแค่ต้องแทนที่ขนาดการตัดสิน} คำสั่งซื้อโมฆะคงที่ (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]) {ary [k] = ary [k + 1] ค่าตัวแปร * a = a+b * b = ab * a = ab */} นับจำนวน ++; }} system.out.println ("/n ------ orderasc หลังจากเรียงลำดับตามลำดับจากน้อยไปมาก --------- จำนวนครั้ง:" + นับ); สำหรับ (int j = 0; j <len; j ++) {system.out.print (ary [j]+""); }} โมฆะคงที่ 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]) 0; // การแลกเปลี่ยนขั้นตอนเดียว} นับ ++; }} system.out.println ("/n ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ System.out.print (ary [j] + ""); = 0; คำสั่งซื้อ ------ จำนวนครั้ง: " + นับ); สำหรับ (int j = 0; j <len; j ++) {system.out.print (ary [j] +" ");}}}}}พิมพ์
------- ก่อนการเรียงลำดับ ------ 898 7 862 286 879 660 433 724 316 737 ------------------------------------------------------------------------------------------------------------------------------------------------------
การจัดเรียงฟองสองทาง
การเรียงลำดับ Bubble_cocktail การเรียงลำดับเป็นการเรียงลำดับฟองสองทาง
ความแตกต่างระหว่างอัลกอริทึมนี้และการเรียงลำดับฟองคือเมื่อเรียงลำดับมันจะถูกจัดเรียงในสองทิศทางในลำดับและชั้นนอกเปรียบเทียบขอบเขตซ้ายและขวา l <r,
วัฏจักรในเลเยอร์ด้านในเป็นสัดส่วนจากซ้ายไปขวาและค่าสูงจะถูกตั้งค่าหลังจาก; วัฏจักรขึ้นอยู่กับทางด้านขวาไปซ้ายและค่าต่ำถูกตั้งค่าไว้ก่อน
ในแง่ของประสิทธิภาพ o (n^2) ไม่เร็วกว่าฟองสบู่ธรรมดา
คลาสสาธารณะ BUBBLE_COCKTAILSORT {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int len = 10; int [] ary = new int [len]; สุ่มสุ่ม = ใหม่สุ่ม (); สำหรับ (int j = 0; j <len; j ++) {ary [j] = random.nextint (1,000); }/** จำนวนการแลกเปลี่ยนขั้นต่ำคือ 1 ครั้งและจำนวนสูงสุดคือ (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,8,10,9}; // ทดสอบการแลกเปลี่ยน System.out.println ("---------------------------"); สำหรับ (int j = 0; j <ary.length; j ++) {system.out.print (ary [j]+""); } orderasc1 (ary); // orderasc2 (ary); // ขึ้นอยู่กับลำดับเพียงแค่ต้องแทนที่ขนาดการตัดสิน} โมฆะคงที่ orderAsc1 (int [] ary) {int comparecount = 0; // เปรียบเทียบเวลา int angecount = 0; // จำนวนการแลกเปลี่ยน int len = ary.length; int left = 0, ขวา = len -1, tl, tr; ในขณะที่ (ซ้าย <ขวา) {// จำนวนรอบคงที่ของเลเยอร์ด้านนอก tl = ซ้าย + 1; tr = ขวา - 1; สำหรับ (int k = ซ้าย; k <ขวา; k ++) {// จำนวนการเปรียบเทียบของชั้นด้านในจากน้อยลงไปน้อยกว่าจากซ้ายไปขวาถ้า (ary [k]> ary [k + 1]) {// ด้านหน้ามากกว่าด้านหลัง tr = k; // ดัชนีที่ K อยู่ที่ TR และ TR แสดงถึงค่าดัชนีสุดท้ายของการเปรียบเทียบที่ตามมาหลังจากเปรียบเทียบจากซ้ายไปขวา K แสดงถึงดัชนีทางด้านซ้าย} comparCount ++; } ขวา = tr; สำหรับ (int k = ขวา; k> ซ้าย; k--) {// จำนวนการเปรียบเทียบในชั้นด้านในจะลดลงจากน้อยลงไปน้อยกว่าจากขวาไปซ้ายถ้า (ary [k] <ary [k-1]) {// หลังนั้นน้อยกว่าการแลกเปลี่ยน [k] tl = k; // ในการเปรียบเทียบครั้งสุดท้ายในรอบกำหนดดัชนีที่ K อยู่ที่ TL, TL แสดงถึงค่าดัชนีเริ่มต้นของการเปรียบเทียบที่ตามมา หลังจากเปรียบเทียบจากขวาไปซ้าย k แสดงถึงดัชนีทางด้านขวา} comparecount ++; } ซ้าย = tl; - System.out.println ("/n ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- - สำหรับ (; l <r;) {// จำนวนรอบนอกรอบ tl = l + 1; ary [k+1]; 1]; ary [k - 1] = temp - ary [k - 1]; ary [k] = temp - ary [k - 1]; Changecount ++; tl = k; } comparCount ++; } l = tl; } system.out.println ("/n ----- orderasc2 หลังจากการเรียงลำดับในลำดับจากน้อยไปมาก ------- จำนวนการเปรียบเทียบ:" + comparecount + ", การแลกเปลี่ยน:" + changecount); สำหรับ (int j = 0; j <len; j ++) {system.out.print (ary [j]+""); -พิมพ์
-------- ก่อนการเรียงลำดับ ------ 783 173 53 955 697 839 201 899 680 677 --------------------------------------------------------------------------------------------------------------------------------------------------