การเรียงลำดับฟอง Java (การเรียงลำดับฟอง)

1. การเรียงลำดับฟอง

Bubble Sort เป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่ง่ายกว่าในการเขียนโปรแกรม โดยจะเดินผ่านลำดับเพื่อจัดเรียงซ้ำๆ โดยเปรียบเทียบสององค์ประกอบในแต่ละครั้ง และสลับองค์ประกอบเหล่านั้นหากอยู่ในลำดับที่ไม่ถูกต้อง ทำซ้ำการทำงานของการเยี่ยมชมอาร์เรย์จนกว่าจะไม่มีองค์ประกอบที่ต้องแลกเปลี่ยนอีกต่อไป ซึ่งหมายความว่าอาร์เรย์ได้รับการจัดเรียงแล้ว

Bubble sort เปรียบเสมือนฟองสบู่ที่โผล่ออกมาจากน้ำ โดย Bubble sort จะเป็นตัวเลขที่เล็กที่สุดหรือมากที่สุด ขึ้นอยู่กับว่าเรากำลังเรียงลำดับอาร์เรย์จากน้อยไปมากหรือจากมากไปน้อย โดยฟองสบู่จะเด้งขึ้นมาที่จุดเริ่มต้นหรือจุดสิ้นสุดของอาร์เรย์

2. หลักการอัลกอริธึมของการเรียงลำดับฟอง

1) เปรียบเทียบองค์ประกอบที่อยู่ติดกัน หากองค์ประกอบแรกมีขนาดใหญ่กว่าองค์ประกอบที่สอง ให้สลับทั้งสองรายการ

2) ทำเช่นเดียวกันกับทุกคู่ขององค์ประกอบที่อยู่ติดกัน โดยเริ่มจากคู่แรกและลงท้ายด้วยคู่สุดท้าย ซึ่งจุดนี้องค์ประกอบสุดท้ายควรเป็นตัวเลขที่มากที่สุด

3) ทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบทั้งหมด ยกเว้นขั้นตอนสุดท้าย

4) ทำซ้ำขั้นตอนข้างต้นต่อไปเพื่อให้องค์ประกอบน้อยลงเรื่อยๆ จนกว่าจะไม่มีตัวเลขคู่ที่จะเปรียบเทียบ

3. ความซับซ้อนและประสิทธิภาพของการเรียงลำดับแบบฟอง

การเรียงลำดับแบบบับเบิ้ลทำงานได้ไม่ดีเมื่อเทียบกับอัลกอริธึมการเรียงลำดับอื่นๆ เช่น การเรียงลำดับแบบด่วน การเรียงลำดับแบบผสาน หรือการเรียงลำดับแบบเชลล์ ความซับซ้อนของตัวพิมพ์โดยเฉลี่ยของอัลกอริธึมเหล่านี้คือ O(nlogn) ในขณะที่ความซับซ้อนของตัวพิมพ์โดยเฉลี่ยของการเรียงลำดับแบบฟองคือ O(n^2)

ในกรณีที่ดีที่สุด การเรียงลำดับแบบบับเบิลจะดีกว่าการเรียงลำดับอย่างรวดเร็วด้วยประสิทธิภาพ O(n) การเรียงลำดับแบบบับเบิ้ลช้ากว่าการเรียงลำดับแบบด่วนหรือการเรียงลำดับแบบรวมถึงสามเท่า แม้ว่าจะมี n=100 แต่ก็ง่ายต่อการนำไปใช้และจดจำ

ความซับซ้อนและประสิทธิภาพของการเรียงลำดับแบบบับเบิ้ลมีดังนี้:

1) ประสิทธิภาพกรณีที่แย่ที่สุดของการเรียงลำดับแบบฟองคือ O(n^2)

2) ประสิทธิภาพกรณีที่ดีที่สุดของการเรียงลำดับแบบฟองคือ O(n)

3) ประสิทธิภาพโดยเฉลี่ยของการเรียงลำดับแบบฟองคือ O(n^2)

4. รหัสแบบฟอร์ม

 //Bubble sort publicstaticvoidbubbleSort(int[]arr){//ลูปด้านนอกใช้เพื่อควบคุมจำนวนรอบของลูปอาเรย์สำหรับ(inti=0;i<arr.length-1;i++){//ด้านใน loop ใช้ในการเปรียบเทียบค่าองค์ประกอบให้สมบูรณ์และสลับค่าองค์ประกอบที่ใหญ่กว่าไปทางด้านหลัง for(intj=0;j<arr.length-1-i;j++){if(arr[j]>arr [j+1]){inttemp= arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}//ผลลัพธ์ผลลัพธ์สำหรับ (intn:nums){ระบบ .out.println(n);} }

ตัวอย่างเช่น:

 publicclassMain {publicstaticvoidmain(String[]args){inta[]={6,1,15,32,9};for(inti=1;i<a.length;i++){for(intj=0;j<a .length-1;j++){if(a[j]>a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp ;}}}System.out.println(ผลลัพธ์ของการเรียงลำดับฟองคือ:);for(inttemp:a){System.out.print(temp+);}}}

ผลการวิ่งมีดังนี้:

 ผลลัพธ์ของการเรียงลำดับแบบฟองคือ: 1691532

คุณสามารถลองด้วยตัวเอง!