单链表的冒泡排序

冒泡排序是最基本也是最简单的一种排序，时间复杂度为O(n^2)，我们可以使用它来对单链表进行排序操作。

链表定义

本次链表采用以下的结构定义：

typedef struct node{
	int element;
	struct node *link;
}Node;
typedef struct headerList{
	Node *head;
	int n;
}HeaderList;

算法一

冒泡排序算法的原始思想：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。

数组代码实现

void sort(int a[], int length){
    int i, j, temp;
    for (j = 0; j < length - 1; j++){
        for (i = 0; i < length - 1 - j; i++){
            if(a[i] > a[i + 1]){
                temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }

将上述思想套用到链表中，我们知道在冒泡排序中要交换数据，所以链表中需要通过指针指向的改变来达到交换的目的，而不是简单节点数据交换。两个节点要想交换位置，必须用2个以上的指针来表明指示要交换节点的前驱和本身，必要时用到后继指针。

链表冒泡排序

void bubbleSort(HeaderList &L) {
	if (!L.head->link) {
        cout << "该链表无节点！" << endl;
        return;
    }
    Node* tail = NULL;   //（tail指向上一轮找出最大值的位置）
    while (tail != L.head->link->link) { //最大值已到链表第二位置
        Node* p = L.head;  //外循环开始，先指向头节点
        Node* q = p->link;  
        while (q->link != tail) {   //下个节点是上一轮最大值的位置
			if (q->element > q->link->element) { 
                p->link = q->link; //让当前节点的先驱指向相邻的节点
                Node* temp = q->link->link; //保存相邻节点的后继
                p->link->link = q;     //令相邻节点的后继等于当前节点
                q->link = temp;  //当前节点指向先前保存的后继
                p = p->link;   //因为mid交换以后，已经后移了一步，所以这里只需前驱后移
            }
            else {         //未交换，手动后移这两个指针
                p = q;
                q = q->link;
            }
        }
        tail = q;   //tail指向这一轮找出最大值的位置。
    } 
}

算法二

另一种冒泡排序的思想，从所有的第一个开始，以第一个为基准，与剩余所有的数比较，选出最小的放在第一位，之后以第二个位置为基准，与剩余所有的数比较，选出最小的放在第二位，直到全部遍历完。

数组代码实现

void sort(int a[], int n){
   int i, j, temp;
   for (i = 0; i < n - 1; i++){
       for (j = i + 1; j < n ; j++){
           if(a[j] < a[i]){
               temp = a[i];
               a[i] = a[j];
               a[j] = temp;
           }
       }
   }

链表冒泡排序

void bubbleSort(HeaderList &L) {
    if (!L.head->link) {
        cout << "该链表无节点！" << endl;
        return;
    }
	Node* pre = L.head;    
    Node* mid = pre->link, *after,*afterPre,*temp;//指向第一个节点，声明内循环中要用的指针
    while (mid) {          
        after = mid->link;  //冒泡第二种形式的思想，让外循环的一个节点与剩余的所有节点比较
        afterPre = mid;     //该节点的前驱指针，方便我们进行交换
        while (after) {     //
			if (mid->element > after->element) { 
                afterPre->link = mid;       
                pre->link = after;         //首先让这两个节点的前驱变了
                temp = mid->link;         //保留外循环中要比较的节点的后继，方便交换过来的节点正确的接上
                mid->link = after->link;  //接上交换过来的后继位置
                after->link = temp;      //接上交换过来的后继位置
                temp = mid;       //mid 和 after 所指向的节点在 链表中已交换位置，所以mid和after指针的地址交换
                mid = after;     //
                after = mid;    //将mid和after的指针的值交换，才能继续以mid所指向的节点当作外循环的基准节点
                               //after才能正确作为内循环要移动并比较的节点指针。
            }
            afterPre = after;   
            after = after->link;  //后移前驱和本身
        }
        pre = mid; 
        mid = mid->link;  //外循环需要后移一步，继续下一轮内循环遍历
    }
}