หลักการ: เปรียบเทียบสององค์ประกอบที่อยู่ติดกันและการแลกเปลี่ยนองค์ประกอบที่มีค่ามากไปทางด้านขวา
แนวคิด: เปรียบเทียบตัวเลขสองตัวที่อยู่ติดกันตามลำดับวางทศนิยมไว้ด้านหน้าและจำนวนมากที่ด้านหลัง นั่นคือในการเดินทางครั้งแรก: ก่อนอื่นเปรียบเทียบตัวเลขแรกและหมายเลขที่สองให้วางทศนิยมก่อนและจำนวนมากหลังจากนั้น จากนั้นเปรียบเทียบหมายเลขที่สองและหมายเลขที่สามให้วางทศนิยมก่อนและหลังจำนวนใหญ่ให้ดำเนินการต่อไปเช่นนี้จนกว่าจะมีการเปรียบเทียบตัวเลขสองตัวสุดท้ายให้วางทศนิยมก่อนและหลังจำนวนใหญ่ ทำซ้ำขั้นตอนแรกจนกว่าการเรียงลำดับทั้งหมดจะเสร็จสมบูรณ์
ตัวอย่างเช่น: ในการเรียงลำดับอาร์เรย์: 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 เวลาทั้งหมดจะถูกจัดเรียงทั้งหมด จำนวนเวลาการเรียงลำดับสำหรับ I-Pass แต่ละตัวคือ (Ni) ดังนั้นคุณสามารถใช้คำสั่งวนซ้ำสองเท่าเพื่อควบคุมจำนวนครั้งที่ชั้นนอกจะควบคุมจำนวนครั้งสำหรับการเดินทางแต่ละครั้งนั่นคือ
สำหรับ (int i = 1; i <arr.length-1; i ++) {สำหรับ (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)
การใช้รหัส:
/ * * การเรียงลำดับฟอง */Bubblesort ระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] arr = {6,3,8,2,9,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-1]; arr [j-1] = อุณหภูมิ; }}} system.out.println (); System.out.println ("อาร์เรย์ที่เรียงลำดับคือ:"); สำหรับ (int num: arr) {system.out.print (num+""); -