บทความนี้อธิบายถึงวิธีการใช้งานการเรียงลำดับที่เท่าเทียมกันของการเรียงลำดับการแลกเปลี่ยน Java แบ่งปันสำหรับการอ้างอิงของคุณ รายละเอียดมีดังนี้:
การเรียงลำดับความเท่าเทียมกันหรือการเรียงลำดับการขนย้ายพาริตี้หรือการเรียงลำดับอิฐเป็นอัลกอริทึมการเรียงลำดับที่ค่อนข้างง่ายซึ่งเดิมคิดค้นขึ้นมาสำหรับการคำนวณแบบขนานกับการเชื่อมต่อระหว่างท้องถิ่น นี่คือการเรียงลำดับเปรียบเทียบคล้ายกับลักษณะของการเรียงลำดับฟอง
ในอัลกอริทึมนี้โดยการเปรียบเทียบตำแหน่งตัวเลขตัวเลขที่อยู่ติดกัน (แปลก) ในอาร์เรย์ถ้าคู่คี่-แม้จะอยู่ในลำดับที่ไม่ถูกต้อง (อันแรกนั้นมากกว่าที่สอง) จากนั้นแลกเปลี่ยน ทำซ้ำขั้นตอนต่อไป แต่สำหรับคู่ตัวเลข (แม้กระทั่งแปลก) ดำเนินการต่อไปเช่นนี้อีกสลับกัน
การเรียงลำดับของอาร์เรย์โปรเซสเซอร์
ในการเรียงลำดับการคำนวณแบบขนานแต่ละโปรเซสเซอร์จะประมวลผลค่าหนึ่งค่าที่สอดคล้องกับมันและมีการเชื่อมต่อระหว่างท้องถิ่นกับเพื่อนบ้านด้านซ้ายและขวาเท่านั้น โปรเซสเซอร์ทั้งหมดสามารถเปรียบเทียบและแลกเปลี่ยนการดำเนินงานกับเพื่อนบ้านในเวลาเดียวกันสลับกันในลำดับแปลก ๆ อัลกอริทึมได้รับการตีพิมพ์ครั้งแรกโดย Habermann ในปี 1972 และแสดงให้เห็นถึงประสิทธิภาพในการประมวลผลแบบขนาน
อัลกอริทึมสามารถขยายได้อย่างมีประสิทธิภาพไปยังกรณีที่โปรเซสเซอร์แต่ละตัวมีหลายค่า ในอัลกอริทึมการแบ่งพาร์ติชันของ Baudetstevenson Parity การแบ่งพาร์ติชันแต่ละโปรเซสเซอร์แต่ละตัวเรียงลำดับ subarrays ที่เป็นเจ้าของในแต่ละขั้นตอนจากนั้นดำเนินการพาร์ติชันผสานหรือการขนย้ายที่รวมกับเพื่อนบ้าน
ความเท่าเทียมกันของ Batcher และแม้กระทั่งการเรียงลำดับ
Batcher Parity Sorting เป็นอัลกอริทึมการเรียงลำดับที่เกี่ยวข้อง แต่มีประสิทธิภาพมากขึ้นซึ่งใช้การแลกเปลี่ยนการแลกเปลี่ยนและการดำเนินการสับเปลี่ยนที่สมบูรณ์แบบ
วิธีการของ Batcher นั้นมีประสิทธิภาพมากในการประมวลผลการคำนวณแบบขนานที่มีการเชื่อมต่อระหว่างกันอย่างกว้างขวาง
ความซับซ้อนเวลาที่เลวร้ายที่สุด/theta (n^2)
กราฟการเรียงลำดับแบบไดนามิกพาริตี้มีดังนี้:
การใช้รหัส:
แพ็คเกจ com.baobaotao.test; : pre "> </span> * @param array <span style =" space white-space: pre "> </span> */void batchersort (int [] array) {int length = array.length; = จริง; ในขณะที่ (จริง) {flag = true; , i+1); , i+1); ที่จะแลกเปลี่ยน b * @param c จำนวนที่จะแลกเปลี่ยน c */ โมฆะคงที่สาธารณะ swap (int [] a, int b, int c) {int temp = 0; ]> a [c]) {temp = a [b]; printarr (int [] array) {สำหรับ (int c: array) {system.out.print (c + ""); [] number = {11,95,45,15,78,84,51,24,12};การวิเคราะห์เอาท์พุท:
11 45 15 95 51 78 12 84 2411 15 45 51 12 95 24 78 8411 15 12 45 24 51 78 95 8411 12 15 24 45 51 78 84 95 95 95
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน