Đề bài
Cho một danh sách liên kết (linked list). Sắp xếp nó bằng thuật toán merge sort.
List: 10->20->8-17->5->13->4 Sorted list: 4->5->8->10->13->17->20
Thuật toán
1. Nếu head là NULL hoặc danh sách chỉ chứa một phần tử thì trả về danh sách 2. Tạo hai danh sách bằng cách chia danh sách gốc thành 2 phần 3. Sắp xếp phần đầu và phần sau của danh sách 4. Gộp hai danh sách đã sắp xếp
Ví dụ
#include <iostream> #include <new> #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) using namespace std; struct node { int data; struct node *next; }; node *createList(int *arr, int n){ node *head, *p; p = head = new node; head->data = arr[0]; head->next = NULL; for (int i = 1; i < n; ++i) { p->next = new node; p = p->next; p->data = arr[i]; p->next = NULL; } return head; } void displayList(node *head){ while (head != NULL) { cout << head->data << " "; head = head->next; } cout << endl; } node *mergeSortedLists(node *head1, node *head2){ node *result = NULL; if (head1 == NULL) { return head2; } if (head2 == NULL) { return head1; } if (head1->data < head2->data) { result = head1; result->next = mergeSortedLists(head1->next,head2); } else { result = head2; result->next = mergeSortedLists(head1, head2->next); } return result; } void splitList(node *src, node **fRef, node **bRef){ node *fast; node *slow; slow = src; fast = src->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } *fRef = src; *bRef = slow->next; slow->next = NULL; } void mergeSort(node **head){ node *p = *head; node *a = NULL; node *b = NULL; if (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}; node *head; head = createList(arr, SIZE(arr)); cout << "Unsorted list: " << endl; displayList(head); mergeSort(&head); cout << "Final sorted list: " << endl; displayList(head); return 0; }
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Unsorted list: 10 20 8 17 5 13 4 Final sorted list: 4 5 8 10 13 17 20