Kỹ thuật sắp xếp trộn (merge sort) dựa trên kỹ thuật chia để trị (divide and conquer). Chúng ta chia toàn bộ tập dữ liệu thành các phần nhỏ hơn và gộp chúng thành một phần lớn hơn theo thứ tự đã sắp xếp. Nó cũng rất hiệu quả cho trường hợp xấu nhất vì thuật toán này có độ phức tạp thời gian thấp hơn cho trường hợp xấu nhất.
Danh sách liên kết có thể được sắp xếp bằng merge-sort rất hiệu quả. Đối với danh sách liên kết, việc gộp (merge) rất đơn giản. Chúng ta chỉ cần cập nhật các liên kết (links) để gộp chúng. Trong phần này, chúng ta sẽ thấy cách sắp xếp danh sách liên kết sử dụng phương pháp này.
Độ phức tạp của kỹ thuật Merge Sort
Độ phức tạp thời gian - O(n log n) cho tất cả các trường hợp
Độ phức tạp không gian - O(n)
Đầu vào - Danh sách không sắp xếp: 14 20 78 98 20 45 Đầu ra - Mảng sau khi sắp xếp: 14 20 20 45 78 98
Thuật toán
mergeList(ll1, ll2)
Đầu vào - Nhận hai danh sách liên kết ll1 và ll2
Đầu ra - Danh sách đã gộp
Bắt đầu
Nếu ll1 rỗng, thì trả về ll2
Nếu ll2 rỗng, thì trả về ll1
Nếu data(ll1) <= data(ll2), thì
new_head = ll1;
next(new_head) = mergeList(next(ll1), ll2)
Ngược lại
new_head = ll2;
next(new_head) = mergeList(ll1, next(ll2))
Trả về new_head
Kết thúcsplit_list(start, ll1, ll2)
Đầu vào - Con trỏ bắt đầu của một danh sách liên kết, hai đối số đầu ra ll1 và ll2
Đầu ra - Hai danh sách liên kết được tạo từ danh sách liên kết
Bắt đầu
slow := start
fast := next(start)
Trong khi fast không null, thực hiện
fast := next(fast)
Nếu fast không null, thì
slow := next(slow)
fast := next(fast)
Kết thúc vòng lặp
ll1 := start
ll2 := next(slow)
next(slow) := null
Kết thúcmergeSort(start)
Đầu vào - Danh sách liên kết
Đầu ra - Danh sách liên kết đã sắp xếp
Bắt đầu
head = start
Nếu head là null hoặc next(head) là null, thì trả về
split_list(head, ll1, ll2)
mergeSort(ll1)
mergeSort(ll2)
start := mergeList(ll1, ll2)
Kết thúcMã nguồn (C++)
#include<bits/stdc++.h>
using namespace std;
class node {
//định nghĩa node để lưu dữ liệu và địa chỉ next
public:
int data;
node *next;
};
void display(class node* start) {
node* p = start; //node hiện tại đặt bằng head
while(p != NULL) { //duyệt cho đến khi node hiện tại không NULL
cout << p->data << " ";
p = p->next; //đi đến node tiếp theo
}
}
node* getNode(int d) {
node* temp = new node;
temp->data = d;
temp->next = NULL;
return temp;
}
node* mergeList(node* ll1, node* ll2) {
//hàm gộp hai danh sách đã sắp xếp
node* newhead = NULL;
if(ll1 == NULL)
return ll2;
if(ll2 == NULL)
return ll1;
//đệ quy gộp các danh sách
if(ll1->data <= ll2->data) {
newhead = ll1;
newhead->next = mergeList(ll1->next, ll2);
} else {
newhead = ll2;
newhead->next = mergeList(ll1, ll2->next);
}
return newhead;
}
void splitList(node* start, node** ll1, node** ll2) {
//tương tự thuật toán rùa thò của Floyd
node* slow = start;
node* fast = start->next;
while(fast != NULL) {
fast = fast->next;
if(fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*ll1 = start;
*ll2 = slow->next;
//chia tách
slow->next = NULL;
}
void mergeSort(node** start) {
node* head = *start;
node* ll1, *ll2;
//trường hợp cơ sở
if(head == NULL || head->next == NULL) {
return;
}
splitList(head, &ll1, &ll2); //chia danh sách thành hai nửa
//sắp xếp các danh sách con trái và phải
mergeSort(&ll1);
mergeSort(&ll2);
//gộp hai danh sách đã sắp xếp
*start = mergeList(ll1, ll2);
return;
}
int main() {
cout << "Tạo danh sách liên kết: " << endl;
cout << "Nhập 0 để dừng xây dựng danh sách, ngược lại nhập bất kỳ số nguyên nào" << endl;
int k, count = 1, x;
node* curr, *temp;
cin >> k;
node* head = getNode(k); //xây dựng danh sách, node đầu tiên
cin >> k;
temp = head;
while(k) {
curr = getNode(k);
temp->next = curr; //thêm từng node
temp = temp->next;
cin >> k;
}
cout << "Trước khi sắp xếp: " << endl;
display(head); //hiển thị danh sách
cout << "\nSau khi sắp xếp: " << endl;
mergeSort(&head);
display(head);
return 0;
}Kết quả
Tạo danh sách liên kết: Nhập 0 để dừng xây dựng danh sách, ngược lại nhập bất kỳ số nguyên nào 89 54 15 64 74 98 10 24 26 0 Trước khi sắp xếp: 89 54 15 64 74 98 10 24 26 Sau khi sắp xếp: 10 15 24 26 54 64 74 89 98