单链表的冒泡，选择和快速排序

单链表的冒泡，选择和快速排序

本文详细介绍了在单链表中实现冒泡排序、选择排序和快速排序的算法。通过代码示例和图解，清晰地展示了每种排序算法在链表中的具体实现方式。

单链表的冒泡，选择和快速排序

选择排序

选择排序的原理是在每一趟遍历时找出所有数据中最小或者最大的那一个值，然后放到开头或者末尾，在链表里面也是同样的道理，在下面的代码当中，遍历了一遍链表之后，我们找出了最大的那个值，然后用头插法插入链表的开头，关键的地方是链表不能查找到上一个节点，所以我们需要用两个指针，一个保留最大值，一个保留最大值的上面一个节点。

if(tail->next != max) {
    max_prev->next = max->next;
    max->next = tail->next;
    tail->next = max;
}

这部分就是遍历了一遍链表之后，我们通过改链操作将目标值插入头节点之后，下一次开始遍历的时候就会跳过这个已查找过的值，对剩下的值继续操作，下面是完整的代码：

void SelectSort(struct node* head) {
    struct node *tail, *prev, *cur, *max, *max_prev;
    for(tail = head; tail && tail->next; tail = tail->next) {
        max = tail->next;
        for(cur = tail->next, prev = tail; cur != NULL; prev = cur, cur = cur->next) {
            if( cur->num > max->num) {
                max = cur;
                max_prev = prev;
            }
        }
        if(tail->next != max) {
            max_prev->next = max->next;
            max->next = tail->next;
            tail->next = max;
        }
    }
}

遍历一遍后找到最大值：

冒泡排序

冒泡排序的原理是每次遍历都能将最大值或者最小值沉底，以此来实现排序。在数组里面，我们可以通过两两交换来实现沉底这个操作，但是在链表当中我们做不到，所以我们依然需要两个指针来进行操作，为了实现升序，我们这里用cur指向当前的节点，当cur指向的值比后一个节点指向的值要大的时候，我们需要交换这两个节点：

if((cur->num) > (cur->next->num)) {
    prev->next = cur->next;
    cur->next = cur->next->next;
    prev->next->next = cur;
    cur = prev->next;
}

最后将最大值沉底之后，我们便不需要再对这个节点进行操作，需要将尾节点指针指向这个最大值，然后完整代码如下：

void BubbleSort(struct node* head) {
    struct node *tail, *prev, *cur;
    tail = NULL;
    while((head->next->next) != tail) {
        prev = head;
        cur = head->next;
        while((cur->next) != tail) {
            if((cur->num) > (cur->next->num)) {
                prev->next = cur->next;
                cur->next = cur->next->next;
                prev->next->next = cur;
                cur = prev->next;
            }
            cur = cur->next;
            prev = prev->next;
        }
        tail = cur;	//更新尾节点
    }
}

交换位置的改链操作：

完成后：

快速排序

快速排序使用分治的思想，遍历之前先设定一个基准值，然后遍历一次，将所有数分成两部分，一部分都是小于这个基准值，另一部分都是大于这个基准值，然后递归操作，这样子所有数都会归为有序

我们要做的有两件事情:

1. 将所有的数分成两部分；
2. 对左右两个部分递归排序；

显然，最关键的部分就是将数分成两个部分。对于数组我们可以定义左右两个指针，然后向中间靠，把数组分成两部分，但是因为链表的单向性，我们还是不能实现这个操作。这个时候我们就不考虑像数组那样直接交换目标值，我们可以把大于基准值的节点用头插法放到前面，这样子到了最后，我们的链表也能被分成两个部分

这里是关键代码：

if(hole->data < cur->data) {
    prev->next = cur->next;
    cur->next = head->next;
    head->next = cur;
}

void QuickSort(struct Node* head, struct Node* tail) {
    if(head == NULL || head->next == tail || head->next->next == tail) {	//如果链表为空，或者只有一个节点就不用排序了
        return;
    }
    struct Node *cur, *prev, *hole;
    hole = head->next;	//设置基准值为第一个节点的值
    for(prev = hole, cur = hole->next; cur != NULL && cur != tail; cur = prev->next) {	//从基准值的下一个值开始遍历
        if(hole->data < cur->data) {	//若是大于基准值，就插入到头节点之后
            prev->next = cur->next;
            cur->next = head->next;
            head->next = cur;
        } else {
            prev = cur;	//要保持两个指针相邻，方便改链操作
        }
    }
    
    QuickSort(head,hole);
    QuickSort(hole,tail);
}

交换前：

改链：

完成后：