ความซับซ้อนของเวลา
ค่าเฉลี่ย: O (NLGN)
กรณีที่เลวร้ายที่สุด: o (n*n) เกิดขึ้นเมื่อข้อมูลอยู่ในสถานะการเรียงลำดับแล้ว
1. เลือกค่า A [i] จากข้อมูลเป็นข้อมูลอ้างอิง
2. การใช้ [i] เป็นข้อมูลอ้างอิงแบ่งข้อมูลออกเป็น 2 ส่วน: P1 และ P2 ข้อมูลทั้งหมดในp1≤a [i] ข้อมูลทั้งหมดใน p2> a [i] และข้อมูลจะกลายเป็น {{p1} {a [i]} {p2}}}
3. ทำซ้ำขั้นตอนข้างต้นด้วย P1 และ P2 จนกระทั่งเหลือเพียง 1 ข้อมูลในแต่ละส่วน
4. ข้อมูลเรียงลำดับตามลำดับจากน้อยไปมาก
ตัวอย่างพื้นฐาน:
ข้อมูลดิบ:
{3, 9, 8, 5, 2, 1, 6} ขั้นตอนที่ 1: เลือกข้อมูลแรก: 3
ขั้นตอนที่ 2: แบ่งข้อมูลออกเป็น 2 ส่วนด้านซ้ายคือ≤3และด้านขวามากกว่า> 3:
{2,1} {3} {9,8,5,6} ขั้นตอนที่ 3: ทำซ้ำขั้นตอนข้างต้นสำหรับแต่ละส่วนจนกว่าจะมีเพียง 1 ข้อมูลที่เหลือในแต่ละส่วน:
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} {9} ขั้นตอนที่ 4: ข้อมูลถูกเรียงลำดับตามลำดับจากน้อยไปมาก:
{1} {2} {3} {5} {6} {8} {9}ข้อมูลในโปรแกรมมักจะถูกเก็บไว้ในอาร์เรย์ การใช้อาร์เรย์ของประเภท int เป็นตัวอย่างคุณสามารถเขียนขั้นตอนข้างต้นลงในต้นแบบฟังก์ชัน Quicksort:
Quicksort (int เริ่มต้น, int end) {// เริ่มต้นคือค่าดัชนีของข้อมูลแรกของอาร์เรย์สิ้นสุดคือค่าดัชนีของข้อมูลสุดท้ายของอาร์เรย์ +1 // หากมีเพียง 1 ข้อมูลหรือ 0 ข้อมูล int p = ใน [เริ่มต้น]; // p เป็นข้อมูลอ้างอิงที่เลือกเลือกข้อมูลแรก int a = เริ่ม +1; // a เป็นค่าดัชนีของการหารข้อมูล 2 ส่วนบรรทัด int b = a; // b คือค่าดัชนีของข้อมูลที่จะเปรียบเทียบสำหรับ (; b <end; b ++) {// เปรียบเทียบข้อมูลในอาร์เรย์ที่มีข้อมูลอ้างอิงในลำดับถ้า (ใน [b] <p) {// ถ้าข้อมูล <ข้อมูลอ้างอิง ดำเนินการต่อ;} // หากข้อมูลอยู่ทางซ้ายแล้วมันจะไม่ย้าย int temp = ใน [a]; // ย้ายข้อมูลไปทางซ้ายใน [a] = ใน [b]; ใน [b] = อุณหภูมิ; A ++; // ย้ายบรรทัดการหารขวา}} ใน [เริ่มต้น] = ใน [a-1]; // whike ค่าอ้างอิงไปที่กลาง 2 ชุดข้อมูลใน [a-1] = p; ถ้า (A-1> เริ่มต้น) {// หากมีข้อมูลทางด้านซ้ายให้ทำซ้ำขั้นตอนด้านบน QuickSort (เริ่มต้น A); } if (end-1> a) {// หากมีข้อมูลทางด้านขวาให้ทำซ้ำขั้นตอนด้านบน QuickSort (A, end); } กลับ; // หากไม่มีข้อมูล} การเพิ่มประสิทธิภาพอัลกอริทึม
อัลกอริทึมการเรียงลำดับอย่างรวดเร็วข้างต้นสามารถกล่าวได้ว่าเป็นการเรียงลำดับขั้นพื้นฐานที่รวดเร็วที่สุดเพราะไม่คำนึงถึงข้อมูลอินพุตใด ๆ อย่างไรก็ตามมันเป็นเรื่องง่ายที่จะค้นหาข้อบกพร่องของอัลกอริทึมนี้: นี่คือเมื่อข้อมูลอินพุตของเราได้รับคำสั่งโดยทั่วไปหรือสั่งซื้ออย่างสมบูรณ์อัลกอริทึมจะลดลงในการเรียงลำดับฟองไม่ได้อีกต่อไป O (NN) แต่ o (n^2)
สาเหตุที่แท้จริงคือในการใช้งานรหัสของเราเราเริ่มจากอาร์เรย์แรกเท่านั้น ถ้าเราใช้ "สามหัว" นั่นคือค่ามัธยฐานของ arr [ต่ำ], arr [สูง], arr [(ต่ำ+สูง)/2] เป็นบันทึกเดือยประสิทธิภาพของการเรียงลำดับอย่างรวดเร็วในสถานการณ์ที่เลวร้ายที่สุดสามารถปรับปรุงได้อย่างมาก อย่างไรก็ตามเรายังไม่สามารถปรับปรุงประสิทธิภาพของมันเป็น O (n) ในกรณีที่สั่งอาร์เรย์ นอกจากนี้ยังมีวิธีการปรับปรุงประสิทธิภาพเวลาของการเรียงลำดับอย่างรวดเร็วในสถานการณ์ที่เลวร้ายที่สุดในระดับที่แตกต่างกัน
นอกจากนี้การเรียงลำดับอย่างรวดเร็วต้องใช้สแต็กแบบเรียกซ้ำซึ่งมักจะไม่ลึกมากและอยู่ในระดับบันทึก (n) อย่างไรก็ตามหากความยาวของทั้งสองอาร์เรย์แบ่งออกเป็นครั้งเดียวไม่สมดุลอย่างรุนแรงในกรณีที่เลวร้ายที่สุดความลึกของสแต็กจะเพิ่มเป็น o (n) ในเวลานี้ความซับซ้อนเชิงพื้นที่ที่นำโดยพื้นที่สแต็กไม่สามารถเพิกเฉยได้ หากมีการเพิ่มค่าใช้จ่ายของตัวแปรเพิ่มเติมมันอาจถึงความซับซ้อนของอวกาศ O (n^2) ที่น่ากลัวที่นี่ ดังนั้นความซับซ้อนเชิงพื้นที่ที่เลวร้ายที่สุดของการเรียงลำดับอย่างรวดเร็วจึงไม่ใช่ค่าคงที่และอาจไม่อยู่ในระดับเดียวกัน
เพื่อแก้ปัญหานี้เราสามารถเปรียบเทียบความยาวของปลายหลังจากแต่ละส่วนและเรียงลำดับลำดับสั้น ๆ ก่อน (วัตถุประสงค์คือการสิ้นสุดสแต็คเหล่านี้ก่อนเพื่อเพิ่มพื้นที่ว่าง) ซึ่งสามารถลดความลึกสูงสุดกลับไปสู่ระดับ O (N)
นี่คือแนวคิดการเพิ่มประสิทธิภาพสามประการสำหรับการเรียงลำดับอย่างรวดเร็ว:
สำหรับอาร์เรย์ขนาดเล็กสามารถใช้การเรียงลำดับเพื่อหลีกเลี่ยงการโทรแบบเรียกซ้ำได้ ตัวอย่างเช่นเมื่อ (hi <= lo + m) คุณสามารถไปที่แทรกเรียง
ใช้ค่ามัธยฐานของ subarray เพื่อหั่นอาเรย์ ซึ่งส่งผลให้การหั่นขึ้นดีขึ้น แต่ค่าใช้จ่ายในการคำนวณค่ามัธยฐาน
หากอาร์เรย์มีองค์ประกอบซ้ำจำนวนมากสามารถใช้การหั่นสามทางได้ แบ่งอาร์เรย์ออกเป็นสามส่วนซึ่งสอดคล้องกับองค์ประกอบอาร์เรย์ที่เล็กกว่าเท่ากับและมากกว่าองค์ประกอบการหั่นตามลำดับ การใช้งานรหัสมีดังนี้:
โมฆะคงที่ส่วนตัว sort1 (int [] a, int lo, int hi) {ถ้า (hi <= lo) กลับมา; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; ในขณะที่ (i <= gt) {ถ้า (a [i] <v) {swap (a, lt ++, i ++); } อื่นถ้า (a [i]> v) {swap (a, i, gt--); } else {i ++; } sort (a, lo, lt - 1); เรียงลำดับ (a, gt + 1, hi); -