การจัดเรียงอย่างรวดเร็วหรือที่เรียกว่าการแบ่งพาร์ติชันและการเรียงลำดับ อัลกอริทึมการเรียงลำดับอย่างรวดเร็วนำไปใช้กับกลยุทธ์ในการแบ่งและพิชิต
บทความนี้ส่วนใหญ่พูดถึงการใช้ JavaScript เพื่อใช้การเรียงลำดับอย่างรวดเร็วของแนวคิดในสถานที่
วิธีการหารและรักษา:
ในวิทยาศาสตร์คอมพิวเตอร์วิธีการแบ่งและพิชิตเป็นกระบวนทัศน์อัลกอริทึมที่สำคัญมากตามการเรียกซ้ำสาขาหลายสาขา คำอธิบายที่แท้จริงคือ "การหารและพิชิต" ซึ่งหมายถึงการแบ่งปัญหาที่ซับซ้อนออกเป็นสองหรือมากกว่าสองปัญหาย่อยที่เหมือนกันหรือคล้ายกันจนกว่าจะสิ้นสุดปัญหาย่อยสามารถแก้ไขได้ง่ายและโดยตรงและการแก้ปัญหาดั้งเดิมคือการควบรวมกิจการของการแก้ปัญหาย่อย (ข้อความที่ตัดตอนมาจาก Wikipedia)
แนวคิดการเรียงลำดับอย่างรวดเร็ว
ระบุองค์ประกอบในอาร์เรย์เป็นไม้บรรทัดวางขนาดใหญ่กว่าและวางให้เล็กกว่ามันก่อนที่องค์ประกอบทำซ้ำสิ่งนี้จนกว่าทั้งหมดจะถูกจัดเรียงตามลำดับบวก
การเรียงลำดับอย่างรวดเร็วแบ่งออกเป็นสามขั้นตอน:
เลือกเกณฑ์มาตรฐาน: เลือกองค์ประกอบเป็นเกณฑ์มาตรฐานในโครงสร้างข้อมูล (Pivot)
พาร์ติชัน: อ้างถึงขนาดของค่าองค์ประกอบอ้างอิงแบ่งพื้นที่ที่ไม่ได้เรียงลำดับ ข้อมูลทั้งหมดที่เล็กกว่าองค์ประกอบอ้างอิงถูกวางไว้ในช่วงเวลาหนึ่งและข้อมูลทั้งหมดที่ใหญ่กว่าองค์ประกอบอ้างอิงจะถูกวางไว้ในช่วงเวลาอื่น หลังจากการดำเนินการพาร์ติชันเสร็จสมบูรณ์ตำแหน่งขององค์ประกอบอ้างอิงคือตำแหน่งที่ควรจะเป็นหลังจากการเรียงลำดับสุดท้าย
การเรียกซ้ำ: เรียกอัลกอริทึมซ้ำในขั้นตอนที่ 1 และขั้นตอนที่ 2 เป็นครั้งแรกจนกว่าจะมีองค์ประกอบเดียวที่เหลืออยู่ในช่วงเวลาที่ไม่ได้เรียงลำดับทั้งหมด
ตอนนี้มาพูดคุยเกี่ยวกับวิธีการใช้งานทั่วไป (ไม่มีการใช้อัลกอริทึมในสถานที่)
ฟังก์ชั่น Quicksort (arr) {ถ้า (arr.length <= 1) return; // โปรดเกณฑ์มาตรฐานหลักที่อยู่ใกล้กับกลางอาร์เรย์ตัวเลขคี่และตัวเลขจะมีค่าแตกต่างกัน แต่ฉันไม่คิดอย่างนั้น แน่นอนคุณสามารถเลือกหมายเลขแรกหรือหมายเลขสุดท้ายเป็นเกณฑ์มาตรฐานและไม่มีคำอธิบายมากเกินไปที่นี่ var pivotindex = math.floor (arr.length/2); var pivot = arr.splice (pivotindex, 1) [0]; (var i = 0; i <arr.length; i ++) {console.log ('the' + (i + 1) + 'การดำเนินการพาร์ติชัน:'); // มีน้อยกว่าการอ้างอิงใส่ในช่วงซ้ายมากกว่าการอ้างอิง {right.push (arr [i]); console.log ('ขวา:' + (arr [i]))}} // ตัวดำเนินการ concat ถูกนำมาใช้ที่นี่เพื่อประกบช่วงซ้ายการอ้างอิงและช่วงเวลาที่ถูกต้องลงในอาร์เรย์ใหม่ // Quicksort (ขวา));} var arr = [14, 3, 15, 7, 2, 76, 11]; console.log (Quicksort (arr));/** เมื่อฐานคือ 7 พาร์ติชันแรกได้มาพร้อมกับสองส่วนย่อยและด้านซ้าย [2] การเรียงลำดับทั้งหมดของชุดย่อยด้านซ้ายจะสิ้นสุด* ด้วยการอ้างอิงเป็น 76 ชุดย่อยที่ถูกต้องถูกแบ่งออกและจัดเรียงให้ได้รับ [14, 15, 11] 76* ในเวลานี้, ข้างต้น [14, 15, 11] ถูกแบ่งและจัดเรียงตาม [14, 15, 11] ข้างต้น [14, 11] ถูกแบ่งและจัดเรียงไปตาม [11] ด้านบนถูกแบ่งและจัดเรียงเป็นฐาน 11, 11 [14]*มีเพียงองค์ประกอบเดียวที่เหลืออยู่ในช่วงเวลาที่ไม่ได้เรียงลำดับทั้งหมดและสิ้นสุดการเรียกซ้ำ **/ผ่านการดีบักเบรกพอยต์สามารถรับผลลัพธ์ได้
ข้อเสีย:
มันต้องใช้พื้นที่เก็บข้อมูลเพิ่มเติมของΩ (n) ซึ่งไม่ดีเท่ากับการเรียงลำดับ ในสภาพแวดล้อมการผลิตจำเป็นต้องมีพื้นที่หน่วยความจำเพิ่มเติมส่งผลกระทบต่อประสิทธิภาพ
ในเวลาเดียวกันหลายคนคิดว่าข้างต้นเป็นประเภทที่รวดเร็วจริง ดังนั้นด้านล่างจึงจำเป็นต้องแนะนำการเรียงลำดับอย่างรวดเร็วของอัลกอริทึมในสถานที่
สำหรับข้อมูลเกี่ยวกับอัลกอริทึมในแหล่งกำเนิดโปรดดูวิกิพีเดีย นักเรียนที่อยู่ภายใต้กำแพงคล้ายกับ Baidu
ในสถานที่
โดยทั่วไปแล้วการเรียงลำดับอย่างรวดเร็วจะถูกนำไปใช้กับการเรียกซ้ำ สิ่งที่สำคัญที่สุดคือฟังก์ชั่นการแบ่งส่วนพาร์ติชันซึ่งแบ่งอาร์เรย์ออกเป็นสองส่วนหนึ่งมีขนาดเล็กกว่าเดือยและอื่น ๆ มีขนาดใหญ่กว่าเดือย หลักการเฉพาะได้รับการกล่าวถึงข้างต้น
ฟังก์ชั่น Quicksort (arr) {// swap function swap (arr, a, b) {var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} // พาร์ติชันพาร์ติชัน (arr, ซ้าย, ขวา) = arr [ขวา];/*** เมื่อจัดเก็บองค์ประกอบที่เล็กกว่าเดือยพวกเขาจะอยู่ถัดจากองค์ประกอบก่อนหน้านี้มิฉะนั้นองค์ประกอบที่เก็บไว้ในช่องว่างอาจมีขนาดใหญ่กว่าเดือยดังนั้นตัวแปร storeindex จะถูกประกาศและเริ่มต้นเพื่อเก็บองค์ประกอบที่เล็กกว่า pivot ถัดจากกัน */var storeIndex = ซ้าย; สำหรับ (var i = ซ้าย; i <ขวา; i ++) {ถ้า (arr [i] <pivot) {/*** สำรวจอาร์เรย์และค้นหาองค์ประกอบที่เล็กกว่า pivot (องค์ประกอบที่ใหญ่กว่า pivot จะถูกข้าม) Swapped*/swap (arr, storeindex, i); storeIndex ++;}} // ในที่สุด: สลับเดือยไปที่ storeIndex, วางองค์ประกอบเบนช์มาร์กที่ตำแหน่งที่ถูกต้องขั้นสุดท้าย (arr, ขวา, storeIndex); storeIndex;} 1); เรียงลำดับ (arr, storeindex + 1, ขวา);} sort (arr, 0, arr.length - 1); return arr;} console.log (Quicksort ([8, 4, 90, 8, 34, 67, 1, 26, 17]));การเพิ่มประสิทธิภาพพาร์ติชัน
นักเรียนที่ระมัดระวังที่นี่อาจถามว่าจะมีประสิทธิภาพที่แตกต่างกันหรือไม่เมื่อเลือกเกณฑ์มาตรฐานที่แตกต่างกัน คำตอบคือใช่ แต่เพราะฉันเป็นคนส่วนหน้าและไม่รู้เกี่ยวกับอัลกอริทึมมากนักดังนั้นหลุมนี้จึงถูกทิ้งให้คนที่มีอำนาจเติมเต็ม
ความซับซ้อน
การเรียงลำดับอย่างรวดเร็วเป็นอัลกอริทึมการเรียงลำดับที่เร็วที่สุดและความซับซ้อนของเวลาคือ O (log n)
ในสถานการณ์เฉลี่ยลำดับของรายการ n ต้องใช้การเปรียบเทียบ (n log n) ในกรณีที่เลวร้ายที่สุดจำเป็นต้องมีการเปรียบเทียบ (N2)
https://github.com/lyz0106/
ข้างต้นเป็นวิธีการเรียงลำดับอย่างรวดเร็วของการใช้งาน JavaScript แนวคิดในสถานที่ที่แนะนำโดยบรรณาธิการ ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน หากคุณมีคำถามใด ๆ โปรดฝากข้อความถึงฉัน บรรณาธิการจะตอบกลับคุณทันเวลา ขอบคุณมากสำหรับการสนับสนุนเว็บไซต์ Wulin Network!