堆排序

#include <vector>
#inelude <iostream>
#inelude <algorithm>
// 维护大顶堆
void heapfy(std::vector<int>& nums, int n, int i)
{
    int biggest = i;
    int lson    = 2 * i + 1;
    int rson    = 2 * i + 2;
    if (lson < n && nums[biggest] < nums[lson])
    {
        biggest = lson;
    }
    if (rson < n && nums[biggest] < nums[rson])
    {
        biggest = rson;
    }
    if (biggest != i)
    {
        std::swap(nums[biggest], nums[i]);
        heapfy(nums, n, biggest);
    }
}
// 堆排序
void heapsort(std::vector<int>& nums)
{
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapfy(nums, n, i);
    }
    for (int i = n-1; i > 0; i--)
    {
        std::swap(nums[0], nums[i]);
        heapfy(nums, i, 0);
    }
}

堆排序变种 求数组topK数字

void heapsort(std::vector<int>& nums, int k)
{
    int n = nums.size();
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapfy(nums, n, i);
    }
    for (int i = n-1; i > n - k - 1; i--)
    {
        std::swap(nums[0], nums[i]);
        heapfy(nums, i, 0);
    }
}

链表的排序 归并排序

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
    // 合并两个有序列表，返回首元结点
    ListNode* mergeList(ListNode* left, ListNode* right)
    {
        // 使用虚假头结点
        ListNode* dummpy = new ListNode();
        ListNode* head = dummpy;
        while(left && right)
        {
            if (left->val < right->val)
            {
                head->next = left;
                left = left->next;
            }
            else
            {
                head->next = right;
                right = right->next;
            }
            head = head->next;
        }
        if(left)
        {
            head->next = left;
        }
        if(right)
        {
            head->next = right;
        }
        head = dummpy->next;
        delete dummpy;
        return head;
    }

    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        // 快慢指针查找中间的节点
        while(fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode* lefthead = head;
        ListNode* righthead = slow->next;
        // 断开中间节点和左边的连接
        slow->next = nullptr;
        lefthead  = sortList(lefthead);
        righthead = sortList(righthead);
        head = mergeList(lefthead, righthead);
        return head;
    }
};