Merge Sort เป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพตามการดำเนินการผสาน อัลกอริทึมนี้เป็นแอปพลิเคชันทั่วไปของการแบ่งแยกและพิชิต
วิธีการเรียงลำดับการรวมคือการรวมตารางที่สั่งซื้อสอง (หรือมากกว่าสอง) ไว้ในตารางที่สั่งซื้อใหม่นั่นคือแบ่งลำดับที่จะจัดเรียงเป็นหลายภาคต่อแต่ละลำดับจะถูกสั่งซื้อ จากนั้นการเรียงลำดับที่สั่งจะรวมอยู่ในลำดับที่สั่งโดยรวม
การเรียงลำดับการผสานเป็นอัลกอริทึมการเรียงลำดับที่มีประสิทธิภาพตามการดำเนินการผสาน อัลกอริทึมนี้เป็นแอปพลิเคชันทั่วไปของการแบ่งแยกและพิชิต รวมลำดับที่สั่งซื้อเพื่อให้ได้ลำดับที่ได้รับคำสั่งอย่างสมบูรณ์; หากสองตารางที่สั่งซื้อถูกรวมเข้ากับตารางที่สั่งซื้อหนึ่งตารางจะเรียกว่าการผสานแบบ 2 ทาง
กระบวนการดำเนินการผสานมีดังนี้:
1. ใช้สำหรับพื้นที่เพื่อให้ขนาดของมันคือผลรวมของสองลำดับที่เรียงลำดับซึ่งใช้ในการจัดเก็บลำดับที่ผสาน
2. ตั้งสองพอยน์เตอร์ตำแหน่งเริ่มต้นคือตำแหน่งเริ่มต้นของลำดับการเรียงลำดับสองลำดับตามลำดับ
3. เปรียบเทียบองค์ประกอบที่ชี้ไปด้วยพอยน์เตอร์สองตัวเลือกองค์ประกอบที่ค่อนข้างเล็กและนำไปใส่ในพื้นที่ผสานและย้ายตัวชี้ไปยังตำแหน่งถัดไป
4. ทำซ้ำขั้นตอนที่ 3 จนกว่าตัวชี้ถึงจุดสิ้นสุดของลำดับ
5. คัดลอกองค์ประกอบที่เหลือทั้งหมดของลำดับอื่นโดยตรงไปยังจุดสิ้นสุดของลำดับการผสาน
ตัวอย่างที่ 1:
การคัดลอกรหัสมีดังนี้:
-
* ผสานหรือที่เรียกว่าอัลกอริทึมการผสานหมายถึงการทำงานของการรวมลำดับสองลำดับในลำดับเดียว
* อัลกอริทึมการเรียงลำดับการผสานขึ้นอยู่กับการดำเนินการผสาน
-
* กระบวนการดำเนินการผสานมีดังนี้:
-
* 1. ใช้สำหรับพื้นที่เพื่อให้ขนาดของมันเป็นผลรวมของสองลำดับที่เรียงลำดับซึ่งใช้ในการจัดเก็บลำดับที่ผสาน
* 2. ตั้งค่าสองพอยน์เตอร์ตำแหน่งเริ่มต้นคือตำแหน่งเริ่มต้นของลำดับการเรียงลำดับสองลำดับตามลำดับ
* 3. เปรียบเทียบองค์ประกอบที่ชี้ไปที่ตัวชี้สองตัวเลือกองค์ประกอบที่ค่อนข้างเล็กและนำไปไว้ในพื้นที่ผสานและย้ายตัวชี้ไปยังตำแหน่งถัดไป
* 4. ทำซ้ำขั้นตอนที่ 3 จนกว่าตัวชี้ถึงจุดสิ้นสุดของลำดับ
* 5. คัดลอกองค์ประกอบที่เหลือทั้งหมดของลำดับอื่นโดยตรงไปยังจุดสิ้นสุดของลำดับที่ผสาน
-
-
ฟังก์ชั่น MANGESORT (รายการ) {
if (items.length <2) {
รายการกลับ;
-
var middle = math.floor (items.length / 2)
ซ้าย = items.slice (0, กลาง),
ขวา = items.slice (กลาง)
params = merge (mergesort (ซ้าย), mergesort (ขวา));
params.unshift (0, items.length);
items.splice.apply (items, params);
รายการกลับ;
ฟังก์ชั่นผสาน (ซ้ายขวา) {
var result = []
il = 0,
ir = 0;
ในขณะที่ (il <left.length && ir <right.length) {
ถ้า (ซ้าย [il] <ขวา [ir]) {
result.push (ซ้าย [IL ++]);
} อื่น {
result.push (ขวา [IR ++]);
-
-
return result.concat (left.slice (IL)) .concat (ขวา. slice (ir));
-
-
// ทดสอบ
var arr = [2, 1, 3, 12, 5, 66, 23, 87, 15, 32];
Mergesort (arr);
ตัวอย่างที่ 2:
การคัดลอกรหัสมีดังนี้:
<script type = "text/javascript">
//document.write("---------------------------------------------------------------------------------------------- ------------------------------------------------------ -------------------------
// var array = อาร์เรย์ใหม่ (12, 25, 32, 16, 18, 27, 59, 69, 36);
count var = 0;
// เรียกวิธีการเรียงลำดับเพื่อจัดเรียง
// msort (อาร์เรย์, อาร์เรย์, 0, array.length - 1);
// แหล่งที่มาอาร์เรย์
// dest Target Array
// S เริ่มต้นตัวห้อย
// ttarget subscript
ฟังก์ชั่น msort (แหล่งที่มา, dest, s, t) {
var result = "";
var m;
var dest2 = new Array ();
ถ้า (s == t) {
dest [s] = แหล่งที่มา [s];
-
อื่น {
m = math.floor ((s + t) / 2);
msort (แหล่งที่มา, dest2, s, m);
msort (แหล่งที่มา, dest2, m+1, t);
ผสาน (dest2, dest, s, m, t);
/* ผลลัพธ์ผลลัพธ์*//
ผลลัพธ์ += "<br /> เธรด" +++ count +"ผลลัพธ์ของการสั่งซื้อผ่านผ่านคือ:";
สำหรับ (var n = 0; n <dest.length; n ++) {
ผลลัพธ์ + = อาร์เรย์ [n] + ",";
-
/* ผลลัพธ์ผลลัพธ์สิ้นสุดลง*/
-
ผลการกลับมา;
-
/* ผลลัพธ์ผลลัพธ์สิ้นสุดลง*/
// หลอมรวมสองอาร์เรย์ตามลำดับขนาดเล็กไปใหญ่
// แหล่งอาร์เรย์ต้นฉบับ
// อาร์เรย์จัดเรียงปลายทาง
// sthe ตัวห้อยแรก
// m ตารางต่อไปนี้ของอาร์เรย์ที่สอง
// ความยาว ntotal
ฟังก์ชั่นผสาน (แหล่งที่มา, dest, s, m, n) {
สำหรับ (var j = m+1, k = s; j <= n && s <= m; k ++) {
if (source [s] <source [j]) {
dest [k] = แหล่งที่มา [s ++];
-
อื่น {
dest [k] = แหล่งที่มา [j ++];
-
-
// เพิ่มอาร์เรย์ที่เหลืออยู่ในตอนท้ายของปลายทาง
ถ้า (s <= m) {
สำหรับ (var l = 0; l <= m - s; l ++) {
dest [k + l] = แหล่งที่มา [s + l];
-
-
ถ้า (j <= n) {
สำหรับ (var l = 0; l <= n - j; l ++) {
dest [k + l] = แหล่งที่มา [j + l];
-
-
-
//document.write("<< <br /> <br /> ")
</script>