Thuật toán insertion sort c++

Không gian phụ trợ: O (1)

Trường hợp ranh giới: thu xếp chèn mất thời gian tối đa để bố trí nếu các phần tử được thu xếp theo lắp thêm tự ngược lại. Cùng cần thời hạn tối thiểu (Thứ từ của n) lúc các thành phần đã được chuẩn bị xếp.

Mô hình thuật toán: Phương pháp tiếp cận gia tăng

Sắp xếp trên chỗ: Có

Ổn định: Có

Trực tuyến: Có

Công dụng: thu xếp chèn được áp dụng khi số lượng phần tử nhỏ. Nó cũng hoàn toàn có thể hữu ích lúc mảng đầu vào gần như là được chuẩn bị xếp, chỉ bao gồm một số phần tử bị để sai địa chỉ trong một mảng khủng hoàn chỉnh.

4. Binary Insertion Sort là gì?

Chúng ta hoàn toàn có thể sử dụng tra cứu kiếm nhị phân để giảm con số so sánh trong thu xếp chèn thông thường. Binary Insertion Sort sử dụng tìm kiếm nhị phân để tìm vị trí phù hợp để chèn mục đã lựa chọn ở mỗi lần lặp. Vào trường thích hợp chèn thông thường, việc sắp xếp lấy O (i) (ở lần lặp máy i). Chúng ta có thể giảm nó thành O (logi) bằng phương pháp sử dụng kiếm tìm kiếm nhị phân. Nói chung, thuật toán vẫn có thời hạn chạy vào trường thích hợp xấu nhất là O (n2) vì chưng chuỗi hoán đổi cần thiết cho mỗi lần chèn.

5. Làm thế nào để triển khai bố trí chèn cho list được Liên kết?

1) Tạo danh sách (hoặc kết quả) được sắp xếp trống

2) xem xét qua danh sách đã cho, triển khai theo các bước sau cho số đông nút.

…… a) Chèn nút lúc này theo phương pháp được bố trí trong list đã bố trí hoặc kết quả.

3) biến đổi phần đầu của danh sách link đã cho thành phần đầu của danh sách được bố trí (hoặc kết quả).

C/C++

/* C program for insertion sort on a linked menu */#include #include /* link list node */struct Node int data; struct Node* next; ; // Function lớn insert a given node in a sorted linked danh sách void sortedInsert(struct Node**, struct Node*); // function khổng lồ sort a singly linked danh sách using insertion sort void insertionSort(struct Node **head_ref) // Initialize sorted linked danh sách struct Node *sorted = NULL; // Traverse the given linked list và insert every // node lớn sorted struct Node *current = *head_ref; while (current != NULL) // Store next for next iteration struct Node *next = current->next; // insert current in sorted linked các mục sortedInsert(&sorted, current); // Update current current = next; // Update head_ref to point khổng lồ sorted linked danh mục *head_ref = sorted; /* function khổng lồ insert a new_node in a list. Chú ý that this function expects a pointer khổng lồ head_ref as this can modify the head of the input linked menu (similar to lớn push())*/void sortedInsert(struct Node** head_ref, struct Node* new_node) /* BELOW FUNCTIONS ARE JUST UTILITY TO thử nghiệm sortedInsert */ /* Function khổng lồ print linked các mục */void printList(struct Node *head) struct Node *temp = head; while(temp != NULL) printf("%d ", temp->data); temp = temp->next; /* A utility function to insert a node at the beginning of linked danh mục */void push(struct Node** head_ref, int new_data) /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; /* link the old danh sách off the new node */ new_node->next = (*head_ref); /* move the head to point khổng lồ the new node */ (*head_ref) = new_node; // Driver program to thử nghiệm above functions int main() struct Node *a = NULL; push(&a, 5); push(&a, 20); push(&a, 4); push(&a, 3); push(&a, 30); printf("Linked list before sorting "); printList(a); insertionSort(&a); printf(" Linked menu after sorting "); printList(a); return 0; Java

// Java program to sort liên kết list // using insertion sort public class LinkedlistIS { node head; node sorted; class node int val; node next; public node(int val) this.val = val; void push(int val) /* allocate node */ node newnode = new node(val); /* liên kết the old menu off the new node */ newnode.next = head; /* move the head to point khổng lồ the new node */ head = newnode; // function to sort a singly linked danh sách using insertion sort void insertionSort(node headref) // Initialize sorted linked danh sách sorted = null; node current = headref; // Traverse the given linked list và insert every // node to sorted while (current != null) // Store next for next iteration node next = current.next; // insert current in sorted linked list sortedInsert(current); // Update current current = next; // Update head_ref to point khổng lồ sorted linked list head = sorted; /* * function khổng lồ insert a new_node in a list. Lưu ý that * this function expects a pointer to lớn head_ref as this * can modify the head of the đầu vào linked danh sách * (similar khổng lồ push()) */ void sortedInsert(node newnode) { /* Special case for the head kết thúc */ if (sorted == null || sorted.val >= newnode.val) newnode.next = sorted; sorted = newnode; else { node current = sorted; /* Locate the node before the point of insertion */ while (current.next != null && current.next.val Python

# Pyhton implementation of above algorithm # Node class class Node: # Constructor khổng lồ initialize the node object def __init__(self, data): self.data = data self.next = None # function khổng lồ sort a singly linked các mục using insertion sort def insertionSort(head_ref): # Initialize sorted linked danh sách sorted = None # Traverse the given linked list & insert every # node khổng lồ sorted current = head_ref while (current != None): # Store next for next iteration next = current.next # insert current in sorted linked menu sorted = sortedInsert(sorted, current) # Update current current = next # Update head_ref to lớn point to lớn sorted linked menu head_ref = sorted return head_ref # function lớn insert a new_node in a list. Cảnh báo that this # function expects a pointer to head_ref as this can modify the # head of the đầu vào linked các mục (similar khổng lồ push()) def sortedInsert(head_ref, new_node): current = None # Special case for the head kết thúc */ if (head_ref == None or (head_ref).data >= new_node.data): new_node.next = head_ref head_ref = new_node else: # Locate the node before the point of insertion current = head_ref while (current.next != None và current.next.data C#

// C# program to lớn sort links list // using insertion sort using System; public class LinkedlistIS { public node head; public node sorted; public class node public int val; public node next; public node(int val) this.val = val; void push(int val) /* allocate node */ node newnode = new node(val); /* liên kết the old các mục off the new node */ newnode.next = head; /* move the head khổng lồ point khổng lồ the new node */ head = newnode; // function to sort a singly // linked menu using insertion sort void insertionSort(node headref) // Initialize sorted linked menu sorted = null; node current = headref; // Traverse the given // linked list & insert every // node to sorted while (current != null) // Store next for next iteration node next = current.next; // insert current in sorted linked list sortedInsert(current); // Update current current = next; // Update head_ref to point lớn sorted linked danh mục head = sorted; /* * function to insert a new_node in a list. Lưu ý that * this function expects a pointer khổng lồ head_ref as this * can modify the head of the input linked các mục * (similar to push()) */ void sortedInsert(node newnode) { /* Special case for the head kết thúc */ if (sorted == null || sorted.val >= newnode.val) newnode.next = sorted; sorted = newnode; else { node current = sorted; /* Locate the node before the point of insertion */ while (current.next != null && current.next.val Kết quả

Linked list before sorting30 3 4 đôi mươi 5Linked menu after sorting3 4 5 đôi mươi 30Nguồn và Tài liệu giờ đồng hồ anh tham khảo:

Tài liệu từ forestcitymalaysias.com:

Nếu các bạn thấy hay với hữu ích, bạn có thể tham gia các kênh sau của forestcitymalaysias.com để nhận được rất nhiều hơn nữa: