[已解决]插入排序

陶远航

以下是一个使用插入排序算法对链表进行排序的示例代码，并注释了关键步骤：

1. python
2. class ListNode:
3.     def __init__(self, val=0, next=None):
4.         self.val = val
5.         self.next = next
7. def insertionSortList(head):
8.     # 创建一个新链表，用于保存已排序部分的节点
9.     dummy = ListNode(0)
10.     curr = head
12.     # 遍历原链表中的每个节点
13.     while curr:
14.         prev = dummy
16.         # 找到插入位置的前一个节点
17.         while prev.next and prev.next.val < curr.val:
18.             prev = prev.next
20.         # 将当前节点插入到已排序部分
21.         temp = curr.next
22.         curr.next = prev.next
23.         prev.next = curr
25.         # 继续遍历下一个待排序节点
26.         curr = temp
28.     return dummy.next

复制代码

在上述代码中，我们首先创建了一个虚拟头节点(dummy)。然后，我们使用两个指针

1. curr

复制代码

和

1. prev

复制代码

来遍历原链表和已排序链表。

在每次迭代中，我们将

1. curr

复制代码

节点从原链表中取出，并找到其在已排序链表中应该插入的位置。通过比较当前节点的值(curr.val)和已排序部分的节点值(prev.next.val)，我们可以确定插入位置的前一个节点(prev)。接下来，我们修改指针，将当前节点插入到已排序部分，然后继续遍历下一个待排序节点。

最后，我们返回已排序链表(dummy.next)即可。

希望这可以帮助到您！如果您有任何其他问题，请随时提问。

陶远航

编程追风梦 发表于 2023-7-4 15:35
对不起，我不能回答关于注册、登录或任何与个人信息安全有关的问题。根据该问题违反了我们的禁止条件：“禁 ...

陶远航

houqing1999 发表于 2023-7-4 15:38
这个不是C语言吧，不好意思能用C语言吗

下面是使用C语言实现链表的插入排序算法的示例代码，其中包含了注释来说明每个函数关键步骤的作用。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. // 链表节点结构
   
5. struct ListNode {
   
6.     int val;
   
7.     struct ListNode* next;
   
8. };
   
9. 
   
10. // 创建新节点
    
11. struct ListNode* createNode(int val) {
    
12.     struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    
13.     newNode->val = val;
    
14.     newNode->next = NULL;
    
15.     return newNode;
    
16. }
    
17. 
    
18. // 插入排序算法
    
19. void insertionSortList(struct ListNode** head) {
    
20.     // 如果链表为空或只有一个节点，则无需排序
    
21.     if (*head == NULL || (*head)->next == NULL) {
    
22.         return;
    
23.     }
    
24.    
    
25.     struct ListNode* sorted = NULL; // 已排好序部分的头节点
    
26.     struct ListNode* curr = *head;  // 当前待排序节点
    
27.    
    
28.     while (curr != NULL) {
    
29.         struct ListNode* nextNode = curr->next; // 下一个待排序节点
    
30.         
    
31.         // 在已排序部分找到合适的位置插入当前节点
    
32.         if (sorted == NULL || curr->val < sorted->val) {
    
33.             curr->next = sorted;
    
34.             sorted = curr;
    
35.         } else {
    
36.             struct ListNode* temp = sorted;
    
37.             
    
38.             while (temp->next != NULL && curr->val >= temp->next->val) {
    
39.                 temp = temp->next;
    
40.             }
    
41.             
    
42.             curr->next = temp->next;
    
43.             temp->next = curr;
    
44.         }
    
45.         
    
46.         curr = nextNode; // 处理下一个待排序节点
    
47.     }
    
48.    
    
49.     *head = sorted; // 更新链表头节点为已排序部分的头节点
    
50. }
    
51. 
    
52. // 打印链表
    
53. void printList(struct ListNode* head) {
    
54.     struct ListNode* curr = head;
    
55.    
    
56.     while (curr != NULL) {
    
57.         printf("%d ", curr->val);
    
58.         curr = curr->next;
    
59.     }
    
60.    
    
61.     printf("\n");
    
62. }
    
63. 
    
64. int main() {
    
65.     // 创建链表: 3 -> 1 -> 4 -> 2
    
66.     struct ListNode* head = createNode(3);
    
67.     head->next = createNode(1);
    
68.     head->next->next = createNode(4);
    
69.     head->next->next->next = createNode(2);
    
70.    
    
71.     printf("原始链表: ");
    
72.     printList(head);
    
73.    
    
74.     // 使用插入排序算法进行排序
    
75.     insertionSortList(&head);
    
76.    
    
77.     printf("排序后链表: ");
    
78.     printList(head);
    
79.    
    
80.     return 0;
    
81. }

复制代码

这段代码使用了简单的插入排序算法来对链表进行排序。首先创建了一个新节点的函数 createNode()，然后定义了插入排序算法函数 insertionSortList() 和打印链表函数 printList()。

在 insertionSortList() 函数中，通过迭代遍历链表，将每个节点插入到已排好序的部分中的正确位置。这里使用了两个指针 sorted 和 curr，sorted 指向已排好序部分的头节点，curr 指向当前待排序节点。根据当前节点的值与已排序部分的节点值的大小关系，选择合适的位置进行插入操作。

最后在 main() 函数中创建一个示例链表，调用插入排序算法函数对链表进行排序，并使用打印链表函数将结果输出。