Sắp xếp trong danh sách liên kết đơn

Chào ace, bài bác này bọn họ sẽ tìm hiểu về Merge Sort đến danh sách link đơn – Singly Linked danh mục và danh sách liên kết kép – Doubly Linked menu trong series tự học tập về cấu tạo dữ liệu(CTDL) cùng giải thuật, sau đây ucozfree.com sẽ trình làng và share chi tiết(khái niệm, độ phức tạp, vận dụng của nó, code ví dụ…) về nó trải qua các phần sau.Bạn vẫn xem: thu xếp Danh Sách Liên Kết

1. MergeSort giành riêng cho Singly Linked List

Merge sort thường xuyên được ưu tiên thực hiện để bố trí danh sách links – linked danh mục nói bình thường (cả danh sách links đơn cùng kép). Vụ việc hiệu suất truy vấn ngẫu nhiên lừ đừ của linked các mục làm cho một số thuật toán không giống (chẳng hạn như QuickSort) vận động kém hiệu quả, và hồ hết thuật toán không giống (chẳng hạn như HeapSort) trọn vẹn không thể setup được.

Bạn đang xem: Sắp xếp trong danh sách liên kết đơn


*

Lấy nhỏ trỏ head là node đầu tiên của linked list sẽ tiến hành sắp xếp, và con trỏ headRef trỏ cho tới node head. Lưu ý rằng chúng ta cần đạt được một tham chiếu (reference) mang đến node head trong hàm MergeSort() cũng chính vì trong đoạn code ví dụ thiết đặt MergeSort đến linked list bên dưới đây, họ sẽ biến đổi các link con trỏ next của những nodes để bố trí linked list (chứ không phải thực hiện sắp xếp dựa trên việc chuyển đổi các phần dữ liệu của các nodes), vị vậy phải biến hóa node head (tức là làm cho một node khác biến node head mới) ví như phần dữ liệu của node head ban sơ không đề nghị là giá chỉ trị bé dại nhất vào linked list.

* biểu thị thuật toán MergeSort giành cho Singly Linked List

MergeSort(headRef)

MergeSort(b);

*headRef = SortedMerge(a, b);

2. MergeSort dành riêng cho Doubly Linked List

Trong phần này họ sẽ khám phá về cách để viết một hàm có công dụng sắp xếp danh sách link kép – doubly linked list theo đồ vật tự tăng dần bằng phương pháp sử dụng merge sort.

Xem thêm: Dự Báo Thời Tiết Ba Ngày Ở Bắc Giang, Bắc Giang, Việt Nam, Thời Tiết Ở Bac Giang

Ví dụ, ta có list liên kết ban sơ ở dạng:


*

Sau khi chuẩn bị xếp, danh sách link kép bên trên sẽ vươn lên là 2 -> 4 -> 8 -> 10

Cách thiết lập thuật toán MergeSort đến Doubly Linked List tương tự như như áp dụng cho Singly Linked list (đã được tế bào tả tại phần trước), chỉ khác ở 1 điểm đặc trưng đó là so với Doubly Linked List, chúng ta sẽ yêu cầu chỉnh sửa các con trỏ previous khi hơp hai danh sách lại với nhau.

Dưới đấy là các đoạn code ví dụ thiết lập thuật toán MergeSort mang lại danh sách links kép – Doubly Linked List.

CÁC ĐOẠN CODE CÀI ĐẶT THUẬT TOÁN ĐƯỢC VIẾT BẰNG C++ C JAVA PYTHON C#

C

// C program for merge sort on doubly linked danh mục #include #include struct Node int data; struct Node *next, *prev; ; struct Node *split(struct Node *head); // Function to lớn merge two linked lists struct Node *merge(struct Node *first, struct Node *second) // If first linked menu is empty if (!first) return second; // If second linked list is empty if (!second) return first; // Pick the smaller value if (first->data data) first->next = merge(first->next,second); first->next->prev = first; first->prev = NULL; return first; else second->next = merge(first,second->next); second->next->prev = second; second->prev = NULL; return second; // Function to do merge sort struct Node *mergeSort(struct Node *head) if (!head // A utility function to insert a new node at the // beginning of doubly linked menu void insert(struct Node **head, int data) struct Node *temp = (struct Node *)malloc(sizeof(struct Node)); temp->data = data; temp->next = temp->prev = NULL; if (!(*head)) (*head) = temp; else temp->next = *head; (*head)->prev = temp; (*head) = temp; // A utility function to lớn print a doubly linked list in // both forward & backward directions void print(struct Node *head) struct Node *temp = head; printf("Forward Traversal using next poitner "); while (head) printf("%d ",head->data); temp = head; head = head->next; printf(" Backward Traversal using prev pointer "); while (temp) printf("%d ", temp->data); temp = temp->prev; // Utility function khổng lồ swap two integers void swap(int *A, int *B) int temp = *A; *A = *B; *B = temp; // Split a doubly linked danh mục (DLL) into 2 DLLs of // half sizes struct Node *split(struct Node *head) struct Node *fast = head,*slow = head; while (fast->next && fast->next->next) fast = fast->next->next; slow = slow->next; struct Node *temp = slow->next; slow->next = NULL; return temp; // Driver program int main(void) struct Node *head = NULL; insert(&head,5); insert(&head,20); insert(&head,4); insert(&head,3); insert(&head,30); insert(&head,10); head = mergeSort(head); printf(" Linked list after sorting "); print(head); return 0; C++

// C++ program for merge sort on doubly linked danh sách #include using namespace std; class Node public: int data; Node *next, *prev; ; Node *split(Node *head); // Function to merge two linked lists Node *merge(Node *first, Node *second) // If first linked danh sách is empty if (!first) return second; // If second linked các mục is empty if (!second) return first; // Pick the smaller value if (first->data data) first->next = merge(first->next,second); first->next->prev = first; first->prev = NULL; return first; else second->next = merge(first,second->next); second->next->prev = second; second->prev = NULL; return second; // Function to vày merge sort Node *mergeSort(Node *head) if (!head // A utility function to lớn insert a new node at the // beginning of doubly linked list void insert(Node **head, int data) Node *temp = new Node(); temp->data = data; temp->next = temp->prev = NULL; if (!(*head)) (*head) = temp; else temp->next = *head; (*head)->prev = temp; (*head) = temp; // A utility function to print a doubly linked danh mục in // both forward and backward directions void print(Node *head) Node *temp = head; coutdata next; cout data prev; } } // Utility function to swap two integers void swap(int *A, int *B) int temp = *A; *A = *B; *B = temp; // Split a doubly linked list (DLL) into 2 DLLs of // half sizes Node *split(Node *head) Node *fast = head,*slow = head; while (fast->next && fast->next->next) fast = fast->next->next; slow = slow->next; Node *temp = slow->next; slow->next = NULL; return temp; // Driver program int main(void) { Node *head = NULL; insert(&head, 5); insert(&head, 20); insert(&head, 4); insert(&head, 3); insert(&head, 30); insert(&head, 10); head = mergeSort(head); cout Java

// Java program to implement merge sort in singly linked danh mục // Linked các mục Class class LinkedList { static Node head; // head of menu /* Node Class */ static class Node int data; Node next, prev; // Constructor to create a new node Node(int d) data = d; next = prev = null; void print(Node node) Node temp = node; System.out.println("Forward Traversal using next pointer"); while (node != null) System.out.print(node.data + " "); temp = node; node = node.next; System.out.println(" Backward Traversal using prev pointer"); while (temp != null) System.out.print(temp.data + " "); temp = temp.prev; // Split a doubly linked danh sách (DLL) into 2 DLLs of // half sizes Node split(Node head) Node fast = head, slow = head; while (fast.next != null && fast.next.next != null) fast = fast.next.next; slow = slow.next; Node temp = slow.next; slow.next = null; return temp; Node mergeSort(Node node) // Function khổng lồ merge two linked lists Node merge(Node first, Node second) { // If first linked danh mục is empty if (first == null) return second; // If second linked menu is empty if (second == null) return first; // Pick the smaller value if (first.data Python

# Program for merge sort on doubly linked list # A node of the doublly linked menu class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: # Constructor for empty Doubly Linked list def __init__(self): self.head = None # Function khổng lồ merge two linked danh sách def merge(self, first, second): # If first linked các mục is empty if first is None: return second # If secon linked menu is empty if second is None: return first # Pick the smaller value if first.data C#

// C# program lớn implement merge // sort in singly linked danh sách using System; // Linked các mục Class public class LinkedList { Node head; // head of menu /* Node Class */ class Node public int data; public Node next, prev; // Constructor khổng lồ create a new node public Node(int d) data = d; next = prev = null; void print(Node node) Node temp = node; Console.WriteLine("Forward Traversal" + "using next pointer"); while (node != null) Console.Write(node.data + " "); temp = node; node = node.next; Console.WriteLine(" Backward Traversal" + "using prev pointer"); while (temp != null) Console.Write(temp.data + " "); temp = temp.prev; // Split a doubly linked list (DLL) // into 2 DLLs of half sizes Node split(Node head) Node fast = head, slow = head; while (fast.next != null && fast.next.next != null) fast = fast.next.next; slow = slow.next; Node temp = slow.next; slow.next = null; return temp; Node mergeSort(Node node) node.next == null) return node; Node second = split(node); // Recur for left and right halves node = mergeSort(node); second = mergeSort(second); // Merge the two sorted halves return merge(node, second); // Function to lớn merge two linked lists Node merge(Node first, Node second) { // If first linked list is empty if (first == null) return second; // If second linked list is empty if (second == null) return first; // Pick the smaller value if (first.data hiệu quả in ra là:

Linked menu after sortingForward Traversal using next pointer3 4 5 10 trăng tròn 30Backward Traversal using prev pointer30 đôi mươi 10 5 4 3Độ tinh vi về thời gian: Độ phức hợp về thời hạn của các đoạn code thiết lập thuật toán MergeSort dành riêng cho Doubly Linked danh mục ở bên trên thì tương tự với độ phức tạp về thời hạn khi thiết đặt MergeSort cho mảng một chiều, đều nên mất O(nLogn) thời gian.

Nguồn với Tài liệu giờ anh tham khảo:

Tài liệu tự ucozfree.com:

Nếu chúng ta thấy hay cùng hữu ích, bạn có thể tham gia những kênh sau của ucozfree.com để nhận được rất nhiều hơn nữa: