搬运自我的CSDN https://blog.csdn.net/u013213111/article/details/88669851
！！！Attention：以下操作中的单链表均带有头结点！！！
1.冒泡排序
首先要获取单链表的长度n。
冒泡排序的基本思路是：从某一方向开始，依次两两比较，把小的放左边，大的放右边。由于单链表的单向性，这里的“冒泡”并不是将更小的元素移到更前的位置，而是反过来，将更大的元素移到更后的位置。程序的主体由两个嵌套的循环构成，外部循环要进行n-1次，内部的循环用于进行相邻元素之间的两两比较。经过第一次外部循环后，最大的元素被移至链表的最末；以此类推。
1 void BubbleSort(Lnode *head) 2 { 3 Lnode *current, *prev, *tmp; 4 current = head; 5 int n = 0; 6 while (current != NULL) { //Find length of the list, length = n 7 n++; 8 current = current->next; 9 } 10 for (int i = 0; i < n; i++) { //n-1 cycles 11 prev = head; //Every cycle begins from head 12 current = head->next; 13 for (int j = n - 1- i; j > 0; j--) { //n-1-i comparisons in every cycle 14 if (current->next != NULL && current->data > current->next->data) { 15 tmp = current->next; 16 prev->next = tmp; 17 current->next = tmp->next; 18 tmp->next = current; 19 prev = tmp; 20 } 21 else { 22 prev = current; 23 current = current->next; 24 } 25 } 26 } 27 }
2.插入排序
引自单链表的插入排序：
插入排序的基本思想：将一个节点插入到一个有序的序列中。对于链表而言，要依次从待排序的链表中取出一个节点插入到已经排好序的链表中，也就是说，在单链表插入排序的过程中，原链表会截断成两部分，一部分是原链表中已经排好序的节点，另一部分是原链表中未排序的节点，这样就需要在排序的过程中设置一个当前节点，指向原链表未排序部分的第一个节点。
思路：
1.定义三个指针，current记录未排序部分的第一个节点，prev用于遍历已排序部分，tail记录已排序部分的最后一个节点。
2.遍历已排序部分，找出是否存在比current大的节点，若存在，则将该节点的前驱节点记为prev，退出遍历。
3.若上述节点存在，则将current插入到已排序部分，注意在此之前要将tail->next指向正确的节点。
4.若上述节点不存在，则直接将tail向后移动一位即可。
5.循环2-4步，直至tail移动到最后一个节点。注意在每次循环的开始要将current移动到tail->next的位置。
代码如下：
1 void InsertSort(Lnode *head) 2 { 3 Lnode *current, *prev, *tail; 4 prev = current = tail = head; 5 while (tail->next != NULL) { 6 prev = head; 7 current = tail->next; //current is the begin of unsorted part 8 while (prev->next != current && prev->next->data < current->data) 9 prev = prev->next; //Find first element which is bigger than current in sorted part 10 if (prev != tail) { //There exists an element in sorted part which is bigger than current 11 tail->next = current->next; 12 current->next = prev->next; 13 prev->next = current; 14 } 15 else //Every sorted element is smaller than current 16 tail = current; //tail is the end of sorted part 17 } 18 }
由于单链表只能从前向后找，在实现上与数组有一些不同之处，但是基本思想是一样的。下面这个动图是从后往前找到插入点，供参考。
原文：https://www.cnblogs.com/lyrich/p/10586157.html