รหัสการใช้งานและแนวคิดของการเรียงลำดับแบบผสาน

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

คัดลอกรหัสรหัส ดังต่อไปนี้:

ดูรหัส
//รวมอาร์เรย์ที่สั่ง a[] และ b[] เข้ากับ c[]
เป็นโมฆะ MemeryArray (int a[], int n, int b[], int m, int c[])
-
ฉัน, เจ, เค;

ผม = เจ = k = 0;
ในขณะที่ (ฉัน < n && j < ม.)
-
ถ้า (a[i] < b[j])
ค[k++] = ก[i++];
อื่น
ค[k++] = ข[เจ++];
-

ในขณะที่ (ฉัน < n)
ค[k++] = ก[i++];

ในขณะที่ (เจ < ม.)
ค[k++] = ข[เจ++];
-

จะเห็นได้ว่าประสิทธิภาพของการรวมลำดับลำดับค่อนข้างสูงและสามารถไปถึง O(n) ได้

หลังจากแก้ไขปัญหาข้างต้นในการรวมลำดับการเรียงลำดับแล้ว เรามาดูการเรียงลำดับการผสานกัน แนวคิดพื้นฐานคือการแบ่งอาร์เรย์ออกเป็นสองกลุ่ม A และ B หากข้อมูลในสองกลุ่มนี้เรียงลำดับกันทั้งหมด ก็สามารถทำสองชุดนี้ได้อย่างง่ายดาย ของข้อมูลจะถูกจัดเรียง จะเก็บข้อมูลในสองกลุ่มนี้ให้เป็นระเบียบได้อย่างไร?

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

คัดลอกรหัสรหัส ดังต่อไปนี้:

ดูรหัส
// จะรวมลำดับสองลำดับ a[first...mid] และ a[mid...last]
การผสานรวมเป็นโมฆะ (int a[], int ก่อน, int mid, int สุดท้าย, int temp[])
-
int i = อันดับแรก, j = กลาง + 1;
int m = กลาง, n = สุดท้าย;
int k = 0;

ในขณะที่ (i <= m && j <= n)
-
ถ้า (a[i] <= a[j])
อุณหภูมิ[k++] = a[i++];
อื่น
อุณหภูมิ[k++] = a[j++];
-

ในขณะที่ (ฉัน <= ม.)
อุณหภูมิ[k++] = a[i++];

ในขณะที่ (เจ <= n)
อุณหภูมิ[k++] = a[j++];

สำหรับ (i = 0; i <k; i++)
a[แรก + i] = อุณหภูมิ[i];
-
การผสานเป็นโมฆะ (int a[], int ก่อน, int สุดท้าย, int temp[])
-
ถ้า (แรก < สุดท้าย)
-
int กลาง = (แรก + สุดท้าย) / 2;
การผสาน (a, อันดับแรก, กลาง, อุณหภูมิ); // จัดเรียงด้านซ้าย
การผสาน (a, mid + 1, สุดท้าย, temp); // ทางด้านขวาถูกจัดเรียง
mergearray(a, ครั้งแรก, กลาง, สุดท้าย, temp); // รวมอาร์เรย์ทั้งสองที่เรียงลำดับไว้
-
-

บูล MergeSort(int a[], int n)
-
int *p = int ใหม่[n];
ถ้า (p == โมฆะ)
กลับเท็จ;
การผสาน (a, 0, n - 1, p);
ลบ[]พี;
กลับเป็นจริง;
-

ประสิทธิภาพของการเรียงลำดับแบบผสานค่อนข้างสูง สมมติว่าความยาวของลำดับคือ N โดยต้องใช้ขั้นตอน logN เพื่อแบ่งลำดับออกเป็นลำดับทศนิยม N) ดังนั้นผลรวมคือ O(N*logN) เนื่องจากการเรียงลำดับแบบผสานทำงานกับข้อมูลที่ติดกันทุกครั้ง วิธีการเรียงลำดับหลายวิธีของการเรียงลำดับแบบผสาน (การเรียงลำดับแบบด่วน การเรียงลำดับแบบผสาน การเรียงลำดับแบบ Hill การเรียงลำดับแบบฮีป) ใน O(N*logN) ก็ค่อนข้างมีประสิทธิภาพเช่นกัน