การสัมภาษณ์เป็นลายลักษณ์อักษรมักเกี่ยวข้องกับอัลกอริทึมต่างๆ บทความนี้แนะนำอัลกอริทึมที่ใช้กันทั่วไปบางส่วนและดำเนินการใน JavaScript
1. แทรกการเรียงลำดับ
1) บทนำสู่อัลกอริทึม
คำอธิบายอัลกอริทึมของการแทรกการเรียงเป็นอัลกอริทึมการเรียงลำดับที่ง่ายและใช้งานง่าย มันทำงานได้โดยการสร้างลำดับที่สั่งซื้อสำหรับข้อมูลที่ไม่ได้รับการสแกนไปข้างหน้าและส่งต่อในลำดับที่เรียงลำดับค้นหาตำแหน่งที่สอดคล้องกันและแทรก ในการดำเนินการเรียงลำดับการเรียงลำดับการเรียงลำดับในสถานที่มักจะใช้ (นั่นคือจำเป็นต้องใช้พื้นที่พิเศษของ O (1)) ดังนั้นในระหว่างกระบวนการสแกนจากด้านหลังไปด้านหน้า
2) คำอธิบายและการใช้งานอัลกอริทึม
โดยทั่วไปแล้วการเรียงลำดับการแทรกจะถูกนำไปใช้ในอาร์เรย์โดยใช้ในสถานที่ อัลกอริทึมเฉพาะอธิบายดังนี้:
เริ่มต้นจากองค์ประกอบแรกองค์ประกอบสามารถพิจารณาได้ว่าได้รับการจัดเรียง;
นำองค์ประกอบถัดไปออกมาและสแกนไปข้างหน้าและส่งต่อในลำดับขององค์ประกอบที่เรียงลำดับแล้ว
หากองค์ประกอบ (เรียงลำดับ) มากกว่าองค์ประกอบใหม่ให้ย้ายองค์ประกอบไปยังตำแหน่งถัดไป
ทำซ้ำขั้นตอนที่ 3 จนกว่าจะพบองค์ประกอบที่เรียงลำดับโดยที่องค์ประกอบใหม่น้อยกว่าหรือเท่ากัน
หลังจากแทรกองค์ประกอบใหม่ลงในตำแหน่งนั้น
ทำซ้ำขั้นตอนที่ 2 ถึง 5
การใช้รหัส JavaScript:
ฟังก์ชันแทรก (อาร์เรย์) {ถ้า (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'array') {สำหรับ (var i = 1; i <array.length; i ++) {var key = array [i]; var j = i - 1; ในขณะที่ (j> = 0 && array [j]> คีย์) {array [j + 1] = array [j]; J--; } array [j + 1] = key; } return array; } else {return 'อาร์เรย์ไม่ใช่อาร์เรย์!'; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: อาร์เรย์อินพุตถูกจัดเรียงตามลำดับจากน้อยไปหามาก t (n) = o (n)
กรณีที่เลวร้ายที่สุด: อาร์เรย์อินพุตถูกจัดเรียงตามลำดับจากมากไปน้อย t (n) = o (n2)
ค่าเฉลี่ย: t (n) = o (n2)
สองประเภทการแทรกแบบไบนารี
1) บทนำสู่อัลกอริทึม
การเรียงลำดับแบบไบนารี-อินสตี้-การเรียงลำดับเป็นอัลกอริทึมการเรียงลำดับที่ทำให้เกิดการเปลี่ยนแปลงเล็กน้อยในอัลกอริทึมการเรียงลำดับการแทรกโดยตรง ความแตกต่างที่ใหญ่ที่สุดระหว่างมันกับอัลกอริทึมการเรียงลำดับการแทรกโดยตรงคือเมื่อมองหาตำแหน่งการแทรกวิธีการค้นหาแบบไบนารีจะใช้ซึ่งมีการปรับปรุงความเร็วในการปรับปรุงบางอย่าง
2) คำอธิบายและการใช้งานอัลกอริทึม
โดยทั่วไปแล้วการเรียงลำดับการแทรกจะถูกนำไปใช้ในอาร์เรย์โดยใช้ในสถานที่ อัลกอริทึมเฉพาะอธิบายดังนี้:
เริ่มต้นจากองค์ประกอบแรกองค์ประกอบสามารถพิจารณาได้ว่าได้รับการจัดเรียง;
นำองค์ประกอบถัดไปออกมาและค้นหาตำแหน่งของหมายเลขแรกที่ใหญ่กว่าในลำดับขององค์ประกอบที่เรียงลำดับแล้ว
หลังจากแทรกองค์ประกอบใหม่ลงในตำแหน่งนั้น
ทำซ้ำสองขั้นตอนข้างต้น
การใช้รหัส JavaScript:
ฟังก์ชั่น binaryinsertionsort (อาร์เรย์) {ถ้า (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'Array') {สำหรับ (var i = 1; i <array.length; i ++) {var key = array [i], ซ้าย = 0 ในขณะที่ (ซ้าย <= ขวา) {var middle = parseInt ((ซ้าย + ขวา) / 2); if (key <array [middle]) {right = middle - 1; } else {left = middle + 1; }} สำหรับ (var j = i-1; j> = ซ้าย; j--) {array [j + 1] = array [j]; } อาร์เรย์ [ซ้าย] = คีย์; } return array; } else {return 'อาร์เรย์ไม่ใช่อาร์เรย์!'; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (nlogn)
กรณีที่เลวร้ายที่สุด: t (n) = o (n2)
ค่าเฉลี่ย: t (n) = o (n2)
3. เลือกการเรียงลำดับ
1) บทนำสู่อัลกอริทึม
การเลือกเรียงลำดับเป็นอัลกอริทึมการเรียงลำดับที่ง่ายและใช้งานง่าย วิธีการทำงาน: ก่อนอื่นค้นหาองค์ประกอบที่เล็กที่สุด (ใหญ่) ในลำดับที่ไม่ได้เรียงลำดับเก็บไว้ที่ตำแหน่งเริ่มต้นของลำดับที่เรียงลำดับจากนั้นดำเนินการต่อเพื่อค้นหาองค์ประกอบที่เล็กที่สุด (ใหญ่) จากองค์ประกอบที่ไม่ได้เรียงลำดับที่เหลืออยู่แล้ววางไว้ที่ท้ายลำดับการเรียงลำดับ และอื่น ๆ จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง
2) คำอธิบายและการใช้งานอัลกอริทึม
การเลือกโดยตรงของ N Records สามารถรับได้ผ่าน N-1 ผ่านไปยัง Select และเรียงลำดับโดยตรง อัลกอริทึมเฉพาะอธิบายดังนี้:
สถานะเริ่มต้น: พื้นที่ที่ไม่มีการเรียงลำดับคือ r [1..N] และพื้นที่ที่สั่งซื้อว่างเปล่า;
เมื่อการสั่งซื้อ i-th (i = 1,2,3 ... N-1) เริ่มต้นขึ้นพื้นที่ปัจจุบันที่สั่งและไม่เรียงลำดับคือ r [1..i-1] และ r (i..n) ตามลำดับ คำสั่งนี้เลือกบันทึก R [k] ด้วยคำหลักที่เล็กที่สุดจากพื้นที่ที่ไม่ได้เรียงลำดับปัจจุบันและแลกเปลี่ยนกับบันทึกแรกของพื้นที่ที่ไม่ได้เรียงลำดับดังนั้น R [1..I] และ R [i+1..n) กลายเป็นพื้นที่ใหม่
การเดินทาง N-1 สิ้นสุดลงและมีการสั่งซื้ออาร์เรย์
การใช้รหัส JavaScript:
ฟังก์ชั่นการเลือก (อาร์เรย์) {if (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'array') {var len = array.length, temp; สำหรับ (var i = 0; i <len - 1; i ++) {var min = array [i]; สำหรับ (var j = i+1; j <len; j ++) {ถ้า (อาร์เรย์ [j] <นาที) {temp = min; min = array [j]; อาร์เรย์ [j] = อุณหภูมิ; }} array [i] = min; } return array; } else {return 'อาร์เรย์ไม่ใช่อาร์เรย์!'; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (n2)
กรณีที่เลวร้ายที่สุด: t (n) = o (n2)
ค่าเฉลี่ย: t (n) = o (n2)
4. การเรียงลำดับฟอง
1) บทนำสู่อัลกอริทึม
การเรียงลำดับฟองเป็นอัลกอริทึมการเรียงลำดับที่ง่าย มันเยี่ยมชมลำดับซ้ำ ๆ ที่จะจัดเรียงเปรียบเทียบสององค์ประกอบในแต่ละครั้งและสลับพวกเขาหากพวกเขาไม่ถูกต้อง งานของการเยี่ยมชมลำดับซ้ำจนกว่าจะไม่จำเป็นต้องแลกเปลี่ยนนั่นคือลำดับได้รับการจัดเรียง ต้นกำเนิดของอัลกอริทึมนี้เป็นเพราะองค์ประกอบที่เล็กกว่าจะ "ลอย" ช้ากว่าไปด้านบนของลำดับผ่านการแลกเปลี่ยน
2) คำอธิบายและการใช้งานอัลกอริทึม
อัลกอริทึมเฉพาะอธิบายดังนี้:
เปรียบเทียบองค์ประกอบที่อยู่ติดกัน หากอันแรกมีขนาดใหญ่กว่าอันที่สองแลกเปลี่ยนสองของพวกเขา;
ทำงานเดียวกันกับองค์ประกอบที่อยู่ติดกันแต่ละคู่ตั้งแต่ต้นคู่แรกจนถึงตอนท้ายของคู่สุดท้ายเพื่อให้องค์ประกอบสุดท้ายควรเป็นจำนวนมากที่สุด
ทำซ้ำขั้นตอนข้างต้นสำหรับองค์ประกอบทั้งหมดยกเว้นขั้นตอนสุดท้าย;
ทำซ้ำขั้นตอนที่ 1 ถึง 3 จนกว่าการเรียงลำดับจะเสร็จสมบูรณ์
การใช้รหัส JavaScript:
ฟังก์ชั่น bubblesort (array) {ถ้า (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'array') {var len = array.length, temp; สำหรับ (var i = 0; i <len - 1; i ++) {สำหรับ (var j = len - 1; j> = i; j--) {ถ้า (array [j] <array [j - 1]) {temp = array [j]; Array [J] = Array [J - 1]; อาร์เรย์ [J - 1] = อุณหภูมิ; }}} return array; } else {return 'อาร์เรย์ไม่ใช่อาร์เรย์!'; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (n)
กรณีที่เลวร้ายที่สุด: t (n) = o (n2)
ค่าเฉลี่ย: t (n) = o (n2)
5. จัดเรียงอย่างรวดเร็ว
1) บทนำสู่อัลกอริทึม
แนวคิดพื้นฐานของการเรียงลำดับอย่างรวดเร็ว: แบ่งระเบียนที่จะจัดเรียงเป็นสองส่วนอิสระผ่านคำสั่งหนึ่งและคำหลักของบางบันทึกมีขนาดเล็กกว่าส่วนอื่น ๆ จากนั้นทั้งสองระเบียนสามารถจัดเรียงแยกต่างหากเพื่อให้ได้ลำดับของลำดับทั้งหมด
2) คำอธิบายและการใช้งานอัลกอริทึม
การเรียงลำดับอย่างรวดเร็วใช้วิธีการหารเพื่อแบ่งสตริงออกเป็นสองรายการย่อย อัลกอริทึมเฉพาะอธิบายดังนี้:
การเลือกองค์ประกอบจากลำดับเรียกว่า "หลักการ" (เดือย);
จัดลำดับลำดับใหม่องค์ประกอบทั้งหมดที่มีขนาดเล็กกว่าค่าอ้างอิงจะถูกวางไว้ด้านหน้าของการอ้างอิงและองค์ประกอบทั้งหมดที่มีขนาดใหญ่กว่าค่าอ้างอิงจะถูกวางไว้ด้านหลังการอ้างอิง (จำนวนเดียวกันสามารถวางไว้ที่ด้านใดด้านหนึ่ง) หลังจากออกจากพาร์ติชันนี้การอ้างอิงอยู่ตรงกลางของลำดับ สิ่งนี้เรียกว่าการดำเนินการพาร์ติชัน
จัดเรียงลำดับย่อยซ้ำน้อยกว่าองค์ประกอบอ้างอิงและลำดับย่อยที่ใหญ่กว่าองค์ประกอบอ้างอิง
การใช้รหัส JavaScript:
// วิธีหนึ่งฟังก์ชั่น Quicksort (อาร์เรย์ซ้าย, ขวา) {ถ้า (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'อาร์เรย์' && typeof ซ้าย === 'หมายเลข' && typeof ขวา == สำหรับ (var j = ซ้าย; j <= ขวา; j ++) {ถ้า (อาร์เรย์ [j] <= x) {i ++; temp = array [i]; อาร์เรย์ [i] = อาร์เรย์ [j]; อาร์เรย์ [j] = อุณหภูมิ; }} QuickSort (อาร์เรย์, ซ้าย, i - 1); Quicksort (อาร์เรย์, i + 1, ขวา); - } else {return 'อาร์เรย์ไม่ใช่อาร์เรย์หรือซ้ายหรือขวาไม่ใช่ตัวเลข!'; }} var aaa = [3, 5, 2, 9, 1]; Quicksort (AAA, 0, AAA.Length - 1); console.log (AAA); // วิธีการ 2 var QuickSort = function (arr) {if (arr.length <= 1) {return arr; } var pivotindex = math.floor (arr.length / 2); var pivot = arr.splice (pivotindex, 1) [0]; var left = []; var right = []; สำหรับ (var i = 0; i <arr.length; i ++) {ถ้า (arr [i] <pivot) {left.push (arr [i]); } else {right.push (arr [i]); }} ส่งคืน Quicksort (ซ้าย) .concat ([pivot], Quicksort (ขวา)); -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (nlogn)
กรณีที่เลวร้ายที่สุด: t (n) = o (n2)
ค่าเฉลี่ย: t (n) = o (nlogn)
6. การเรียงลำดับกอง
1) บทนำสู่อัลกอริทึม
การเรียงลำดับฮีปหมายถึงอัลกอริทึมการเรียงลำดับที่ออกแบบมาโดยใช้โครงสร้างข้อมูลฮีป การสแต็กเป็นโครงสร้างที่มีต้นไม้ไบนารีประมาณอย่างสมบูรณ์และเป็นไปตามคุณสมบัติของการซ้อน: นั่นคือค่าคีย์หรือดัชนีของโหนดเด็กนั้นมีขนาดเล็กกว่า (หรือมากกว่า) โหนดแม่
2) คำอธิบายและการใช้งานอัลกอริทึม
อัลกอริทึมเฉพาะอธิบายดังนี้:
ลำดับเริ่มต้นของคำหลักที่จะจัดเรียง (R1, R2 ... RN) ถูกสร้างขึ้นเป็นกองบนสุดขนาดใหญ่ซึ่งเป็นพื้นที่ที่ไม่มีการเรียงลำดับเริ่มต้น;
แลกเปลี่ยนองค์ประกอบสูงสุดของฮีป R [1] กับองค์ประกอบสุดท้าย R [n] และในเวลานี้ภูมิภาคที่ไม่มีการเรียงลำดับใหม่ (R1, R2, ... RN-1) และภูมิภาคที่สั่งใหม่ (RN) ได้รับและ r [1,2 ... n-1] <= r [n] เป็นที่พอใจ;
เนื่องจากกองใหม่ Top R [1] หลังจากการแลกเปลี่ยนอาจละเมิดคุณสมบัติของกองจึงจำเป็นต้องปรับพื้นที่ที่ไม่ได้เรียงลำดับปัจจุบัน (R1, R2, ... RN-1) ไปยังกองใหม่จากนั้นแลกเปลี่ยน r [1] กับองค์ประกอบสุดท้ายของพื้นที่ที่ไม่ได้สั่งซื้ออีกครั้ง ทำซ้ำกระบวนการนี้จนกว่าจำนวนองค์ประกอบในพื้นที่ที่สั่งซื้อคือ N-1 และกระบวนการเรียงลำดับทั้งหมดเสร็จสิ้น
การใช้รหัส JavaScript:
/*เมธอดคำอธิบาย: heap sort @param array array ที่จะเรียงลำดับ*/function heapsort (array) {ถ้า (object.prototype.toString.call (อาร์เรย์) .slice (8, -1) === 'Array') สำหรับ (var i = math.floor (heapsize / 2); i> = 0; i--) {heapify (อาร์เรย์, i, heapsize); } // การเรียงลำดับฮีปสำหรับ (var j = heapsize-1; j> = 1; j--) {temp = array [0]; อาร์เรย์ [0] = อาร์เรย์ [j]; อาร์เรย์ [j] = อุณหภูมิ; heapify (array, 0, -heapsize); }} else {return 'อาร์เรย์ไม่ใช่อาร์เรย์!'; }}/ * เมธอดคำอธิบาย: รักษาคุณสมบัติของฮีป @param arr array @param x อาร์เรย์ตัวห้อย @param len ขนาด heap */ฟังก์ชั่น heapify (arr, x, len) {ถ้า (object.prototype.toString.call (arr) .slice (8, -1) === x + 1, ใหญ่ที่สุด = x, อุณหภูมิ; if (l <len && arr [l]> arr [ใหญ่ที่สุด]) {ใหญ่ที่สุด = l; } if (r <len && arr [r]> arr [ใหญ่ที่สุด]) {ใหญ่ที่สุด = r; } ถ้า (ใหญ่ที่สุด! = x) {temp = arr [x]; arr [x] = arr [ใหญ่ที่สุด]; arr [ใหญ่ที่สุด] = อุณหภูมิ; heapify (arr, ใหญ่, เลน); }} else {return 'arr ไม่ใช่อาร์เรย์หรือ x ไม่ใช่ตัวเลข!'; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (nlogn)
กรณีที่เลวร้ายที่สุด: t (n) = o (nlogn)
ค่าเฉลี่ย: t (n) = o (nlogn)
7. การสั่งซื้อ
1) บทนำสู่อัลกอริทึม
การเรียงลำดับการผสานเป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพตามการดำเนินการผสาน อัลกอริทึมนี้เป็นแอปพลิเคชันทั่วไปของการแบ่งแยกและพิชิต การเรียงลำดับการผสานเป็นวิธีการเรียงลำดับที่เสถียร ผสานลำดับที่สั่งเพื่อให้ได้ลำดับที่ได้รับคำสั่งอย่างสมบูรณ์; นั่นคือทำให้แต่ละลำดับลำดับก่อนจากนั้นทำตามลำดับส่วนที่ตามมา หากสองตารางที่สั่งซื้อถูกรวมเข้ากับตารางที่สั่งซื้อหนึ่งตารางจะเรียกว่าการผสานแบบ 2 ทาง
2) คำอธิบายและการใช้งานอัลกอริทึม
อัลกอริทึมเฉพาะอธิบายดังนี้:
แบ่งลำดับอินพุตของความยาว n ออกเป็นสองลำดับความยาว n/2;
การเรียงลำดับทั้งสองนี้ถูกจัดเรียงกันแยกกัน
ผสานการเรียงลำดับทั้งสองในลำดับการเรียงลำดับสุดท้าย
การใช้รหัส JavaScript:
ฟังก์ชั่น mergesort (array, p, r) {ถ้า (p <r) {var q = math.floor ((p + r) / 2); Mergesort (Array, P, Q); Mergesort (Array, Q + 1, R); ผสาน (อาเรย์, P, Q, R); }} ฟังก์ชั่นผสาน (อาร์เรย์, p, q, r) {var n1 = q - p + 1, n2 = r - q, ซ้าย = [], ขวา = [], m = n = 0; สำหรับ (var i = 0; i <n1; i ++) {left [i] = array [p+i]; } สำหรับ (var j = 0; j <n2; j ++) {ขวา [j] = array [q + 1 + j]; } ซ้าย [n1] = ขวา [n2] = number.max_value; สำหรับ (var k = p; k <= r; k ++) {ถ้า (ซ้าย [m] <= ขวา [n]) {array [k] = ซ้าย [m]; M ++; } else {array [k] = ขวา [n]; n ++; -3) การวิเคราะห์อัลกอริทึม
กรณีที่ดีที่สุด: t (n) = o (n)
กรณีที่เลวร้ายที่สุด: t (n) = o (nlogn)
ค่าเฉลี่ย: t (n) = o (nlogn)
8. การจัดเรียงถัง
1) บทนำสู่อัลกอริทึม
หลักการของการเรียงลำดับถัง: สมมติว่าข้อมูลอินพุตมีการกระจายอย่างสม่ำเสมอข้อมูลจะถูกแบ่งออกเป็นจำนวน จำกัด ของถังและแต่ละถังจะถูกจัดเรียงแยกต่างหาก (เป็นไปได้ที่จะใช้อัลกอริทึมการเรียงลำดับอื่น ๆ
2) คำอธิบายและการใช้งานอัลกอริทึม
อัลกอริทึมเฉพาะอธิบายดังนี้:
ตั้งค่าอาร์เรย์เชิงปริมาณเป็นถังเปล่า
วนซ้ำผ่านข้อมูลอินพุตและใส่ข้อมูลลงในถังที่สอดคล้องกันทีละคน
จัดเรียงแต่ละถังที่ไม่ว่างเปล่า
ประกบข้อมูลที่จัดเรียงจากถังเปล่า
การใช้รหัส JavaScript:
/*เมธอดคำอธิบาย: bucket sort @param array array @param num จำนวนของถัง*/ ฟังก์ชั่น bucketsort (อาร์เรย์, num) {ถ้า (array.length <= 1) {return array; } var len = array.length, buckets = [], result = [], min = max = array [0], regex = '/^[1-9]+[0-9]*$/', space, n = 0; num = num || ((num> 1 && regex.test (num))? num: 10); สำหรับ (var i = 1; i <len; i ++) {min = min <= array [i]? ขั้นต่ำ: อาร์เรย์ [i]; สูงสุด = สูงสุด> = อาร์เรย์ [i]? สูงสุด: อาร์เรย์ [i]; } space = (max - min + 1) / num; สำหรับ (var j = 0; j <len; j ++) {var index = math.floor ((array [j] - min) / space); if (buckets [index]) {// bucket ที่ไม่ว่างเปล่า, แทรกเรียงลำดับ var k = buckets [index] .length - 1; ในขณะที่ (k> = 0 && buckets [index] [k]> array [j]) {buckets [index] [k + 1] = buckets [index] [k]; K--; } buckets [index] [k + 1] = array [j]; } else {// bucket ว่างเปล่าเริ่มต้นถัง [index] = []; ถัง [ดัชนี] .push (อาร์เรย์ [j]); }} ในขณะที่ (n <num) {result = result.concat (buckets [n]); n ++; } ผลตอบแทนผลลัพธ์; -3) การวิเคราะห์อัลกอริทึม
ในกรณีที่ดีที่สุดของการเรียงลำดับถังเวลาเชิงเส้น O (n) ความซับซ้อนของเวลาของการเรียงลำดับของการเรียงลำดับขึ้นอยู่กับความซับซ้อนของเวลาของการเรียงลำดับข้อมูลระหว่างถังเนื่องจากความซับซ้อนของเวลาของชิ้นส่วนอื่น ๆ คือ o (n) เห็นได้ชัดว่ายิ่งมีการแบ่งถังขนาดเล็กลงเท่าไหร่ข้อมูลก็น้อยกว่าที่ถังคือเวลาที่ใช้ในการเรียงลำดับน้อยลง แต่การบริโภคพื้นที่ที่สอดคล้องกันจะเพิ่มขึ้น
9. การนับการเรียงลำดับ
1) บทนำสู่อัลกอริทึม
การนับการเรียงลำดับเป็นอัลกอริทึมการเรียงลำดับที่เสถียร Count Sorting ใช้อาร์เรย์เพิ่มเติม C ซึ่งองค์ประกอบ i-th คือจำนวนองค์ประกอบที่มีค่าเท่ากับ i ในอาร์เรย์ A ที่จะจัดเรียง จากนั้นตามอาร์เรย์ C องค์ประกอบใน A จะถูกจัดเรียงไปยังตำแหน่งที่ถูกต้อง มันสามารถจัดเรียงจำนวนเต็มเท่านั้น
2) คำอธิบายและการใช้งานอัลกอริทึม
อัลกอริทึมเฉพาะอธิบายดังนี้:
ค้นหาองค์ประกอบที่ใหญ่ที่สุดและเล็กที่สุดในอาร์เรย์ที่จะจัดเรียง;
นับจำนวนครั้งแต่ละองค์ประกอบที่มีค่าของฉันในอาร์เรย์จะปรากฏขึ้นและเก็บไว้ในรายการ i-th ของอาร์เรย์ C;
สะสมจำนวนทั้งหมด (เริ่มต้นจากองค์ประกอบแรกใน C แต่ละรายการและรายการก่อนหน้าจะถูกเพิ่ม);
อาร์เรย์เป้าหมายเติมย้อนกลับ: วางแต่ละองค์ประกอบ i ในรายการ c (i) th ของอาร์เรย์ใหม่และลบ C (i) โดย 1 สำหรับแต่ละองค์ประกอบ
การใช้รหัส JavaScript:
ฟังก์ชั่นการนับ (อาร์เรย์) {var len = array.length, b = [], c = [], min = max = array [0]; สำหรับ (var i = 0; i <len; i ++) {min = min <= array [i]? ขั้นต่ำ: อาร์เรย์ [i]; สูงสุด = สูงสุด> = อาร์เรย์ [i]? สูงสุด: อาร์เรย์ [i]; c [array [i]] = c [array [i]]? C [Array [i]] + 1: 1; } สำหรับ (var j = min; j <max; j ++) {c [j + 1] = (c [j + 1] || 0) + (c [j] || 0); } สำหรับ (var k = len - 1; k> = 0; k--) {b [c [array [k]] - 1] = อาร์เรย์ [k]; C [Array [K]]-; } return b; -3) การวิเคราะห์อัลกอริทึม
เมื่อองค์ประกอบอินพุตเป็นจำนวนเต็มระหว่าง 0 ถึง K เวลาทำงานคือ O (N + K) การเรียงลำดับไม่ใช่การเรียงลำดับการเปรียบเทียบและความเร็วในการเรียงลำดับเร็วกว่าอัลกอริทึมการเรียงลำดับการเปรียบเทียบใด ๆ เนื่องจากความยาวของอาร์เรย์ C ที่ใช้นับขึ้นอยู่กับช่วงของข้อมูลในอาร์เรย์ที่จะเรียงลำดับ (เท่ากับความแตกต่างระหว่างค่าสูงสุดและค่าต่ำสุดของอาร์เรย์ที่จะจัดเรียงบวก 1) สิ่งนี้ทำให้การเรียงลำดับต้องใช้เวลาและหน่วยความจำจำนวนมากสำหรับอาร์เรย์ที่มีช่วงข้อมูลขนาดใหญ่