ผสานการเรียงลำดับสำหรับรายการที่เชื่อมโยงโดยใช้ C ++

คำชี้แจงปัญหา

ได้รับการเชื่อมโยงรายการ จัดเรียงโดยใช้อัลกอริธึมการจัดเรียงแบบผสาน

รายการ:10->20->8-17->5->13->4รายการที่เรียงลำดับ:4->5->8->10->13->17->20

อัลกอริทึม

<ก่อน>1. หาก head เป็น NULL หรือ list มีเพียงหนึ่งองค์ประกอบ ให้ส่งคืน list2 สร้างสองรายการโดยแบ่งรายการเดิมออกเป็น 2 ส่วน3. เรียงลำดับส่วนแรกและส่วนที่สองของ list4 รวมรายการที่เรียงลำดับทั้งสอง

ตัวอย่าง

#include #include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;struct node { ข้อมูล int; struct node *next;};node *createList(int *arr, int n){ โหนด *หัว, *p; p =หัว =โหนดใหม่; head->data =arr[0]; head->next =NULL; สำหรับ (int i =1; i next =โหนดใหม่; p =p->ถัดไป; p->data =arr[i]; p->ถัดไป =NULL; } return head;} void displayList(node *head){ while (head !=NULL) { cout <data <<" "; หัว =หัว -> ถัดไป; } cout <data data) { ผลลัพธ์ =head1; ผลลัพธ์ -> ถัดไป =mergeSortedLists (head1-> ถัดไป, head2); } อื่น ๆ { ผล =head2; ผลลัพธ์ -> ถัดไป =mergeSortedLists (head1, head2->next); } ส่งคืนผลลัพธ์;} void splitList (โหนด * src, โหนด **fRef, โหนด ** bRef) { โหนด * เร็ว; โหนด *ช้า; ช้า =src; เร็ว =src->ถัดไป; ในขณะที่ (เร็ว !=NULL) { เร็ว =เร็ว->ถัดไป; ถ้า (เร็ว !=NULL) { ช้า =ช้า->ถัดไป; เร็ว =เร็ว -> ถัดไป; } } *fRef =src; *bRef =ช้า -> ถัดไป; ช้า -> ถัดไป =NULL;} โมฆะ mergeSort (โหนด ** หัว) { โหนด * p =* หัว; โหนด *a =NULL; โหนด *b =NULL; ถ้า (p ==NULL || p->next ==NULL) { return; } splitList(p, &a, &b); mergeSort(&a); mergeSort(&b); *head =mergeSortedLists(a, b);}int main(){ int arr[] ={10, 20, 8, 17, 5, 13, 4}; โหนด * หัว; หัว =createList(arr, SIZE(arr)); cout <<"รายการที่ไม่เรียงลำดับ:" < ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 รายการที่ยังไม่ได้เรียงลำดับ:10 20 8 17 5 13 4 รายการที่เรียงลำดับสุดท้าย:4 5 8 10 13 17 20