จัดเรียงฟอง
หลักการของฟองคือการสร้างองค์ประกอบที่ใหญ่ที่สุดหรือองค์ประกอบที่เล็กที่สุด "ลอย"
แทรกการเรียงลำดับเลือกเรียงลำดับการเรียงลำดับการเรียงลำดับฟองคือการเรียงลำดับการเปรียบเทียบทั้งหมด
ความคิด
เปรียบเทียบตัวเลขสองตัวที่อยู่ติดกันทีละตัววางทศนิยมไว้ด้านหน้าและจำนวนมากที่ด้านหลัง
ขั้นตอนที่ 1: เปรียบเทียบตัวเลขแรกและหมายเลขที่สองใส่ทศนิยมก่อนและจำนวนมากหลังจากนั้น เปรียบเทียบหมายเลขที่สองและหมายเลขที่สามให้วางทศนิยมก่อนและหลังจำนวนใหญ่ให้ดำเนินการต่อไปเช่นนี้จนกว่าจะมีการเปรียบเทียบตัวเลขสองตัวสุดท้ายให้วางทศนิยมก่อนและหลังจำนวนมาก
ขั้นตอนที่ 2: ในการเดินทางครั้งที่สอง: ยังคงเริ่มจากลอการิทึมแรก (เนื่องจากอาจเป็นเพราะการแลกเปลี่ยนหมายเลขที่สองและหมายเลขที่สามหมายเลขแรกจะไม่เล็กกว่าหมายเลขที่สองอีกต่อไป) วางทศนิยมก่อนและหลังการใส่จำนวนมาก ในตอนท้ายของการเดินทางครั้งที่สองจะได้รับจำนวนสูงสุดใหม่ที่ตำแหน่งสุดท้าย (จริง ๆ แล้วเป็นจำนวนที่ใหญ่เป็นอันดับสองในลำดับทั้งหมด)
หากสิ่งนี้ดำเนินต่อไปให้ทำซ้ำกระบวนการข้างต้นจนกว่าการเรียงลำดับจะเสร็จสมบูรณ์ในที่สุด
เนื่องจากทศนิยมจะถูกวางไปข้างหน้าและจำนวนมากจะถูกวางย้อนหลังในระหว่างกระบวนการเรียงลำดับซึ่งเทียบเท่ากับการเพิ่มขึ้นของฟองสบู่จึงเรียกว่าการเรียงลำดับฟอง
เอฟเฟกต์แอนิเมชั่นการเรียงลำดับฟอง
การใช้งาน: รหัสนี้ค่อนข้างง่ายและเป็นรหัสพื้นฐานและพื้นฐานที่สุดในอัลกอริทึม - -
สามสิ่งที่ควรทราบ
1. วิธีการแลกเปลี่ยนคลาสสามารถแก้ไขได้ในจาวาสคริปต์ด้วย a = [b, b = a] [0]
แทนที่
การคัดลอกรหัสมีดังนี้:
var, a, b, temp
อุณหภูมิ = a;
a = b;
b = อุณหภูมิ
วิธีการแลกเปลี่ยนนี้
2. ให้ความสนใจกับแคชของตัวแปรลูปโดยที่ Array.length ถูกแคช
3. ให้ความสนใจกับลูปแบบฝังซึ่งเป็นการเปรียบเทียบจากหมายเลขแรกกับหมายเลขสุดท้ายที่ n และ n คือหมายเลขขั้นตอนการเปรียบเทียบ
ฟังก์ชั่น bubblesort (อาร์เรย์) {var l = array.length; สำหรับ (var i = 0; i <l; i ++) {// จำนวนขั้นตอนที่เปรียบเทียบคือความยาวของอาร์เรย์สำหรับ (var j = 0; j <li; j ++) {// จำนวนของการแลกเปลี่ยนอินไลน์ {array [j] = [array [j - 1], array [j - 1] = array [j]] [0] // องค์ประกอบสลับที่นี่}} สำหรับ (var k = 0; k <l; k ++) {console.log (อาร์เรย์ [k]+","); [6,54,6,22,5,7,8,2,34]; Bubblesort (A);เอฟเฟกต์ภาพเคลื่อนไหว
เรียงลำดับ
มันง่ายมากมันเป็นขั้นตอนสำหรับเราที่จะสัมผัสและแทรกการ์ด!
แนวคิด:
1 ก่อนอื่นสมมติว่าเราแตะการ์ดและการ์ดทั้งหมดในมือของเราถูกตั้งค่าให้ว่าง = [] แตะกด (arr [0])
2 นำการ์ดใบถัดไปออกไปตั้งค่าเป็น A, สแกนจากด้านหลังไปด้านหน้าในการ์ดทั้งหมดของเราว่างเปล่า (เรียงลำดับแล้ว)
3 หากการ์ดในมือของคุณว่างเปล่า [ว่างเปล่า length-n] (เรียงลำดับ) มากกว่าองค์ประกอบใหม่ให้ย้ายการ์ดไปยังตำแหน่งถัดไป (พื้นที่ว่าง) ว่างเปล่า [empty.length-n] = ว่าง [ว่างเปล่า. length-n+1]
4Repeat ขั้นตอนที่ 3 จนกว่าการ์ดที่จัดเรียงจะว่างเปล่า [ว่างเปล่าความยาว N] น้อยกว่าหรือเท่ากับก
5 แทรก A ลงในตำแหน่งนี้ว่าง [empty.length-n] = a
6 ทำซ้ำขั้นตอนที่ 2
อย่างไรก็ตามรหัส JavaScript ยังคงใช้งานได้ยากเล็กน้อยรหัสมีดังนี้:
ฟังก์ชั่นแทรก (arr) {var l = arr.length; var empty = [] // อาร์เรย์ว่างเปล่าแสดงว่ามือของเราว่างเปล่า push (arr [0]); // ลองแตะรูปภาพก่อน (var i = 1; i <l; i ++) {// โปรดทราบว่าจุดเริ่มต้นที่นี่คือ 1 เพราะเราได้สัมผัสหนึ่ง! ถ้า (arr [i]> ว่าง [ว่างเปล่า - ความยาว - 1]) {ว่าง [ว่างเปล่า] = arr [i]} // ถ้ามันใหญ่กว่าอาร์เรย์ที่สั่งซื้อว่างเปล่าให้วางตรงไปที่ปลาย (var j = ว่างเปล่า j> 0 && arr [i] <ว่าง [J - 1]; j--) เมื่อ arr <เป็นอาร์เรย์ที่สั่งซื้อไม่จำเป็นต้องย้าย ว่างเปล่า [J] = ว่าง [J - 1]; // ย้ายว่าง [J - 1] = arr [i]; // ใส่ค่าไปยังตำแหน่งว่าง} // console.log (ว่าง)} return}}จากนั้นจุดความรู้ที่สำคัญกว่านี้คือสัญลักษณ์ && ซึ่งหมายความว่า "และ" นั่นคือเงื่อนไขของทั้งสองฝ่ายจะต้องพบก่อนที่จะมีการแสดงออก
สัญลักษณ์ && สามารถแทนที่ได้หากเช่นถ้า (a) {fun ()} เท่ากับ a && b
อีกจุดที่สำคัญมาก
สมมติว่าอาร์เรย์เป็น arr จากนั้น "รายการสุดท้าย" คือ arr [arr.length-1]
จัดเรียงแอนิเมชั่น
การเลือกการเลือก
นอกจากนี้ยังเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่าย
แนวคิด:
ค้นหาองค์ประกอบที่เล็กที่สุด - โยนมันเข้าไปในอาร์เรย์ - ค้นหาตัวเล็กอีกครั้ง - โยนมันลงในอาร์เรย์และอื่น ๆ
ก่อนอื่นค้นหาองค์ประกอบที่เล็กที่สุดในอาร์เรย์ที่ไม่ได้แยก วิธีที่คุณพบสามารถใช้วิธีการตัดสินและการมอบหมายอย่างต่อเนื่องนั่นคือ: ให้อาร์เรย์องค์ประกอบแรก [0] ของอาร์เรย์เป็นองค์ประกอบที่เล็กที่สุดจากนั้นหมายเลขลำดับของ "องค์ประกอบขั้นต่ำ" ในอาร์เรย์คือ 0
จากนั้นวนซ้ำอาร์เรย์ หากองค์ประกอบที่สองของอาร์เรย์มีขนาดเล็กกว่านั้นองค์ประกอบที่สองคือองค์ประกอบที่เล็กที่สุดและอัปเดต "0" เป็น "1"
หลังจากข้ามไปเรารู้ว่าตัวห้อยขององค์ประกอบที่เล็กที่สุดในซีรีส์นี้คือ "n"; มันถูกนำออกและเก็บไว้ที่ตำแหน่งเริ่มต้นของลำดับการเรียงลำดับ (อาร์เรย์ [n])
จากนั้นดำเนินการต่อเพื่อค้นหาองค์ประกอบที่เล็กที่สุดจากองค์ประกอบที่ไม่ได้เรียงลำดับที่เหลืออยู่จากนั้นวางไว้ในตอนท้ายของลำดับการเรียงลำดับ โปรดทราบว่าตัวห้อยของการเดินทางเริ่มต้นจาก 1 ในเวลานี้ เพราะเราได้เลือกองค์ประกอบที่เล็กที่สุดแล้ว
และอื่น ๆ จนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง
ฟังก์ชั่น selectsort (array) {var min; var l = array.length; // ความยาวแคชสำหรับ (var i = 0; i <l; i ++) {// เริ่มวนลูปวนรอบ 1 ครั้งและคุณสามารถค้นหาองค์ประกอบ l min = i; // (อาร์เรย์ [ขั้นต่ำ]> อาร์เรย์ [j]) // ตัดสินว่า min = j; // อัปเดตตัวห้อย "ขั้นต่ำ"} ถ้า (min! = i) {// เพราะที่นี่เพราะมันทำงานในอาร์เรย์เดียวกันคุณสามารถแลกเปลี่ยนองค์ประกอบโดยตรง ตัวอย่างเช่นรายการแรกของอาร์เรย์คือฉันจากนั้นฉันก็พบว่าองค์ประกอบที่เล็กที่สุดคืออาร์เรย์ [ขั้นต่ำ] ดังนั้นฉันต้องแลกเปลี่ยนขั้นต่ำนี้กับฉัน และอื่น ๆ Array [i] = [Array [min], Array [min] = array [i]] [0]; // องค์ประกอบการแลกเปลี่ยน}} return array;}สิ่งที่ยังคงระบุไว้ที่นี่คือวิธีการเขียนของอาร์เรย์แลกเปลี่ยน [i] = [อาร์เรย์ [ขั้นต่ำ], อาร์เรย์ [ขั้นต่ำ] = อาร์เรย์ [i]] [0]
มันง่ายที่จะแลกเปลี่ยนอาร์เรย์ [i] และอาร์เรย์ [min] ~
จัดเรียงแอนิเมชั่น
จัดเรียงอย่างรวดเร็ว
การจัดเรียงอย่างรวดเร็วเป็นอัลกอริทึมการเรียงลำดับที่ทรงพลังที่สุดในปัจจุบันซึ่งใช้ประโยชน์จากแนวคิดของการเรียกซ้ำ
ความคิด
การเลือกองค์ประกอบจากอาร์เรย์เรียกว่า "เกณฑ์มาตรฐาน" สามารถเลือกได้โดยตรงโดยใช้ความยาว/2
วนซ้ำผ่านอาร์เรย์องค์ประกอบทั้งหมดที่มีขนาดเล็กกว่าค่าอ้างอิงจะถูกวางไว้ด้านหน้าของการอ้างอิงและองค์ประกอบทั้งหมดที่มีขนาดใหญ่กว่าค่าอ้างอิงจะถูกวางไว้ด้านหลังการอ้างอิง (จำนวนเดียวกันสามารถใช้กับทั้งสองด้าน) ในแง่ของคนธรรมดาชายคนนั้นยืนอยู่ทางซ้ายและผู้หญิงยืนอยู่ทางขวา -
จากนั้นเราจะได้อาร์เรย์อาร์เรย์ = อาร์เรย์ลาเรย์ประกอบด้วยชิ้นส่วนที่เล็กกว่าเบนช์มาร์ก + อาร์เรย์ rarray ประกอบด้วยชิ้นส่วนที่ใหญ่กว่าเกณฑ์มาตรฐาน
จากนั้นเราเพียงแค่ต้อง "เดียวกัน" กระบวนการ Larray และ Rarray ~
สิ่งนี้ต้องใช้การเขียนซ้ำ หลังจากการประมวลผล Larray จะถูกแบ่งออกเป็นมาตรฐานของ Larray ซึ่งมีขนาดเล็กกว่าเกณฑ์มาตรฐานของ Larray และใหญ่กว่าเกณฑ์มาตรฐานของ Larray -
จากนั้นเราก็ทำสิ่งต่าง ๆ ต่อไปชายคนนั้นยืนอยู่ทางซ้ายและผู้หญิงยืนอยู่ทางขวา -
จนกว่าเราจะพบว่าความยาวของแลร์เรย์กลายเป็น 1 ซึ่งไม่เพียงพอที่จะถูกแบ่งอีกครั้งเราคิดว่าการเรียงลำดับสิ้นสุดลง
ฟังก์ชั่น QuickSort (arr) {var l = arr.length; // ความยาวอาร์เรย์แคชถ้า (arr.length <= 1) {return arr}; // ถ้าความยาวของลาร์เรย์และ rarray เราได้รับมีขนาดเล็กกว่า 1 ดังนั้นไม่จำเป็นต้องจัดเรียง ~ var num = math.floor (arr.length/2); // เลือกหมายเลขที่อยู่ตรงกลางของอาร์เรย์ โปรดทราบว่าความยาว/2 ไม่จำเป็นต้องเป็นจำนวนเต็ม ใช้ math.floor เพื่อปัด var numValue = arr.splice (num, 1) [0]; // ใช้วิธีการประกบเพื่อใช้องค์ประกอบให้ความสนใจกับไวยากรณ์ var ซ้าย = []; // สร้างคอนเทนเนอร์อ้างอิงด้านซ้าย var ขวา = []; // สร้างคอนเทนเนอร์อ้างอิงที่ถูกต้อง left.push (arr [i]): right.push (arr [i]); // ผู้ชายยืนอยู่ทางซ้ายและผู้หญิงยืนอยู่ทางขวา - } return Quicksort (ซ้าย) .concat ([numvalue], Quicksort (ขวา)) // ซ้ำอีกครั้งดำเนินการต่อไปที่อาร์เรย์ซ้ายและขวา -เอฟเฟกต์ภาพเคลื่อนไหว:
โปรดทราบว่าแม้ว่า arr.splice (num, 1) วาดเพียงหนึ่งตัวเลขผลของการประกบก็เป็นอาร์เรย์ซึ่งต้องใช้ [0] มิฉะนั้นผลลัพธ์จะเป็นอาร์เรย์อาร์เรย์ (1) - -
การอ้างอิง Splice: //www.vevb.com/w3school/js/jsref_splice.htm
Math.floor เป็นข้อมูลอ้างอิงสำหรับวัตถุคณิตศาสตร์ //www.vevb.com/w3school/js/js_obj_math.htm
การเรียกซ้ำคืออะไร: http://baike.baidu.com/view/96473.htm
นอกเหนือจากการเรียงลำดับอย่างรวดเร็วอัลกอริทึมสี่ตัวข้างต้นเป็นอัลกอริทึมการเรียงลำดับที่เรียบง่ายทั้งหมดและอัลกอริทึมทั้งสี่นี้มักจะถ่ายบ่อยมากในระหว่างการสัมภาษณ์ ~
มันยังคงเป็นสิ่งสำคัญที่จะเน้นที่นี่ว่าอัลกอริทึมข้างต้นใช้ความรู้ที่เกี่ยวข้องมากมายเกี่ยวกับลูปและอาร์เรย์ดังนั้นคุณต้องจดจำมัน!