หลักการ
การเรียงลำดับฟองอาจเป็นอัลกอริทึมที่โปรแกรมเมอร์ทุกคนสามารถใช้และยังเป็นหนึ่งในอัลกอริทึมที่คุ้นเคยที่สุด
แนวคิดของมันไม่ซับซ้อน:
สมมติว่าอาร์เรย์ arr [] ถูกจัดเรียงแล้วและมีองค์ประกอบ n
1. ถ้า n = 1: เห็นได้ชัดว่าไม่จำเป็นต้องเข้าคิว (อันที่จริงการสนทนานี้ดูเหมือนจะไม่จำเป็น)
2. ถ้า n> 1:
(1) เราเริ่มต้นด้วยองค์ประกอบแรกและเปรียบเทียบทุกสององค์ประกอบที่อยู่ติดกัน หากองค์ประกอบก่อนหน้านี้มีขนาดใหญ่กว่าองค์ประกอบถัดไปอดีตจะได้รับการจัดอันดับเบื้องหลังอย่างแน่นอนในผลลัพธ์สุดท้าย ดังนั้นเราจึงแลกเปลี่ยนองค์ประกอบทั้งสองนี้ จากนั้นเปรียบเทียบองค์ประกอบสององค์ประกอบถัดไปที่อยู่ติดกัน ด้วยวิธีนี้จนกระทั่งเปรียบเทียบองค์ประกอบคู่สุดท้ายการเรียงลำดับรอบแรกจะเสร็จสมบูรณ์ เป็นที่แน่นอนว่าองค์ประกอบสุดท้ายจะต้องใหญ่ที่สุดในอาร์เรย์ (เพราะองค์ประกอบที่ค่อนข้างใหญ่จะถูกวางไว้ที่ด้านหลังทุกครั้ง)
(2) ทำซ้ำกระบวนการข้างต้นคราวนี้เราไม่จำเป็นต้องพิจารณากระบวนการสุดท้ายเพราะมีการจัดเรียงแล้ว
(3) ดังนั้นจนกว่าจะมีองค์ประกอบที่เหลืออยู่เพียงอย่างเดียวองค์ประกอบจะต้องมีขนาดเล็กที่สุดจากนั้นการเรียงลำดับของเราสามารถจบลงได้ เห็นได้ชัดว่าการเรียงลำดับ N-1 ได้ดำเนินการ
ในกระบวนการข้างต้นทุกครั้ง (หรือ "ล้อ" ถูกจัดเรียงตัวเลขจะช้า "ลอย" จากตำแหน่งที่แน่นอนไปยังตำแหน่งสุดท้าย (วาดแผนภาพแผนผังและวาดอาร์เรย์ในแนวตั้ง) เช่นเดียวกับฟองสบู่ดังนั้นจึงเรียกว่า "วิธีการเรียงลำดับฟอง"
การใช้รหัส:
Bubblesort ระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int score [] = {67, 69, 75, 87, 89, 90, 99, 100}; สำหรับ (int i = 0; i <score.length -1; i ++) {// ไม่เพียง แต่ทำ n -1 สั่งซื้อ (int j = 0; j <คะแนนความยาว -i -1; j ++) {// เรียงลำดับช่วงเวลาที่ไม่เรียงลำดับในปัจจุบัน ภายหลัง int temp = คะแนน [j]; คะแนน [j] = คะแนน [j + 1]; คะแนน [j + 1] = อุณหภูมิ; }} system.out.print ("th" + (i + 1) + "ผลการเรียงลำดับ:"); สำหรับ (int a = 0; a <score.length; a ++) {system.out.print (คะแนน [a]+"/t"); } system.out.println (""); } system.out.print ("ผลการเรียงลำดับสุดท้าย:"); สำหรับ (int a = 0; a <score.length; a ++) {system.out.print (คะแนน [a]+"/t"); }}}
ประสิทธิภาพ/ความซับซ้อนของอัลกอริทึม
เราเพิกเฉยต่อเวลาที่ตัวแปรลูปเพิ่มขึ้นโดยอัตโนมัติและเริ่มต้น ก่อนการวิเคราะห์จำนวนการเปรียบเทียบอัลกอริทึม เป็นเรื่องง่ายที่จะเห็นว่าการเรียงลำดับฟองข้างต้นโดยไม่มีการปรับปรุงใด ๆ จะดำเนินการในรอบ N-1 โดยไม่คำนึงถึงข้อมูลอินพุตและจำนวนครั้งในแต่ละรอบของการเรียงลำดับจะต้องเปรียบเทียบลดลงจาก N-1 ถึง 0 จากนั้นจำนวนการเปรียบเทียบทั้งหมดคือ (N-1)+(N-2)+...+2+1 = (N-1) (เนื่องจากฉันไม่รู้วิธีทำสี่เหลี่ยมที่นี่ที่นี่ฉันใช้ n^2 เพื่อเป็นตัวแทนสี่เหลี่ยมด้านล่างเหมือนกัน)
มาดูจำนวนการมอบหมาย การมอบหมายที่นี่หมายถึงการดำเนินการแลกเปลี่ยน สำหรับรหัสข้างต้นการแลกเปลี่ยน 1 ครั้งเท่ากับการมอบหมายสามครั้ง เนื่องจากไม่ใช่ทุกครั้งที่จำเป็นต้องแลกเปลี่ยนจำนวนการดำเนินการที่ได้รับมอบหมายจึงเกี่ยวข้องกับข้อมูลอินพุต ในกรณีที่ดีที่สุดนั่นคือเมื่อคำสั่งซื้ออยู่ในจุดเริ่มต้นจำนวนการมอบหมายคือ 0 ในกรณีที่เลวร้ายที่สุดจำนวนการมอบหมายคือ (N-1) N/2 สมมติว่าข้อมูลอินพุตเป็นการแจกแจงโดยเฉลี่ย (หรือ "สุ่มอย่างสมบูรณ์") จากนั้นประมาณครึ่งหนึ่งของจำนวนการแลกเปลี่ยน จากผลลัพธ์ข้างต้นเราสามารถได้รับกรณีเฉลี่ยโดยมีจำนวนการมอบหมายเป็น 3/2 * (n^2)/2 = 3/4 * (n^2)
โดยสรุปไม่ว่าในกรณีใดความซับซ้อนของพื้นที่การเรียงลำดับฟอง (พื้นที่พิเศษ) จะเป็น O (1) เสมอ
ทำให้ดีขึ้น
ความซับซ้อนของเวลาที่เหมาะสมจะแสดงเมื่อมีการสั่งซื้อข้อมูลอย่างสมบูรณ์ซึ่งก็คือ O (n) ในกรณีอื่น ๆ มันมักจะเป็น o (n^2) ดังนั้นอัลกอริทึมจะทำงานได้ดีที่สุดเมื่อมีการสั่งข้อมูลโดยทั่วไป
อย่างไรก็ตามรหัสด้านบนมีความซับซ้อน O (n) ได้อย่างไร ในความเป็นจริงเนื่องจากข้างต้นมุ่งเน้นไปที่แนวคิดพื้นฐานจึงเป็นเพียงกรณีที่ง่ายที่สุด เพื่อให้อัลกอริทึมมีความซับซ้อน O (n) ในกรณีที่ดีที่สุดจำเป็นต้องมีการปรับปรุงบางอย่าง รหัสที่ได้รับการปรับปรุงคือ:
Public Static Void Bubblesort (int [] arr) {int temp = 0; การแลกเปลี่ยนบูลีน; สำหรับ (int i = arr.length -1; i> 0; -i) {// ความยาวของแต่ละการเรียงลำดับจะต้องสลับ = false; สำหรับ (int j = 0; j <i; ++ j) {// จากองค์ประกอบแรกไปยังองค์ประกอบ i-th ถ้า (arr [j]> arr [j +1]) {temp = arr [j]; arr [j] = arr [j + 1]; arr [j + 1] = อุณหภูมิ; swap = true; }} // loop j ถ้า (swap == false) {break; }} // loop i} // วิธี bubblesortในความเป็นจริงเนื่องจากการเรียงลำดับฟองไม่ได้ใช้ในกรณีของข้อมูลจำนวนมากตัวแปรบูลีนที่เพิ่มเข้ามาเมื่อใช้ข้อมูลขนาดเล็กจะทำให้เกิดค่าใช้จ่ายเพิ่มเติม ดังนั้นโดยส่วนตัวแล้วฉันคิดว่าอัลกอริทึมที่ได้รับการปรับปรุงด้านบนเป็นเพียงทฤษฎีล้วนๆ โดยปกติเพียงแค่เขียนก่อนหน้านี้โดยการเรียงลำดับเดือด
ความเสถียรของอัลกอริทึม
เป็นเรื่องง่ายที่จะเห็นว่าเมื่อองค์ประกอบที่อยู่ใกล้เคียงเท่ากันเราไม่จำเป็นต้องเปลี่ยนตำแหน่งของพวกเขาดังนั้นการเรียงลำดับฟองจึงเป็นการเรียงลำดับที่มั่นคง
อัลกอริทึมสถานการณ์ที่ใช้งานได้
แนวคิดของการเรียงลำดับฟองนั้นง่ายและรหัสนั้นง่ายซึ่งเหมาะอย่างยิ่งสำหรับการเรียงลำดับข้อมูลขนาดเล็ก อย่างไรก็ตามเนื่องจากความซับซ้อนสูงของอัลกอริทึมจึงไม่เหมาะสำหรับการใช้งานเมื่อปริมาณข้อมูลมีขนาดใหญ่ หากคุณต้องใช้มันเมื่อมีข้อมูลมากขึ้นคุณควรปรับปรุงอัลกอริทึมเช่นการเลือกวิธีการเรียงลำดับ