c++定义数据结构类型实现分别用简单插入排序、直接选择排序、冒泡排序、二路归并排序、快速排序方法进行排序并输出排序结果。 测试数据：产生10个1~999之间的随机整数。

好的，以下是您需要的代码：

#include <iostream>
#include <ctime>
using namespace std;

struct Node {
    int val;
    Node* next;
};

void printList(Node* head) {
    Node* ptr = head;
    while (ptr != nullptr) {
        cout << ptr->val << " ";
        ptr = ptr->next;
    }
    cout << endl;
}

void insertSort(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* sortedTail = head; // 已排序部分的尾节点
    Node* ptr = sortedTail->next; // 待排序节点
    sortedTail->next = nullptr;
    while (ptr != nullptr) {
        Node* cur = ptr; // 当前待排序节点
        ptr = ptr->next;
        if (cur->val < head->val) { // 特判头节点
            cur->next = head;
            head = cur;
            continue;
        }
        Node* prev = head; // 已排序部分的前一个节点
        while (prev != sortedTail && prev->next->val <= cur->val) {
            prev = prev->next;
        }
        cur->next = prev->next;
        prev->next = cur;
        if (cur->next == nullptr) { // 更新尾节点
            sortedTail = cur;
        }
    }
}

void selectionSort(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* sortedTail = head; // 已排序部分的尾节点
    while (sortedTail->next != nullptr) {
        Node* prev = sortedTail; // 已排序部分的前一个节点
        Node* minPrev = prev; // 最小元素节点的前一个节点
        Node* ptr = prev->next; // 待排序节点
        while (ptr != nullptr) {
            if (ptr->val < minPrev->next->val) {
                minPrev = prev;
            }
            prev = prev->next;
            ptr = ptr->next;
        }
        if (minPrev != sortedTail) { // 将最小元素移动到已排序部分的尾部
            Node* minNode = minPrev->next;
            minPrev->next = minNode->next;
            minNode->next = nullptr;
            sortedTail->next = minNode;
            sortedTail = minNode;
        } else { // 最小元素就是已排序部分的尾节点
            sortedTail = sortedTail->next;
        }
    }
}

void bubbleSort(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    bool swapped = true;
    while (swapped) {
        swapped = false;
        Node* prev = nullptr; // 用于交换相邻节点的前一个节点
        Node* ptr = head; // 待排序节点
        while (ptr->next != nullptr) {
            if (ptr->val > ptr->next->val) { // 交换相邻节点
                Node* next = ptr->next;
                ptr->next = next->next;
                next->next = ptr;
                if (prev == nullptr) { // 更新头节点
                    head = next;
                } else {
                    prev->next = next;
                }
                prev = next;
                swapped = true;
            } else {
                prev = ptr;
                ptr = ptr->next;
            }
        }
    }
}

void mergeSort(Node*& head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* mid = head; // 找到链表的中间节点
    Node* ptr = head->next;
    while (ptr != nullptr) {
        ptr = ptr->next;
        if (ptr != nullptr) {
            mid = mid->next;
            ptr = ptr->next;
        }
    }
    Node* right = mid->next; // 右侧链表的头节点
    mid->next = nullptr; // 将链表分为两个部分
    mergeSort(head); // 递归排序左侧链表
    mergeSort(right); // 递归排序右侧链表
    // 归并两个有序链表
    Node* dummy = new Node{0, nullptr};
    Node* tail = dummy;
    while (head != nullptr && right != nullptr) {
        if (head->val < right->val) {
            tail->next = head;
            head = head->next;
        } else {
            tail->next = right;
            right = right->next;
        }
        tail = tail->next;
    }
    tail->next = (head != nullptr) ? head : right;
    head = dummy->next;
    delete dummy;
}

Node* partition(Node* head, Node* tail, Node*& newHead, Node*& newTail) {
    Node* pivot = tail; // 选取尾节点为枢轴
    Node* prev = nullptr;
    Node* cur = head;
    while (cur != pivot) {
        if (cur->val < pivot->val) { // 将小于枢轴的元素移到前面
            if (newHead == nullptr) {
                newHead = cur;
            }
            prev = cur;
            cur = cur->next;
        } else { // 将大于等于枢轴的元素移到后面
            if (prev != nullptr) {
                prev->next = cur->next;
            }
            Node* next = cur->next;
            cur->next = nullptr;
            tail->next = cur;
            tail = tail->next;
            cur = next;
        }
    }
    if (newHead == nullptr) {
        newHead = pivot;
    }
    newTail = tail;
    return pivot;
}

Node* quickSortImpl(Node* head, Node* tail) {
    if (head == nullptr || head == tail) {
        return head;
    }
    Node* newHead = nullptr;
    Node* newTail = nullptr;
    Node* pivot = partition(head, tail, newHead, newTail);
    if (newHead != pivot) {
        Node* ptr = newHead;
        while (ptr->next != pivot) {
            ptr = ptr->next;
        }
        ptr->next = nullptr;
        newHead = quickSortImpl(newHead, ptr);
        ptr = newHead;
        while (ptr->next != nullptr) {
            ptr = ptr->next;
        }
        ptr->next = pivot;
    }
    pivot->next = quickSortImpl(pivot->next, newTail);
    return newHead;
}

void quickSort(Node*& head) {
    head = quickSortImpl(head, nullptr);
}

int main() {
    srand(time(nullptr));
    Node* head = nullptr;
    for (int i = 0; i < 10; i++) {
        int val = rand() % 999 + 1;
        head = new Node{val, head};
    }
    cout << "Original list: ";
    printList(head);
    insertSort(head);
    cout << "After insert sort: ";
    printList(head);
    selectionSort(head);
    cout << "After selection sort: ";
    printList(head);
    bubbleSort(head);
    cout << "After bubble sort: ";
    printList(head);
    mergeSort(head);
    cout << "After merge sort: ";
    printList(head);
    quickSort(head);
    cout << "After quick sort: ";
    printList(head);
    return 0;
}

这段代码实现了简单插入排序、直接选择排序、冒泡排序、二路归并排序、快速排序算法，并对产生的 10 个随机整数进行了排序。