ใช้ var a = [4,2,6,3,1,9,5,5,7,8,0]; เป็นตัวอย่าง
1. Hill sort. การเรียงลำดับฮิลล์เป็นการอัพเกรดที่ทำจากการเรียงลำดับ มันเป็นวิธีการบางอย่างในการเปรียบเทียบกับวิธีการที่มีระยะทางก่อน
ฟังก์ชั่นเชลล์ (arr) {var i, k, j, len = arr.length, gap = math.ceil (len/2), temp; ในขณะที่ (gap> 0) {สำหรับ (var k = 0; k <gap; k ++) {var tagarr = []; tagarr.push (arr [k]) สำหรับ (i = k+gap; i <len; i = i+gap) {temp = arr [i]; tagarr.push (อุณหภูมิ); สำหรับ (j = i-gap; j> -1; j = j-gap) {ถ้า (arr [j]> temp) {arr [j+gap] = arr [j]; } else {break; }} arr [j+gap] = temp; } console.log (Tagarr, "Gap:"+Gap); // เอาต์พุตอาร์เรย์เรียงลำดับที่แทรกอยู่ในปัจจุบัน console.log (arr); // ส่งออกอาร์เรย์หลังจากการเรียงลำดับรอบนี้ } gap = parseInt (GAP/2); } return arr; -กระบวนการส่งออก:
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "Gap: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 0] [6, 7] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 3, 5, 9, 6, 7, 8, 1, 1] [2, 3, 9, 7, 1, 1]
มันสามารถเห็นได้จากผลลัพธ์ ช่วงเวลาระหว่างรอบแรกคือ 5 เรียงลำดับอาร์เรย์ของช่วงเวลาเหล่านี้
ช่วงเวลาคือ 5:
[4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [6, 7] "Gap: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 6, 3, 0, 9, 5, 7, 8, 0] [6, 7] "ช่องว่าง: 5" [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] [4, 2, 6, 3, 1, 9, 5, 7, 8, 0] [1, 0] "ช่องว่าง: 5" [4, 2, 3, 5, 9, 6, 7, 8, 1, 1] [2, 3, 9, 7, 1, 1]
ช่วงเวลาคือ 2:
[4, 2, 6, 3, 0, 9, 5, 7, 8, 1] 4 6 0 5 8 2 3 9 7 1
หลังการเรียงลำดับ:
[0, 1, 4, 2, 5, 3, 6, 7, 8, 9]
ช่วงเวลาคือ 1:
หลังการเรียงลำดับ:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
2. เรียงลำดับอย่างรวดเร็ว ทำอาร์เรย์ที่มีค่าในอาร์เรย์ วางค่าให้เล็กกว่านี้ไปทางซ้ายของอาร์เรย์และใส่ค่าที่ใหญ่กว่านี้ไปทางขวาของอาร์เรย์ จากนั้นทำการดำเนินการเดียวกันกับอาร์เรย์ด้านซ้ายและขวา จนกว่าการเรียงลำดับจะเสร็จสมบูรณ์ โดยปกติค่าแรกของอาร์เรย์จะถูกทำเครื่องหมาย
รหัส:
ฟังก์ชั่น QuickSort (arr) {var len = arr.length, leftarr = [], rightarr = [], แท็ก; if (len <2) {return arr; } tag = arr [0]; สำหรับ (i = 1; i <len; i ++) {ถ้า (arr [i] <= แท็ก) {leftarr.push (arr [i])} else {rightarr.push (arr [i]); }} ส่งคืน QuickSort (leftarr) .concat (แท็ก, QuickSort (Rightarr)) -3. คำสั่งซื้อและเรียงลำดับ ผสานชุดเรียงลำดับเรียงลำดับเป็นลำดับที่มีขนาดใหญ่และสมบูรณ์แบบ ผสานเริ่มต้นด้วยหน่วยที่เล็กที่สุด จากนั้นค่อยๆรวมอาร์เรย์ที่สั่งซื้อ ในที่สุดการเรียงลำดับการผสานก็ทำได้
วิธีการรวมสองอาร์เรย์ที่สั่งซื้อ:
ฟังก์ชั่นย่อย (arr1, arr2) {var len1 = arr1.length, len2 = arr2.length, i = 0, j = 0, arr3 = [], barr1 = arr1.slice (), barr2 = arr2.slice (); ในขณะที่ (barr1.length! = 0 || barr2.length! = 0) {ถ้า (barr1.length == 0) {arr3 = arr3.concat (barr2); barr2.length = 0; } อื่นถ้า (barr2.length == 0) {arr3 = arr3.concat (barr2); barr2.length = 0; } อื่นถ้า (barr2.length == 0) {arr3 = arr3.concat (barr1); barr1.length = 0; } else {ถ้า (barr1 [0] <= barr2 [0]) {arr3.push (barr1 [0]); barr1.shift (); } else {arr3.push (barr2 [0]); Barr2.shift (); }} return arr3; -ผสานเรียงลำดับ:
ฟังก์ชั่น mergesort (arr) {var len = arr.length, arrleft = [], arrright = [], gap = 1, maxGap = len-1, gaparr = [], glen, n; ในขณะที่ (Gap <maxGap) {gap = math.pow (2, n); if (gap <= maxGap) {gaparr.push (gap); } n ++; } glen = gaparr.length; สำหรับ (var i = 0; i <glen; i ++) {gap = gaparr [i]; สำหรับ (var j = 0; j <len; j = j+gap*2) {arrleft = arr.slice (j, j+gap); arrright = arr.slice (j+gap, j+gap*2); console.log ("ซ้าย:"+arrleft, "ขวา:"+arrright); arr = arr.slice (0, j) .concat (subsort (arrleft, arrright), arr.slice (j+gap*2)); }} return arr; -เรียงลำดับ [4,2,6,3,1,9,5,7,7,8,0] ผลผลิต:
ซ้าย: 4 ขวา: 2 ซ้าย: 6 ขวา: 3 ซ้าย: 1 ขวา: 9 ซ้าย: 5 ขวา: 7 ซ้าย: 8 ขวา: 0 ซ้าย: 2,4 ขวา: 3,6 ซ้าย: 1,9 ขวา: 5,7 ซ้าย: 0,8 ขวา: ซ้าย: 2,3,4,6 ขวา: 1,5,7,9 ซ้าย: 0,8
จะเห็นได้ว่าเริ่มต้นจากหน่วยที่เล็กที่สุด
รอบแรกรวมองค์ประกอบที่อยู่ติดกันตามลำดับ: 4,2; 6,3; 1,9; 5,7; 8,0
หลังจากการผสานเสร็จสมบูรณ์แล้ว: [2,4,3,6,1,9,9,5,7,0,8]
รอบที่สองรวมกันในหนึ่งหน่วยของ 2 องค์ประกอบ: [ 2,4], [3,6]; [1,9], [5,7]; [0,8], [];
หลังจากการผสานเสร็จสมบูรณ์แล้ว: [2,3,4,6,1,1,5,7,9,0,8]
รอบที่สามรวมกันในหนึ่งหน่วยของ 4 องค์ประกอบ: [ 2,3,4,6], [1,5,7,9]; [0,8], []
หลังจากการผสานเสร็จสิ้นมันจะกลายเป็น: [1,2,3,4,5,6,7,7,9,0,8];
รอบที่สี่ผสานในหนึ่งหน่วยของ 8 องค์ประกอบ: [1,2,3,4,5,6,7,9], [0,8];
ผสานเสร็จสมบูรณ์ [0,1,2,3,4,5,6,7,7,8,9];
ข้างต้นเป็นเรื่องเกี่ยวกับบทความนี้ฉันหวังว่ามันจะเป็นประโยชน์กับการเรียนรู้ของทุกคน