参照闫神讲解，整理了一下sort函数

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void bubble_sort(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        bool flag = true;
        for (int j = 0; j < n - i - 1; ++j) {
            if (nums[j+1] < nums[j]) {
                swap(nums[j+1], nums[j]);
                flag = false;
            }
        } 
        if (flag) break;
    }
    return;
} 

void selection_sort(vector<int> &nums) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        int k = i;
        for (int j = i + 1; j < n; ++j) {
            if (nums[j] < nums[k]) 
                k = j;
        }
        if (k != i)
            swap(nums[i], nums[k]);
    }
    return;
}

void insert_sort(vector<int> &nums) {
    int n = nums.size();
    for (int i = 1; i < n; ++i) {
        // 为确保稳定性 找到第一个大于nums[i]的数值下标 
        int tmp = nums[i];
        int low = 0, high = i;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] <= nums[i]) low = mid + 1;
            else high = mid; 
        }
        for (int k = i; k > high; --k) {
            nums[k] = nums[k - 1];
        } 
        nums[high] = tmp;
    }
    return;
}

void push_down(vector<int> &heap, int size, int u) {
    int t = u;
    int left = 2 * u, right = 2 * u + 1;
    while (left <= size && heap[left] > heap[t]) t = left;
    while (right <= size && heap[right] > heap[t]) t = right;
    if (t != u) {
        swap(heap[t], heap[u]);
        push_down(heap, size, t);
    }
    return;
}
void push_up(vector<int> &heap, int u) {
    int father = u / 2;
    while (father && heap[father] < heap[u]) {
        swap(heap[father], heap[u]);
        u = father;
        father /= 2;
    }
    return;
}
void heap_sort(vector<int> &heap) {
    heap.insert(heap.begin(), -1);
    int n = heap.size() - 1;
    for (int i = 1; i <= n; ++i) {
        push_up(heap, i);
    }

    while (n) {
        swap(heap[1], heap[n--]);
        push_down(heap, n, 1);
    }
    heap.erase(heap.begin());
    return;
}

void quick_module(vector<int> &nums, int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, pivot = nums[(l+r) >> 1];
    while (i < j) {
        do i++; while (nums[i] < pivot);
        do j--; while (nums[j] > pivot);
        if (i < j) swap(nums[i], nums[j]);
        else {
            quick_module(nums, l, j);
            quick_module(nums, j + 1, r);
        }
    }
    return;
}
void quick_sort(vector<int> &nums) {
    quick_module(nums, 0, nums.size() - 1);
    return;
}

void merge_module(vector<int> &nums, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    merge_module(nums, l, mid);
    merge_module(nums, mid + 1, r);

    static vector<int> tmp;
    tmp.clear();
    int i = l, j = mid + 1;
    while (i <= mid && j <= r) {
        if (nums[i] <= nums[j])
            tmp.push_back(nums[i++]);
        else 
            tmp.push_back(nums[j++]);   
    }    
    while (i <= mid) tmp.push_back(nums[i++]);
    while (j <= r) tmp.push_back(nums[j++]);
    for (i = l, j = 0; i <= r; ++i, ++j) nums[i] = tmp[j];
    return; 
}
void merge_sort(vector<int> &nums) {
    merge_module(nums, 0, nums.size() - 1);
    return;
}

// 基于链表的排序 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {} 
};

ListNode* merge2Lists(ListNode *l, ListNode *r) {
    ListNode *head = new ListNode(-1);
    ListNode *p = head;
    while (l && r) {
        if (l->val <= r->val) {
            p->next = l;
            l = l->next;
            p = p->next;
        } else {
            p->next = r;
            r = r->next;
            p = p->next;
        }
    }
    if (l) p->next = l;
    if (r) p->next = r;
    return head->next;
}
// 基于链表的归并 
ListNode* mergeSort(ListNode *list) {
    if (!list || !list->next) return list;

    ListNode *fast = list, *low = list;
    ListNode *pre = NULL;
    while (fast && fast->next) {
        pre = low;
        low = low->next;
        fast = fast->next->next;
    }
    pre->next = NULL;  // 断链！！ 
    ListNode *l = mergeSort(list);
    ListNode *r = mergeSort(low);
    return merge2Lists(l, r);
}

// follow up: 排序k个有序列表 
ListNode* mergeKLists(vector<ListNode*>& lists) {
    int m = lists.size();
    if (m == 0) return NULL;
    if (m == 1) return lists[0];

    int mid = m / 2;
    vector<ListNode*> left = vector<ListNode*>(lists.begin(), lists.begin() + mid);
    vector<ListNode*> right = vector<ListNode*>(lists.begin() + mid, lists.end());
    ListNode *l= mergeKLists(left);
    ListNode *r= mergeKLists(right);
    return merge2Lists(l, r);
}

// 基于链表的快排 
void swap(ListNode *p, ListNode *q) {
    int t = p->val;
    p->val = q->val;
    q->val = t;
}
void quick(ListNode *head, ListNode *end) {
    if(!head || head == end) return;

    ListNode *small = head, *p = head->next;

    while (p != end->next) {
        if (p->val < head->val) {
            small = small->next;
            swap(small, p);
        }
        p = p->next;
    }

    swap(head, small);
    quick(head, small);
    quick(small->next, end);
}
ListNode* quickSort(ListNode *head) {
    ListNode *end = head;
    while (end->next) end = end->next;

    quick(head, end);

    return head;
}
// 基于链表的插入排序
ListNode* insertionSortList(ListNode* head) {
    ListNode *dummy = new ListNode(-1);
    while (head) {
        ListNode *next = head->next;
        ListNode *p = dummy;
        while (p->next && p->next-> val <= head->val) p = p->next;

        head->next = p->next;
        p->next = head;

        head = next;
    }
    return dummy->next;
}

void print(ListNode *head) {
    ListNode *p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    } 
    cout << endl;
}
int main() {
    vector<int> nums = {3, 2, 1, 5, 3, 3, 7, 6, 7, 9, 8, 10};
    //for (int x : nums) cout << x << " "; cout << endl;

    //bubble_sort(nums);
    //selection_sort(nums);
    //insert_sort(nums);
    //heap_sort(nums);
    //quick_sort(nums);
    //merge_sort(nums);

    ListNode *list = new ListNode(nums[0]);
    ListNode *p = list;
    for (int i = 1; i < nums.size(); ++i) {
        p->next = new ListNode(nums[i]);    
        p = p->next;
    }

    print(list);
    ListNode *res = quickSort(list);
    print(list);

    //for (int x : nums) cout << x << " "; cout << endl;
}