ไอเดียพื้นฐาน
Radixsort ได้รับการพัฒนาขึ้นอยู่กับการเรียงลำดับของถังและการเรียงลำดับทั้งสองเป็นการใช้งานขั้นสูงของการจัดสรรการจัดเรียง แนวคิดพื้นฐานของการกระจาย: กระบวนการจัดเรียงไม่จำเป็นต้องเปรียบเทียบคำหลัก แต่ใช้การเรียงลำดับผ่านกระบวนการ "แจกจ่าย" และ "รวบรวม" ความซับซ้อนของเวลาของพวกเขาสามารถบรรลุลำดับเชิงเส้น: o (n)
การเรียงลำดับของ Cardinality เป็นอัลกอริทึมการเรียงลำดับที่มั่นคง แต่มีข้อ จำกัด บางประการ:
1. คำหลักสามารถย่อยสลายได้
2. จำนวนคำหลักที่บันทึกไว้มีขนาดเล็กลงและจะดีกว่าถ้าพวกเขามีความหนาแน่น 3. หากเป็นตัวเลขจะเป็นการดีที่สุดที่จะไม่ได้ลงนามมิฉะนั้นความซับซ้อนของการแมปที่สอดคล้องกันจะเพิ่มขึ้น คุณสามารถจัดเรียงกันได้ก่อน
ลองมาดูการเรียงลำดับถัง (RadixSort)
การเรียงลำดับถังเรียกว่าการเรียงลำดับกล่อง (binsort) ความคิดพื้นฐานของมันคือการตั้งค่าถังหลายถังสแกนบันทึกที่จะจัดเรียง r [0], r [1], …, r [n-1] โหลดระเบียนทั้งหมดด้วยคำหลักในช่วงที่แน่นอนลงในถัง KTH
ตัวอย่างเช่นในการเรียงลำดับการเล่นไพ่ 52 ไพ่โดยจุด A <2 <… <j <q <k, 13 "ถัง" ต้องตั้งค่า เมื่อเรียงลำดับการ์ดแต่ละใบจะถูกวางไว้ในถังที่สอดคล้องกันตามจุดและจากนั้นถังจะเชื่อมต่อกันตามลำดับเพื่อรับสำรับการ์ดที่จัดเรียงตามลำดับที่เพิ่มขึ้นของคะแนน
ในการเรียงลำดับถังจำนวนถังขึ้นอยู่กับช่วงค่าของคำหลัก ดังนั้นการเรียงลำดับของถังจึงต้องการให้ประเภทคำหลักมี จำกัด มิฉะนั้นอาจจำเป็นต้องใช้ถังไม่ จำกัด
โดยทั่วไปแล้วมันไม่สามารถคาดเดาได้ว่ามีการเก็บบันทึกที่มีคำหลักเท่ากันจำนวนเท่าใดในแต่ละถังดังนั้นประเภทของถังควรได้รับการออกแบบเป็นรายการที่เชื่อมโยง
เพื่อให้แน่ใจว่าการเรียงลำดับมีความเสถียรการเชื่อมต่อระหว่างกระบวนการบรรจุและการรวบรวมจะต้องดำเนินการตามหลักการแรกในการออก
สำหรับการเรียงลำดับถังเวลาของกระบวนการจัดสรรคือ o (n); เวลาของกระบวนการรวบรวมคือ o (m) (รายการที่เชื่อมโยงใช้เพื่อจัดเก็บอินพุตที่จะจัดเรียงบันทึก) หรือ O (m+n) ดังนั้นเวลาสำหรับการเรียงลำดับถังคือ o (m+n) หากลำดับของขนาดของจำนวนถัง m คือ o (n) เวลาของการเรียงลำดับถังเป็นเส้นตรงนั่นคือ o (n)
ความซับซ้อนของเวลาส่วนใหญ่ของอัลกอริทึมการเรียงลำดับที่สำคัญที่กล่าวถึงข้างต้นคือ O (N2) และอัลกอริทึมการเรียงลำดับบางอย่างคือ O (nlogn) แต่การเรียงลำดับบาร์เรลสามารถบรรลุความซับซ้อนของเวลาของ O (n) อย่างไรก็ตามข้อเสียของการเรียงลำดับถังคือ: ประการแรกความซับซ้อนของพื้นที่ค่อนข้างสูงและจำเป็นต้องใช้ค่าใช้จ่ายเพิ่มเติม การเรียงลำดับมีอาร์เรย์สองอาร์เรย์ของค่าใช้จ่ายหนึ่งเก็บอาร์เรย์ที่จะจัดเรียงและอีกอันหนึ่งเป็นถังที่เรียกว่า ตัวอย่างเช่นค่าที่จะเรียงลำดับคือจาก 0 ถึง M-1 จากนั้นจำเป็นต้องมีถัง M และอาร์เรย์ถังนี้ต้องใช้พื้นที่อย่างน้อย m ประการที่สององค์ประกอบที่จะจัดเรียงจะต้องอยู่ในช่วงที่กำหนด ฯลฯ
การเรียงลำดับของ Cardinality เป็นการปรับปรุงการจัดเรียงแบบถังซึ่งทำให้ "การเรียงลำดับถัง" เหมาะสำหรับชุดค่าองค์ประกอบที่ใหญ่กว่าแทนที่จะปรับปรุงประสิทธิภาพ
มาใช้ตัวอย่างการเล่นไพ่เพื่อแสดงให้เห็น การ์ดประกอบด้วยคำหลักสองคำ: ชุดสูท (Peach <Heart <mei <mei <square) + ค่าหน้า (a <2 <3 <4 <... <k) หากขนาดของการ์ดถูกกำหนดโดยชุดสูทก่อนและการ์ดของชุดชุดเดียวกันจะถูกกำหนดโดยจำนวน เรามีอัลกอริทึมสองอย่างเพื่อแก้ปัญหานี้
นั่นคือถ้าชุดสูทแตกต่างกันไม่ว่าค่าใบหน้าจะเป็นอย่างไรการ์ดที่มีสีสูทที่ต่ำกว่านั้นเล็กกว่าสีสูทที่มีสีสูทสูงกว่า เฉพาะในชุดสูทชุดเดียวกันความสัมพันธ์ขนาดจะถูกกำหนดโดยขนาดของค่าใบหน้า นี่คือการสั่งซื้อรหัสคีย์หลายรหัส
เพื่อให้ได้ผลลัพธ์การเรียงลำดับเราจะพูดถึงวิธีการเรียงลำดับสองวิธี
วิธีที่ 1: เรียงลำดับชุดสูทและสีแรกและแบ่งออกเป็น 4 กลุ่มคือกลุ่มดอกพลัมพลัมกลุ่มสแควร์กลุ่มหัวใจสีแดงและกลุ่มหัวใจสีดำ จากนั้นจัดเรียงแต่ละกลุ่มตามค่าหน้าและสุดท้ายเชื่อมต่อ 4 กลุ่มเข้าด้วยกัน
วิธีที่ 2: ก่อนอื่นให้ 13 กลุ่มตัวเลข (หมายเลข 2, 3, ... , a) ตามค่าใบหน้า 13 ตัวใส่การ์ดลงในกลุ่มตัวเลขที่สอดคล้องกันตามค่าใบหน้าและแบ่งออกเป็น 13 กอง จากนั้นให้กลุ่มหมายเลข 4 (ดอกพลัม, สี่เหลี่ยม, หัวใจสีแดง, หัวใจสีดำ) นำการ์ดออกในกลุ่ม 2 และนำพวกเขาเข้าไปในกลุ่มสีที่สอดคล้องกันจากนั้นนำการ์ดออกมาในกลุ่ม 3 และนำพวกเขาไปสู่กลุ่มสีที่สอดคล้องกัน ... ด้วยวิธีนี้กลุ่มสีทั้ง 4
การเรียงลำดับรหัสหลายคีย์ถูกเรียงลำดับตามลำดับจากรหัสหลักไปยังรหัสคีย์ที่สองหรือจากคีย์ที่สองไปยังรหัสหลักหลักและแบ่งออกเป็นสองวิธี:
ลำดับความสำคัญบิตที่สำคัญที่สุด (MostInicantDigitFirst) ซึ่งเรียกว่าวิธี MSD:
1) การจัดเรียงครั้งแรกและจัดกลุ่มโดย K1 แบ่งลำดับออกเป็นหลายลำดับ ในบันทึกของกลุ่มลำดับเดียวกันรหัสคีย์ K1 มีค่าเท่ากัน
2) จากนั้นจัดเรียงแต่ละกลุ่มเป็นกลุ่มย่อยโดย K2 หลังจากนั้นให้เรียงลำดับรหัสคีย์ต่อไปนี้ด้วยวิธีนี้จนกว่าแต่ละกลุ่มย่อยจะถูกเรียงลำดับด้วยรหัสคีย์รอง KD
3) จากนั้นเชื่อมต่อกลุ่มเพื่อรับลำดับที่สั่งซื้อ วิธีการที่แนะนำในการเรียงลำดับการ์ดตามชุดและค่าใบหน้าคือวิธี MSD
วิธีการที่สำคัญน้อยที่สุด digitfirst เรียกว่าวิธี LSD:
1) เริ่มเรียงลำดับจาก KD จากนั้นจัดเรียง KD-1 ซ้ำ ๆ จนกว่าจะถูกแบ่งออกเป็นลำดับที่เล็กที่สุดตาม K1
2) สุดท้ายให้เชื่อมต่อแต่ละลำดับย่อยเพื่อให้ได้ลำดับที่สั่งซื้อ วิธีที่สองที่แนะนำในการเรียงลำดับการ์ดตามความเหมาะสมและค่าใบหน้าคือวิธี LSD
คำหลักเดียวของประเภทตัวเลขหรืออักขระสามารถถือได้ว่าเป็นคำหลายคีย์ที่ประกอบด้วยตัวเลขหลายหลักหรือหลายอักขระ ในเวลานี้วิธี "การจัดสรร-รวบรวม" สามารถใช้ในการเรียงลำดับ กระบวนการนี้เรียกว่าวิธีการเรียงลำดับของ cardinality ซึ่งจำนวนของค่าที่เป็นไปได้สำหรับแต่ละหมายเลขหรืออักขระเรียกว่า cardinality ตัวอย่างเช่นฐานของชุดการเล่นไพ่คือ 4 และฐานของค่าใบหน้าคือ 13 เมื่อเรียงลำดับการเล่นไพ่คุณสามารถจัดระเบียบตามสไตล์ก่อนหรือตามค่าใบหน้าก่อน เมื่อเรียงลำดับตามสีก่อนแบ่งออกเป็น 4 สแต็ค (การแจกแจง) ตามลำดับของสีแดงสีดำสี่เหลี่ยมจัตุรัสและดอกไม้จากนั้นซ้อนกัน (รวบรวม) ตามลำดับนี้แล้วแบ่งออกเป็น 13 สแต็ค (การแจกแจง) ตามลำดับของค่าใบหน้า ด้วยวิธีนี้การจัดสรรทุติยภูมิและคอลเลกชันสามารถจัดเรียงไพ่เล่นได้อย่างเป็นระเบียบ
ในระหว่างกระบวนการ "การจัดสรร-รวบรวม" ความเสถียรของการเรียงลำดับจะต้องได้รับการรับรอง
แนวคิดของการเรียงลำดับของ cardinality คือการเก็บแต่ละกลุ่มของคำหลักในข้อมูลที่จะเรียงลำดับตามลำดับ ตัวอย่างเช่นลำดับต่อไปนี้ที่จะจัดเรียง:
135, 242, 192, 93, 345, 11, 24, 19
เราแบ่งตัวเลขหนึ่งสิบและหลายร้อยของแต่ละค่าออกเป็นสามคำหลักเช่น:
135-> K1 (ตัวเลขเดียว) = 5, K2 (สิบหลัก) = 3, K3 (ร้อยหลัก) = 1
จากนั้นเริ่มต้นจากบิตเดียวต่ำสุด (เริ่มต้นจากคำหลักสุดท้าย) คำหลัก K1 ทั้งหมดของข้อมูลทั้งหมดจะถูกจัดสรรถัง (เนื่องจากแต่ละหมายเลขคือ 0-9 ดังนั้นขนาดของถังคือ 10) จากนั้นจะส่งออกข้อมูลในที่เก็บตามลำดับเพื่อให้ได้ลำดับต่อไปนี้
(11), (242, 192), (93), (24), (135, 345), (19) (การเรียงลำดับเริ่มต้นจากคำหลักมากที่สุดโดยไม่สนใจตัวเลขร้อยสิบหลักและจัดสรรตามตัวเลขในตัวเลขหลักเดียว)
จากนั้นลำดับข้างต้นจะถูกจัดสรรสำหรับ K2 และลำดับเอาต์พุตคือ:
(11, 19), (24), (135), (242, 345), (192, 93) (อ้างถึงคำหลักที่มากที่สุดในการเรียงลำดับคำหลักที่สองไม่สนใจตัวเลขร้อยและเดียวและจัดสรรตามจำนวนสิบหลัก)
ในที่สุดสำหรับการจัดสรรถังของ K3 ลำดับผลลัพธ์คือ:
(011, 019, 024, 093), (135, 192), (242), (345) (ดูคำหลักที่สองเพื่อเรียงลำดับคำหลักสูงสุดละเว้นตัวเลขสิบและเดียวและจัดสรรตามตัวเลขในตัวเลขร้อยหลัก)
การเรียงลำดับเสร็จสมบูรณ์
การใช้งาน Java
โมฆะสาธารณะ radixsort () {int max = array [0]; สำหรับ (int i = 0; i <array.length; i ++) {// ค้นหาค่าสูงสุดในอาร์เรย์ถ้า (อาร์เรย์ [i]> max) {max = array [i]; }} int keysnum = 0; // จำนวนคำหลักเราใช้หลักเดียวสิบหลักและหลายร้อย ... เป็นคำหลักดังนั้นจำนวนคำหลักคือตัวเลขสูงสุดในขณะที่ (สูงสุด> 0) {สูงสุด /= 10; Keysnum ++; } รายการ <arrayList <จำนวนเต็ม >> buckets = new ArrayList <arrayList <จำนวนเต็ม >> (); สำหรับ (int i = 0; i <10; i ++) {// หมายเลขที่เป็นไปได้สำหรับแต่ละหลักคือ 0 ~ 9 ดังนั้นตั้ง 10 buckets buckets.add (arraylist ใหม่ <integer> ()); // ถังประกอบด้วย arraylist <integer>} สำหรับ (int i = 0; i <keysnum; i ++) {// เริ่มต้นด้วยคำหลักล่าสุดให้กำหนดตามคำหลักในการกลับ (int j = 0; j <array.length; j ++) {// สแกนองค์ประกอบทั้งหมด องค์ประกอบเช่น 258 ตอนนี้คุณต้องถอดหมายเลขในสิบหลัก 258%100 = 58,58/10 = 5 int key = array [j]%(int) math.pow (10, i+1)/(int) math.pow (10, i); buckets.get (key) .add (array [j]); // ใส่องค์ประกอบนี้ลงในถังด้วยคีย์คีย์คีย์} // หลังจากการจัดสรรแล้วให้คัดลอกองค์ประกอบในถังกลับไปที่ตัวนับอาร์เรย์ int = 0; // ตัวนับองค์ประกอบสำหรับ (int j = 0; j <10; j ++) {arraylist <integer> bucket = buckets.get (j); // bucket ด้วยคำหลัก j ในขณะที่ (bucket.size ()> 0) {array [counter ++] = bucket.remove (0); // คัดลอกองค์ประกอบแรกในถังไปยังอาร์เรย์และลบ}} system.out.print ("เธรด"+(i+1)+"การเรียงลำดับล้อ:"); แสดง(); -ผลการพิมพ์มีดังนี้:
การวิเคราะห์อัลกอริทึม
เมื่อมองแวบแรกประสิทธิภาพการดำเนินการของการเรียงลำดับของ Cardinality ดูเหมือนจะดีและไม่น่าเชื่อว่าสิ่งที่คุณต้องทำคือคัดลอกรายการข้อมูลต้นฉบับจากอาร์เรย์ไปยังรายการที่เชื่อมโยงแล้วคัดลอกกลับ หากมี 10 รายการข้อมูลมีการจำลอง 20 ครั้งให้ทำซ้ำกระบวนการสำหรับแต่ละบิต สมมติว่าต้องมีการจัดเรียงตัวเลข 5 หลักจำเป็นต้องมี 20*5 = 100 สำเนา หากมีรายการข้อมูล 100 รายการแสดงว่ามี 200*5 = 1,000 สำเนา จำนวนสำเนาเป็นสัดส่วนกับจำนวนรายการข้อมูลนั่นคือ o (n) นี่คืออัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพที่สุดที่เราเคยเห็น
น่าเสียดายที่รายการข้อมูลมากขึ้นจำเป็นต้องใช้คำหลักที่ยาวขึ้น หากรายการข้อมูลเพิ่มขึ้น 10 ครั้งคำหลักจะต้องเพิ่มโดยหนึ่ง (การเรียงลำดับอีกหนึ่งรอบ) จำนวนสำเนาและจำนวนรายการข้อมูลเป็นสัดส่วนกับความยาวของคำหลักและสามารถพิจารณาได้ว่าความยาวของคำหลักคือลอการิทึมของ N ดังนั้นในกรณีส่วนใหญ่ประสิทธิภาพการดำเนินการของการเรียงลำดับพระคาร์ดินัลจะกลับไปที่ O (N*logn) ซึ่งเกือบจะเหมือนกับการเรียงลำดับอย่างรวดเร็ว
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการแนะนำการเรียงลำดับของ Cardinality และการใช้ภาษา Java ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น