C++用链表实现插入排序,从小到大排序。
时间: 2024-02-24 20:59:54 浏览: 25
好的,以下是C++代码实现:
```c++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 定义插入排序函数
ListNode* insertionSortList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode *dummy = new ListNode(0); // 创建虚拟头节点
dummy->next = head;
ListNode *lastSorted = head, *cur = head->next; // 初始化已排序区间和待排序指针
while (cur != nullptr) {
if (lastSorted->val <= cur->val) { // 待插入节点在已排序区间之后
lastSorted = lastSorted->next;
} else { // 待插入节点在已排序区间之前
ListNode *prev = dummy;
while (prev->next->val <= cur->val) {
prev = prev->next;
}
lastSorted->next = cur->next;
cur->next = prev->next;
prev->next = cur;
}
cur = lastSorted->next;
}
return dummy->next;
}
// 打印链表
void printList(ListNode *head) {
while (head != nullptr) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
// 创建链表
ListNode *head = new ListNode(3);
head->next = new ListNode(1);
head->next->next = new ListNode(5);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(4);
cout << "Before sort: ";
printList(head);
head = insertionSortList(head);
cout << "After sort: ";
printList(head);
return 0;
}
```
以上代码中,我们使用了链表的插入操作来实现插入排序。具体地,我们维护一个已排序区间,初始时只有一个节点,即链表的头节点;然后从第二个节点开始遍历链表,把它插入到已排序区间中合适的位置。这里需要用到两个指针,一个指向已排序区间的最后一个节点,另一个指向当前待排序的节点。