在LeetCode 148接触到了链表的排序。
这一篇文章主要是实现，原理同数组排序算法。
1. 冒泡排序
ListNode *BubbleSort(ListNode *head) {
if (!head || !head->next) return head;
ListNode res;
res.next = head;
ListNode *pre, *cur, *next, *tail;
tail = NULL;
while (res.next != tail) {
pre = &res;
cur = res.next;
while (cur->next != tail) {
next = cur->next;
if (cur->val > next->val) { // 如果当前的比下一个节点大，交换两个节点
pre->next = next; // 前一个节点接后一个节点
cur->next = next->next; // 当前节点连下一个节点的后驱
next->next = cur; // 下一个节点的后驱变为当前节点
pre = next; // 前一个节点后移
} else { // 如果当前的比下一个节点小
pre = cur; // 前一个节点变为当前节点
cur = cur->next; // 当前节点后移
}
}
tail = cur; // 尾部放了最大元素后，尾部前移
}
return res.next;
}
2. 选择排序
ListNode *SelectionSort(ListNode *head) {
if (!head || !head->next) return head;
ListNode sortedHead, unsortHead;
ListNode *pre, *cur, *minPre, *sortedTail;
// 拆成2个链表，一个已排序，一个未排序
sortedHead.next = NULL;
unsortHead.next = head;
sortedTail = &sortedHead;
while (unsortHead.next) {
pre = minPre = &unsortHead;
cur = unsortHead.next;
while (cur) {
if (cur->val < minPre->next->val) { // 找到最小节点和前一个节点
minPre = pre;
}
pre = cur;
cur = cur->next;
}
sortedTail->next = minPre->next; // 插入到已排序链表的最后
sortedTail = minPre->next; // 移动已排序链表的尾节点指向
minPre->next = minPre->next->next; // 最小节点的前一个节点连最小节点的后驱
}
return sortedHead.next;
}
3. 插入排序
ListNode *InsertionSort(ListNode *head) {
if (!head || !head->next) return head;
ListNode sortedHead;
sortedHead.next = head;
ListNode *unsort, *sortedTail, *insert, *pre;
// 拆成2个链表，一个已排序，一个未排序
unsort = head->next; // 认为未排序节点从第二个节点开始
sortedTail = head; // 认为第一个节点已排序
sortedTail->next = NULL;
while (unsort) {
pre = &sortedHead;
insert = unsort;
unsort = unsort->next;
if (insert->val > sortedTail->val) { // 如果比最后的还大，就不比较了
sortedTail->next = insert;
sortedTail = insert;
sortedTail->next = NULL;
continue;
}
// 找到合适的插入位置
while (pre->next->val < insert->val) {
pre = pre->next;
}
insert->next = pre->next;
pre->next = insert;
}
return sortedHead.next;
}
4. 希尔排序
链表的插入排序不需要挪动数组，希尔排序的优势不明显。
另外，链表没有索引，或者实现索引效率较低，不太适合希尔排序。
5. 堆排序
堆利用了数组索引的访问进行构建，链表没有索引，或者实现索引效率较低，不太适合堆排序。
6. 归并排序
ListNode *MergeSort(ListNode *head) {
if (!head || !head->next) return head;
// 统计长度，后期分组
int length = 0;
ListNode* cur = head;
for (; cur; cur = cur->next, ++length);
// 临时头结点
ListNode lead;
lead.next = head;
// 按分组长度修改链表
struct ListNode *pre, *p1, *p2;
int size = 1;
while (size < length) {
pre = &lead;
cur = lead.next;
while (cur) {
// 找到分组的头
int i;
p1 = cur;
for (i = 0; cur && i < size; cur = cur->next, ++i);
if (i < size) break; // 第一组都没满，第二组就没有了，不需要合并
p2 = cur;
for (i = 0; cur && i < size; cur = cur->next, ++i);
// 合并
int l1 = size, l2 = i; // p1和p2的长度
while (l1 && l2) {
if (p1->val < p2->val) {
pre->next = p1;
p1 = p1->next;
--l1;
} else {
pre->next = p2;
p2 = p2->next;
--l2;
}
pre = pre->next;
}
// 另一个部分还没有到尾部
if (l1) {
pre->next = p1;
i = l1;
} else {
pre->next = p2;
i = l2;
}
// pre移动到尾部
for (; i; pre = pre->next, --i);
// pre后驱为下2组的头
pre->next = cur;
}
// 每一组的数量翻倍
size *= 2;
}
cur = lead.next;
return cur;
}
7. 快速排序
// 辅助连接已排序节点
typedef struct Pair {
ListNode *head;
ListNode *tail;
} Pair;
Pair PairQuickSort(ListNode *node)
{
Pair pair;
if (!node || !node->next) { // 递归结束条件，只有一个节点或没有节点
pair.head = pair.tail = node;
return pair;
}
ListNode *key = node; // 分界节点
node = node->next; // 从下一个节点开始比较
//拆分链表，l中为比分界节点小的，r中为比分界节点大的
ListNode l, r;
ListNode *pl = &l, *pr = &r;
while (node) {
if (node->val < key->val) {
pl->next = node;
pl = pl->next;
} else {
pr->next = node;
pr = pr->next;
}
node = node->next;
}
pl->next = pr->next = NULL; //两个部分的结束
Pair lPair = PairQuickSort(l.next); // 递归较小部分
Pair rPair = PairQuickSort(r.next); // 递归较大部分
// 通过分界节点把两个部分链接起来
if (lPair.tail) { //左边的尾节点
lPair.tail->next = key;
pair.head = lPair.head;
} else {
pair.head = key;
}
key->next = rPair.head;
pair.tail = rPair.tail ? rPair.tail : key;
return pair;
}
ListNode *QuickSort(ListNode *head) {
if (!head || !head->next) return head;
return PairQuickSort(head).head;
}
网友评论