试以单向链表为存储结构实现简单选择排序的算法。
实现递增排序，首先选择一个元素作为第一个比较值，遍历其他所有的元素，如果发现其他元素中有比它小的元素，则交换两个元素，这样每一趟都能找到符合要求的最小值
正经的单向链表排序，不是换数据的那种！
思想是选择排序的思想，但问题在于单链表结构不同于数组的直接交换，需要断链和重新成链等各种操作，稍不留神就直接G了
具体实现步骤如下：
- 初始化指针变量a和b，它们都指向链表的头节点。
- 外层循环遍历链表，直到节点b是链表中的最后一个节点。
- 内层循环遍历以节点b为起始的子链表，寻找其中最小的节点d。
- 如果节点b的值大于节点d的值，说明需要将节点d插入到节点b之前。
- 根据不同情况进行节点的移动和连接操作：
- 如果节点d紧跟在节点b后面，分为两种情况：
- 如果节点b是链表的头节点，则直接将节点d移动到节点b之前，并调整头节点的指针。
- 如果节点b不是链表的头节点，则将节点d移动到节点b之前，并更新a的next指针。
- 如果节点b和节点d之间有其他节点，也分为两种情况：
- 如果节点b是链表的头节点，则将节点d移动到节点b之前，并更新头节点的指针。
- 如果节点b不是链表的头节点，则将节点d移动到节点b之前，并更新a的next指针。
- 如果节点d紧跟在节点b后面，分为两种情况：
- 完成内层循环后，更新a和b的指针，继续下一轮循环，直到整个链表都被排序完成。
- 最后返回排序后的链表头节点。
下面是C语言写法：
typedef struct Node
{
int data;
struct Node *next;
}LinkNode;
LinkNode* selectionSort(LinkNode* head)
{
LinkNode *a, *b, *c, *d, *r; // 声明指针变量 a, b, c, d, r
a = b = head; // 初始化指针变量 a, b，它们指向链表头部
// 当 b 不是最后一个节点时执行循环
while (b->next) {
c = d = b->next; // 初始化指针变量 c, d，它们指向 b 的下一个节点
// 当 d 指向一个有效节点时执行循环
while (d) {
if (b->data > d->data) { // 如果 b 的值大于 d 的值
if (b->next == d) { // 如果 d 紧跟在 b 后面
if (b == head) { // 如果 b 是链表的头节点
// 将 d 移动到 b 的前面
b->next = d->next;
d->next = b;
// 交换 b 和 d 的指针
r = b;
b = d;
d = r;
c = d; // 更新 c
// 更新链表头部
head = b;
// 跳到下一个元素，因为它已经是有序的
d = d->next;
}
else { // 如果 b 不是链表的头节点
// 将 d 移动到 b 的前面
b->next = d->next;
d->next = b;
a->next = d;
// 交换 b 和 d 的指针
r = b;
b = d;
d = r;
c = d; // 更新 c
// 跳到下一个元素，因为它已经是有序的
d = d->next;
}
}
else { // 如果 b 和 d 之间有一些非零节点
if (b == head) { // 如果 b 是链表的头节点
// 交换 b->next 和 d->next
r = b->next;
b->next = d->next;
d->next = r;
c->next = b;
// 交换 b 和 d 的指针
r = b;
b = d;
d = r;
c = d; // 更新 c
// 跳到下一个元素，因为它已经是有序的
d = d->next;
// 更新链表头部
head = b;
}
else { // 如果 b 不是链表的头节点
// 交换 b->next 和 d->next
r = b->next;
b->next = d->next;
d->next = r;
c->next = b;
a->next = d;
// 交换 b 和 d 的指针
r = b;
b = d;
d = r;
c = d; // 更新 c
// 跳到下一个元素，因为它已经是有序的
d = d->next;
}
}
}
else { // 如果 b 的值不大于 d 的值
// 更新 c 并跳到下一个元素，因为它已经是有序的
c = d;
d = d->next;
}
}
a = b; // 更新 a
b = b->next; // 更新 b
}
return head; // 返回排序后的链表头部
}
下面是Java语言写法：
public class Main {
public static class Node {
int data;
Node next;
};
public static Node selectionSort(Node head)
{
Node a, b, c, d, r;
a = b = head;
while (b.next != null) {
c = d = b.next;
while (d != null) {
if (b.data > d.data) {
if (b.next == d) {
if (b == head) {
b.next = d.next;
d.next = b;
r = b;
b = d;
d = r;
c = d;
head = b;
d = d.next;
}
else {
b.next = d.next;
d.next = b;
a.next = d;
r = b;
b = d;
d = r;
c = d;
d = d.next;
}
}
else {
if (b == head) {
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
r = b;
b = d;
d = r;
c = d;
d = d.next;
head = b;
}
else {
r = b.next;
b.next = d.next;
d.next = r;
c.next = b;
a.next = d;
r = b;
b = d;
d = r;
c = d;
d = d.next;
}
}
}
else {
c = d;
d = d.next;
}
}
a = b;
b = b.next;
}
return head;
}
// 新建Node节点
static Node newNode(int val)
{
Node temp = new Node();
temp.data = val;
temp.next = null;
return temp;
}
}
示例
以 -2-0-0-3-5-1- 单链表为例
由于动态演示图较大，csdn无法上传，请移步至 https://gitee.com/xjk2000/image-storage/blob/master/1.gif
Java代码测试执行：
执行结果：
