อัลกอริทึม QuickSort ใน Javaสคริปต์พร้อมตัวอย่าง

Quick Sort คืออะไร?

จัดเรียงด่วน เป็นอัลกอริธึมการเรียงลำดับแบบเปรียบเทียบที่ปฏิบัติตาม หารและพิชิต วิธีการนี้เลือกองค์ประกอบหนึ่งเป็นตัวหลัก แบ่งอาร์เรย์ออกเป็นส่วนที่เก็บค่าที่เล็กกว่าตัวหลักและส่วนที่เก็บค่าที่ใหญ่กว่า จากนั้นใช้วิธีการเดียวกันกับแต่ละส่วนจนกว่าอาร์เรย์ทั้งหมดจะถูกจัดเรียงอย่างเป็นระเบียบ

Quick Sort เป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่ใช้กันอย่างแพร่หลายที่สุดในทุกภาษาโปรแกรม หากคุณเขียน Javaต้นฉบับคุณอาจเคยใช้ฟังก์ชันในตัวไปแล้ว เรียงลำดับ () เนื่องจากวิธีการนี้ คุณอาจสงสัยว่าทำไมการเรียนรู้การใช้งาน Quick Sort แยกต่างหากจึงคุ้มค่า เพื่อตอบคำถามนั้น คุณต้องรู้ก่อนว่าการเรียงลำดับหมายถึงอะไร และการเรียงลำดับเริ่มต้นใน Quick Sort คืออะไร Javaสคริปต์ทำได้จริง ๆ

คุณสมบัติหลักสามประการที่กำหนด Quick Sort ได้แก่:

• ในสถานที่: มันจัดเรียงใหม่จากต้นฉบับ แถว และไม่ได้จัดสรรอาร์เรย์ที่สองที่มีขนาดเท่ากัน
• เรียกซ้ำ: แต่ละพาร์ติชันจะสร้างช่วงย่อยสองช่วงที่เรียงลำดับตามฟังก์ชันเดียวกัน
• ไม่เสถียร: องค์ประกอบสองอย่างที่มีคีย์เท่ากัน อาจมีลำดับสัมพัทธ์ที่แตกต่างกันไปจากเดิม

การเรียงลำดับคืออะไร?

การเรียงลำดับหมายถึงการจัดเรียงองค์ประกอบตามลำดับที่กำหนด คุณน่าจะเคยเจอเรื่องนี้ในโรงเรียนมาแล้ว เช่น การเรียงตัวเลขจากน้อยไปมาก จากน้อยไปมาก เรียงลำดับ และเรียงจากใหญ่ที่สุดไปเล็กที่สุด คือ จากมากไปน้อย การเรียงลำดับไม่จำกัดเฉพาะตัวเลขเท่านั้น สามารถเรียงลำดับข้อความตามตัวอักษร วันที่ตามลำดับเวลา และวัตถุตามฟิลด์ใดก็ได้ที่คุณเลือก เช่น ราคาหรือคะแนน

การเรียงลำดับมีความสำคัญ เพราะข้อมูลที่เรียงลำดับแล้วจะช่วยให้การทำงานเร็วขึ้น การค้นหาแบบไบนารีใช้เวลา O(log n) แต่เฉพาะกับข้อมูลที่เรียงลำดับแล้วเท่านั้น การลบข้อมูลซ้ำ การค้นหาช่วง การจัดอันดับ และการรวมข้อมูล จะทำงานได้เร็วขึ้นมากเมื่อข้อมูลถูกเรียงลำดับ ซึ่งเป็นเหตุผลว่าทำไมทุกภาษาจึงมีฟังก์ชันการเรียงลำดับอย่างน้อยหนึ่งฟังก์ชัน

การเรียงลำดับเริ่มต้นใน Javaต้นฉบับ

ดังกล่าวก่อนหน้านี้, Javaสคริปต์ให้ เรียงลำดับ ()ลองใช้อาร์เรย์ขนาดเล็ก เช่น [5,3,7,6,2,9] ที่คุณต้องการเรียงลำดับจากน้อยไปมาก เรียกใช้ เรียงลำดับ () บนอาร์เรย์ดูเหมือนว่าจะทำเช่นนั้นจริงๆ

ภาพหน้าจอข้างต้นแสดงคอนโซลของเบราว์เซอร์ที่พิมพ์อาร์เรย์ที่เรียงลำดับแล้ว นี่คือโค้ดเดียวกัน:

var items = [5, 3, 7, 6, 2, 9];
console.log(items.sort());

Output:

[ 2, 3, 5, 6, 7, 9 ]

ผลลัพธ์นั้นถูกต้อง แต่เป็นเพียงความบังเอิญเท่านั้น Array.prototype.sort() จะแปลงทุกองค์ประกอบให้เป็นสตริง แล้วเปรียบเทียบสตริงเหล่านั้น เว้นแต่คุณจะระบุฟังก์ชันเปรียบเทียบ ค่าทุกค่าในอาร์เรย์นี้เป็นตัวเลขหลักเดียว ดังนั้นลำดับของสตริงจึงตรงกับลำดับตัวเลข หากเปลี่ยนข้อมูล ภาพลวงตาก็จะแตกสลาย

var prices = [10, 9, 1, 100, 25];
console.log(prices.sort());                              // string comparison
console.log(prices.sort(function (a, b) { return a - b; })); // numeric comparison

Output:

[ 1, 10, 100, 25, 9 ]
[ 1, 9, 10, 25, 100 ]

ฟังก์ชัน sort() ใช้อัลกอริทึมใด?

ข้อกำหนดไม่ได้ระบุชื่ออัลกอริทึม ดังนั้นแต่ละเอนจิ้นจึงเลือกใช้อัลกอริทึมของตนเอง เอนจิ้นสมัยใหม่ทั้งหมดใช้อัลกอริทึมแบบผสาน (merge-based algorithm):

• V8 (Chrome, Edge, Node.js) ได้ใช้งานแล้ว ทิมซอร์ต ตั้งแต่ V8 7.0 เป็นต้นมา จัดส่งในสี Chrome 70
• สไปเดอร์มังกี้ (Firefox) ใช้ รวมการจัดเรียง.
• Javaสคริปต์คอร์ (ซาฟารี) ยังใช้ รวมการจัดเรียง.

ตั้งแต่ ES2019 เป็นต้นมา ภาษาดังกล่าวรับประกันว่า sort() is มั่นคงซึ่งทำให้ไม่สามารถใช้ Quick Sort แบบธรรมดาภายในเอนจินได้ การเรียงลำดับแบบผสานต้องการหน่วยความจำเสริม O(n) และต้องเรียกใช้เมธอดของคุณ Javaใช้สคริปต์เปรียบเทียบสำหรับทุกการเปรียบเทียบ Quick Sort แบบเขียนด้วยมือจะเปรียบเทียบตัวเลขโดยตรงและเรียงลำดับในตำแหน่งเดิม จึงสามารถจัดการกับอาร์เรย์ตัวเลขขนาดใหญ่ได้ดีกว่า การเรียงลำดับจำนวนเต็มสุ่ม 1,000,000 ตัวบน Node.js 22 ใช้เวลาประมาณ ms 100 โดยใช้การเรียงลำดับด่วนด้านล่างและโดยประมาณ ms 210 สีสดสวย sort((a, b) => a - b).

ดังนั้น Quick Sort จึงคุ้มค่าที่จะเขียนเมื่อคุณต้องการการเรียงลำดับแบบ in-place การควบคุมหน่วยความจำอย่างเข้มงวด หรือเพียงแค่ต้องการความเข้าใจอย่างถ่องแท้ว่าการเรียงลำดับทำงานอย่างไร มาดูกลไกโดยละเอียดกัน

การจัดเรียงด่วนทำงานอย่างไร?

Quick Sort ทำซ้ำการดำเนินการหลักหนึ่งครั้ง เรียกว่า การแยกโดยลดช่วงการวัดลงเรื่อยๆ นี่คือขั้นตอนตามลำดับ:

1. หา เดือย องค์ประกอบในอาร์เรย์
2. เริ่มวางตัวชี้เมาส์ซ้ายที่องค์ประกอบแรกของช่วงข้อมูล
3. เริ่มวางตัวชี้เมาส์ขวาที่องค์ประกอบสุดท้ายของช่วงข้อมูล
4. เปรียบเทียบค่าที่อยู่ทางซ้ายสุดของตัวชี้กับค่าหลัก ถ้าค่าทางซ้ายสุดน้อยกว่าค่าหลัก ให้เลื่อนตัวชี้ไปทางขวาหนึ่งขั้น ทำเช่นนี้ต่อไปจนกว่าค่าทางซ้ายสุดจะมีค่ามากกว่าหรือเท่ากับค่าหลัก
5. เปรียบเทียบค่าขององค์ประกอบทางด้านขวากับค่าหลัก หากค่าขององค์ประกอบทางด้านขวามากกว่าค่าหลัก ให้เลื่อนตัวชี้ทางด้านขวาไปทางซ้ายหนึ่งขั้น ทำเช่นนี้ต่อไปจนกว่าค่าขององค์ประกอบทางด้านขวาจะน้อยกว่าหรือเท่ากับค่าหลัก
6. ถ้าตัวชี้ด้านซ้ายยังคงน้อยกว่าหรือเท่ากับตัวชี้ด้านขวา ให้สลับตำแหน่งขององค์ประกอบทั้งสอง
7. เพิ่มตัวชี้ทางซ้ายและลดตัวชี้ทางขวา
8. ถ้าดัชนีด้านซ้ายยังคงน้อยกว่าหรือเท่ากับดัชนีด้านขวา ให้ทำซ้ำตั้งแต่ขั้นตอนที่ 4 มิฉะนั้น ให้ส่งคืนดัชนีของตัวชี้ด้านซ้าย

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

วิธีการกำหนดองค์ประกอบหลัก (Pivot Element)

การเลือกจุดหมุน (pivot) คือการตัดสินใจเพียงอย่างเดียวที่ทำให้การเรียงลำดับแบบ Quick Sort เร็วขึ้นแตกต่างจากการเรียงลำดับที่ช้าลง หากคุณเลือกจุดหมุนเสมอ เป็นครั้งแรก การใช้ element ในอาร์เรย์ที่เรียงลำดับแล้ว จะทำให้เกิดการแบ่งที่แย่ที่สุดเท่าที่จะเป็นไปได้ นั่นคือ ด้านหนึ่งว่างเปล่า และอีกด้านหนึ่งมี element ที่เหลืออยู่ทั้งหมด ซึ่งจะทำให้ขั้นตอนวิธีมีประสิทธิภาพเป็น O(n²) การนำ element มาใช้ กลาง การใช้ element (ความยาวของอาร์เรย์หารด้วยสอง) ช่วยหลีกเลี่ยงข้อผิดพลาดดังกล่าวสำหรับข้อมูลที่เรียงลำดับแล้วและข้อมูลที่เรียงลำดับย้อนกลับ ซึ่งเป็นเหตุผลว่าทำไมโค้ดด้านล่างจึงใช้ element นี้

กลยุทธ์การเปลี่ยนแกนหมุนที่พบบ่อย:

• องค์ประกอบแรกหรือองค์ประกอบสุดท้าย: เขียนโค้ดง่ายที่สุด แต่มีประสิทธิภาพ O(n²) สำหรับข้อมูลที่เรียงลำดับแล้ว
• องค์ประกอบตรงกลาง: ค่าเริ่มต้นที่ดีที่จัดการกับอาร์เรย์ที่เรียงลำดับแล้วและเรียงลำดับย้อนกลับได้ในเวลา O(n log n)
• องค์ประกอบสุ่ม: ทำให้ไม่สามารถสร้างข้อมูลป้อนเข้าในกรณีที่เลวร้ายที่สุดล่วงหน้าได้
• ค่ามัธยฐานของทั้งสาม: ใช้ค่ามัธยฐานของค่าแรก ค่ากลาง และค่าสุดท้าย ซึ่งเป็นตัวเลือกมาตรฐานในไลบรารีการผลิต

ต่อไป มาลองใช้ Quick Sort กับอาร์เรย์กัน [5,3,7,6,2,9].

ขั้นตอนที่ 1: จุดหมุนคือองค์ประกอบตรงกลาง โดยที่ซ้าย = 0 และขวา = 5 Math.floor((5 + 0) / 2) ให้ค่าดัชนี 2 ดังนั้นค่า pivot คือ 7.

ขั้นตอนที่ 2: เริ่มวางตัวชี้ที่ปลายทั้งสองของอาร์เรย์ ตัวชี้ด้านซ้ายอยู่ที่ดัชนี 0 (ค่า ) 5) และตัวชี้ด้านขวาอยู่ที่ดัชนี 5 (ค่า 9).

ขั้นตอนที่ 3: เปรียบเทียบค่าทางซ้ายกับค่าหลัก (pivot) 5 < 7 ดังนั้นเลื่อนไปทางขวาไปที่ดัชนี 1 3 < 7 ดังนั้นเลื่อนไปทางขวาไปที่ดัชนี 2 ค่าที่นั่นคือ 7 ซึ่งไม่น้อยกว่าค่าหลัก ดังนั้นตัวชี้ทางซ้ายจึงหยุดอยู่ที่ดัชนี 2

ขั้นตอนที่ 4: เปรียบเทียบค่าด้านขวากับค่าหลัก 9 > 7 ดังนั้นเลื่อนไปทางซ้ายไปยังดัชนี 4 ค่าที่นั่นคือ 2 ซึ่งไม่มากกว่าค่าหลัก ดังนั้นตัวชี้ด้านขวาจึงหยุดอยู่ที่ดัชนี 4

ขั้นตอนที่ 5: ดัชนีด้านซ้าย (2) น้อยกว่าหรือเท่ากับดัชนีด้านขวา (4) ดังนั้นให้สลับค่าทั้งสอง อาร์เรย์จะกลายเป็น [5,3,2,6,7,9].

ขั้นตอนที่ 6: เลื่อนตัวชี้ทั้งสองตัวเข้ามาด้านในหนึ่งขั้น ตอนนี้ตัวชี้ด้านซ้ายอยู่ที่ดัชนี 3 และตัวชี้ด้านขวาอยู่ที่ดัชนี 3

ขั้นตอนที่ 7: ทำการสแกนซ้ำ ค่าที่ดัชนี 3 คือ 6 และ 6 < 7 ดังนั้นตัวชี้ด้านซ้ายจึงเลื่อนไปยังดัชนี 4 ค่าที่ดัชนี 3 ไม่มากกว่าค่าหลัก ดังนั้นตัวชี้ด้านขวาจึงยังคงอยู่ที่ดัชนี 3

ขั้นตอนที่ 8: ดัชนีด้านซ้าย (4) ตอนนี้มากกว่าดัชนีด้านขวา (3) ดังนั้นลูปจึงสิ้นสุดและฟังก์ชันจะส่งคืนค่า 4ค่าทุกอย่างก่อนดัชนีที่ 4 จะมีค่าน้อยกว่าหรือเท่ากับค่า pivot และค่าทุกอย่างตั้งแต่ดัชนีที่ 4 เป็นต้นไปจะมีค่ามากกว่าหรือเท่ากับค่า pivot

จากคำแนะนำนั้น คุณจำเป็นต้องเขียนโค้ดสำหรับสองการดำเนินการ: สลับping สององค์ประกอบและการแบ่งช่วง

Code เพื่อสลับสอง Numbers in Javaต้นฉบับ

ดังที่ภาพหน้าจอของตัวแก้ไขด้านบนแสดงให้เห็น ตัวช่วยสลับค่าจะใช้ตัวแปรชั่วคราวเพื่อสลับค่าที่สองดัชนี มันเปลี่ยนแปลงอาร์เรย์โดยตรงและไม่ส่งค่าใด ๆ กลับมา

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

var demo = [5, 3, 7, 6, 2, 9];
swap(demo, 0, 5);
console.log(demo);

Output:

[ 9, 3, 7, 6, 2, 5 ]

Code เพื่อดำเนินการแบ่งพาร์ติชัน

โค้ดในภาพหน้าจอด้านบนจะแปลงขั้นตอนที่ 1 ถึง 8 ให้เป็นฟังก์ชัน โดยสองส่วนภายในนั้น ลูป เลื่อนตัวชี้ไปข้างหน้า if บล็อกจะทำการสลับ และฟังก์ชันจะส่งคืนดัชนีการแบ่ง

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swap two elements
            i++;
            j--;
        }
    }
    return i;
}

var items = [5, 3, 7, 6, 2, 9];
var index = partition(items, 0, items.length - 1);
console.log(items);
console.log(index);

Output:

[ 5, 3, 2, 6, 7, 9 ]
4

ผลลัพธ์ตรงกับคำแนะนำในคู่มือทุกประการ: หลังจากผ่านการแบ่งพาร์ติชันหนึ่งรอบ อาร์เรย์จะเป็น [5,3,2,6,7,9] และดัชนีการแบ่งที่ส่งคืนคือ 4

ดำเนินการเรียกซ้ำ Operaการ

เมื่อการแบ่งส่วนได้ผลลัพธ์เป็นดัชนีการแบ่งแล้ว ให้ใช้ดัชนีนั้นในการแบ่งช่วงและเรียกใช้ Quick Sort กับแต่ละครึ่ง นั่นคือเหตุผลที่เรียกว่าอัลกอริทึมแบบแบ่งและพิชิต (Divide and Conquer) การเรียกซ้ำจะดำเนินต่อไปจนกว่าช่วงย่อยทุกช่วงจะมีองค์ประกอบเพียงหนึ่งเดียว ซึ่งในจุดนั้นอาร์เรย์ทั้งหมดจะถูกเรียงลำดับแล้ว

หมายเหตุ อัลกอริทึม Quick Sort ทำงานกับอาร์เรย์เดียวกันตลอดกระบวนการ ไม่มีการสร้างอาร์เรย์ใหม่ในระหว่างกระบวนการ ซึ่งทำให้มันเป็นอัลกอริทึมแบบ in-place

งั้นคุณเรียก... พาร์ติชัน () ฟังก์ชันที่อธิบายไว้ข้างต้น และใช้ค่าที่ส่งคืนเพื่อแยก แถว แบ่งออกเป็นส่วนๆ นี่คือโค้ดที่ทำเช่นนั้น:

โปรดสังเกตเงื่อนไขการป้องกันสองข้อที่ไฮไลต์ไว้ในภาพหน้าจอ left < index - 1 ยืนยันว่าอย่างน้อยสององค์ประกอบยังคงอยู่ทางด้านซ้าย และ index < right ยืนยันผลลัพธ์เดียวกันสำหรับด้านขวา หากไม่มีตัวป้องกันเหล่านั้น ฟังก์ชันจะเรียกตัวเองซ้ำไปเรื่อย ๆ ในช่วงที่มีองค์ประกอบเดียว

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var items = [5, 3, 7, 6, 2, 9];
var result = quickSort(items, 0, items.length - 1);
console.log(result);

Output:

[ 2, 3, 5, 6, 7, 9 ]

การจัดเรียงด่วนแบบสมบูรณ์ Code

การนำส่วนประกอบการสลับ การแบ่งส่วน และการเรียกซ้ำมารวมกัน จะได้การใช้งานที่สมบูรณ์:

var items = [5, 3, 7, 6, 2, 9];

function swap(items, leftIndex, rightIndex) {
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)], // middle element
        i       = left,  // left pointer
        j       = right; // right pointer
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j); // swapping two elements
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); // index returned from partition
        if (left < index - 1) { // more elements on the left side of the pivot
            quickSort(items, left, index - 1);
        }
        if (index < right) { // more elements on the right side of the pivot
            quickSort(items, index, right);
        }
    }
    return items;
}

// first call to quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

Output:

[ 2, 3, 5, 6, 7, 9 ]

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

ความซับซ้อนด้านเวลาและพื้นที่ของการเรียงลำดับแบบเร็ว (Quick Sort)

การแบ่งพาร์ติชันแต่ละครั้งจะเข้าถึงแต่ละองค์ประกอบในช่วงหนึ่งครั้ง ดังนั้นการแบ่งพาร์ติชันแต่ละครั้งจึงมีค่าใช้จ่าย O(n) ค่าใช้จ่ายทั้งหมดจึงขึ้นอยู่กับว่าสามารถแบ่งอาร์เรย์ได้กี่ครั้งก่อนที่ช่วงจะกลายเป็นเรื่องที่ไม่สำคัญ

ความซับซ้อนของพื้นที่จัดเก็บข้อมูลคือ O(log n) สำหรับเวอร์ชันแบบ in-place นี้ ไม่มีการจัดสรรอาร์เรย์ตัวที่สอง ดังนั้นหน่วยความจำส่วนเกินเพียงอย่างเดียวคือสแต็กการเรียกซ้ำ และการแบ่งแบบสมดุลจะทำให้สแต็กนั้นมีความลึกประมาณ log₂(n) เฟรม ในกรณีที่เลวร้ายที่สุด สแต็กจะเติบโตเป็น O(n) เฟรม ซึ่งเป็นเหตุผลว่าทำไมอาร์เรย์ขนาดใหญ่มากจึงสามารถทำให้สแต็กการเรียกเกินขีดจำกัดได้

ตัวเลขสองตัวนี้ทำให้เห็นภาพชัดเจนขึ้น การเรียงลำดับค่าสุ่ม 4,096 ค่าด้วยโค้ดข้างต้นใช้การเปรียบเทียบประมาณ 65,000 ครั้ง เทียบกับค่า n·log₂(n) ทางทฤษฎีที่ 49,152 และการเรียกซ้ำที่ลึกที่สุดใช้เฟรม 24 เฟรม ในขณะที่ log₂(4096) คือ 12 ตัวเลขทั้งสองอยู่ในช่วงค่าคงที่เล็กน้อยที่คาดหวังได้จากอัลกอริทึม O(n log n)

Quick Sort เทียบกับการเรียงลำดับแบบอื่นๆ Algorithms

Quick Sort ไม่ใช่ตัวเลือกเดียวที่เหมาะสมเสมอไป ตารางด้านล่างเปรียบเทียบ Quick Sort กับอัลกอริทึมอื่นๆ ที่คุณอาจพบเจอได้บ่อย เพื่อให้คุณสามารถเลือกอัลกอริทึมที่เหมาะสมกับข้อมูลของคุณได้

ในทางปฏิบัติ Quick Sort มักจะทำงานได้ดีกว่า เพราะลูปภายในกระชับและทำงานได้ดีในช่วงข้อมูลที่ต่อเนื่องกันและเป็นมิตรกับแคช เลือกใช้ Merge Sort เมื่อต้องการรับประกันขอบเขต O(n log n) หรือการเรียงลำดับที่เสถียร เลือกใช้ Heap Sort เมื่อหน่วยความจำมีจำกัดมาก และเลือกใช้ Insertion Sort สำหรับอาร์เรย์ขนาดเล็กมากหรือเกือบเรียงลำดับแล้ว ไลบรารีที่ใช้งานจริงมักจะผสมผสานกัน เช่น Introsort เริ่มต้นด้วย Quick Sort เปลี่ยนไปใช้ Heap Sort หากการเรียกซ้ำลึกเกินไป และจบด้วย Insertion Sort ในช่วงข้อมูลขนาดเล็ก

วิธีการเรียงลำดับวัตถุและสตริงอย่างรวดเร็ว

การใช้งานที่แสดงให้เห็นจนถึงตอนนี้เป็นการเปรียบเทียบค่ากับ < และ >ซึ่งจำกัดไว้เฉพาะตัวเลขเท่านั้น แอปพลิเคชันจริงจำเป็นต้องเรียงลำดับ วัตถุ โดยพิจารณาจากคุณสมบัติ สตริงเรียงตามตัวอักษร หรือวันที่เรียงตามลำดับเวลา วิธีแก้ไขคือย้ายการเปรียบเทียบไปไว้ในฟังก์ชันเรียกกลับ (callback) เหมือนกับฟังก์ชันในตัว sort() ไม่

ตัวเปรียบเทียบจะรับค่าสองค่าและส่งคืนค่าลบเมื่อค่าแรกควรมาก่อน ค่าบวกเมื่อค่าที่สองควรมาก่อน และศูนย์เมื่อทั้งสองค่าเท่ากัน การแทนที่การเปรียบเทียบแบบตายตัวสองครั้งด้วยการเรียกใช้ตัวเปรียบเทียบจะทำให้ขั้นตอนวิธีนี้ทำงานได้กับข้อมูลทุกประเภท

function swap(items, i, j) {
    var temp = items[i];
    items[i] = items[j];
    items[j] = temp;
}

function partition(items, left, right, compare) {
    var pivot = items[Math.floor((right + left) / 2)],
        i     = left,
        j     = right;
    while (i <= j) {
        while (compare(items[i], pivot) < 0) { i++; }
        while (compare(items[j], pivot) > 0) { j--; }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

function quickSort(items, left, right, compare) {
    if (left >= right) { return items; } // nothing left to split
    var index = partition(items, left, right, compare);
    if (left < index - 1) { quickSort(items, left, index - 1, compare); }
    if (index < right) { quickSort(items, index, right, compare); }
    return items;
}

function sort(items, compare) {
    compare = compare || function (a, b) { return a < b ? -1 : a > b ? 1 : 0; };
    return quickSort(items, 0, items.length - 1, compare);
}

var numbers = [10, 9, 1, 100, 25];
console.log(sort(numbers, function (a, b) { return a - b; }));

var names = ["Priya", "arun", "Bala", "chetan"];
console.log(sort(names, function (a, b) {
    return a.toLowerCase().localeCompare(b.toLowerCase());
}));

var employees = [
    { name: "Arun",   salary: 52000 },
    { name: "Bala",   salary: 41000 },
    { name: "Chetan", salary: 68000 }
];
console.log(sort(employees, function (a, b) { return a.salary - b.salary; }));

Output:

[ 1, 9, 10, 25, 100 ]
[ 'arun', 'Bala', 'chetan', 'Priya' ]
[
  { name: 'Bala', salary: 41000 },
  { name: 'Arun', salary: 52000 },
  { name: 'Chetan', salary: 68000 }
]

มีรายละเอียดสามประการที่ควรสังเกต ตัวป้องกันการเรียกซ้ำในตอนนี้คือ left >= rightซึ่งถูกต้องสำหรับช่วงใดๆ และไม่ขึ้นอยู่กับความยาวของอาร์เรย์ภายนอก การเปรียบเทียบสตริงใช้ localeCompare() เพื่อให้ตัวอักษรที่มีเครื่องหมายเน้นเสียงและตัวพิมพ์ใหญ่-เล็กได้รับการจัดการอย่างถูกต้อง แทนที่จะใช้รหัสจุดดิบ และเนื่องจาก Quick Sort ไม่เสถียร ข้อมูลที่มีเงินเดือนเท่ากันอาจสลับตำแหน่งกันได้ ดังนั้น หากลำดับเดิมมีความสำคัญสำหรับคุณ ให้เรียงลำดับโดยใช้คีย์ที่สองเพื่อตัดสินลำดับที่เท่ากัน

พร้อมที่จะก้าวต่อไปหรือยัง? เสริมสร้างรากฐานให้แข็งแกร่งยิ่งขึ้นด้วย Javaบทนำของบทภาพยนตร์ฝึกฝนกลไกการชี้ใน Javaลูปสคริปต์ทำงานผ่านขั้นตอนเพิ่มเติม ในทางปฏิบัติ Javaตัวอย่างโค้ดสคริปต์เปรียบเทียบการใช้งานใน เรียงลำดับการแทรก และ เรียงลำดับกองหรือเพิ่มประเภทคงที่ให้กับอัลกอริทึมนี้ด้วย TypeScript การอ้างอิง

คำถามที่พบบ่อย