将链表内整形数据排序在不使用STL的情况下c++

在不使用STL的情况下，可以使用冒泡排序、插入排序、选择排序、快速排序等算法对链表内的整形数据进行排序。

1. 冒泡排序：

冒泡排序是一种简单的排序算法，其基本思想是通过不断交换相邻元素的位置来进行排序。具体实现如下：

void bubbleSort(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    bool flag = true;
    while (flag) {
        flag = false;
        Node* p = head->next;
        while (p->next != nullptr) {
            if (p->data > p->next->data) {
                int tmp = p->data;
                p->data = p->next->data;
                p->next->data = tmp;
                flag = true;
            }
            p = p->next;
        }
    }
}

2. 插入排序：

插入排序是一种稳定的排序算法，其基本思想是将一个元素插入已排好序的数组或链表中。具体实现如下：

void insertSort(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* p = head->next->next;
    head->next->next = nullptr;
    while (p != nullptr) {
        Node* q = head;
        while (q->next != nullptr && q->next->data < p->data) {
            q = q->next;
        }
        Node* tmp = q->next;
        q->next = p;
        p = p->next;
        q->next->next = tmp;
    }
}

3. 选择排序：

选择排序是一种简单的排序算法，其基本思想是每次选择最小的元素放到已排序部分的末尾。具体实现如下：

void selectSort(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* p = head->next;
    while (p != nullptr) {
        Node* q = p->next;
        Node* min = p;
        while (q != nullptr) {
            if (q->data < min->data) {
                min = q;
            }
            q = q->next;
        }
        int tmp = p->data;
        p->data = min->data;
        min->data = tmp;
        p = p->next;
    }
}

4. 快速排序：

快速排序是一种分治的排序算法，其基本思想是选定一个基准元素，将小于基准元素的元素放在左边，大于基准元素的元素放在右边，然后对左右两部分分别进行递归排序。具体实现如下：

Node* partition(Node* low, Node* high) {
    int pivot = low->data;
    Node* i = low;
    Node* j = low->next;
    while (j != high->next) {
        if (j->data < pivot) {
            i = i->next;
            int tmp = i->data;
            i->data = j->data;
            j->data = tmp;
        }
        j = j->next;
    }
    int tmp = low->data;
    low->data = i->data;
    i->data = tmp;
    return i;
}

void quickSort(Node* low, Node* high) {
    if (low == nullptr || high == nullptr || low == high) {
        return;
    }
    Node* pivot = partition(low, high);
    quickSort(low, pivot);
    quickSort(pivot->next, high);
}

void quickSort(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    Node* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }
    quickSort(head, tail);
}