数据结构与算法-链表排序算法

在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. 插入排序

LeetCode 147

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;
}