概述
对于数组来说实现排序是很容易的，因为数组的数据元素的逻辑地址是连续的，并且通过下标的改变就可以轻松交换位置。
但在链表中，每个节点的逻辑地址是不确定的，所以没法直接通过索引直接映射来交换位置。
实现
在链表中实现排序的方法可以用 静态链表、通过索引按链表顺序查找结点。第二种方法明显开销较大，因为每一次通过索引建立结点的关系来查找结点都需要进行遍历。不过可以进行动态缓存来降低开销。
这两种方法都需要进行额外的开销。在下面我直接采取结点间的逻辑关系来得到对应的结点。
本文链表结构与代码见文章C/C++线性表实现(顺序存储与链式存储)
冒泡排序代码：
class seq_IntegerLinkList:public seq_LinkList<int>
{
public:
void Sorted(bool is_asc);
};
void seq_IntegerLinkList::Sorted(bool is_asc=true)
{
if (length<=1)
{
return;
}
LinkNode* prior=head;//前一个 注意：这里实现的链表结构 使用head->next指向头结点
LinkNode* cur;//当前指向
LinkNode* next;//后一个
for (int i = 0; i < length-1; i++)
{
for (int j = 0; j < length-i-1; j++)
{
cur = prior->next;//前一个的直接后续得到当前遍历的节点
next = cur->next;//cur的直接后续得到下一个节点
if (cur->data > next->data)
{
//更新节点指向
cur->next = next->next;
next->next = cur;
prior->next = next;
}
//根据冒泡排序每一轮选出一个最大的值
//如果i等于0时，直接更新尾指针指向当前结点
if (i == 0)
{
last->next = cur;
}
//prior指针向后移。
prior=prior->next;
}
//每一轮结束 从头开始。所以prior指向head
prior=head;
}
}
注意：这里实现的链表结构 使用head->next指向头结点。prior指针代表前一个。cur指针代表当前内层正在遍历的结点。next指针代表cur指针的直接后续。通过prior cur next之间的链式结构逻辑关系进行结点交换。每一轮选出一个最大的值并作为表尾。
主程序入口测试
/*
* @Author : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
* @Date : 2023-04-06 20:25:10
* @LastEditors : unity-mircale 9944586+unity-mircale@user.noreply.gitee.com
* @LastEditTime : 2023-04-07 22:12:12
* @FilePath : /DS2/source/Program.cpp
* @Description : 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
*/
#include <stdlib.h>
#include <iostream>
#include "seq_LinkList.h"
#include "seq_IntegerLinkList.h"
#include "stdio.h"
using namespace std;
template<class T>
void PRINTF_SEQUENCE(seq_LinkList<T> seq);
void Test01();
void Test02();
int main()
{
Test02();
system("pause");
}
template<class T>
void PRINTF_SEQUENCE(seq_LinkList<T> seq)
{
int length=seq.getlength();
for (int i = 0; i < length; i++)
{
cout<<seq.get(i)<<endl;
}
}
void Test01()
{
seq_LinkList<int> seq;
seq.ADD(11);
seq.ADD(12);
seq.ADD(13);
PRINTF_SEQUENCE(seq);
seq.INSERT(1,22);
cout<<"INSERT:"<<endl;
PRINTF_SEQUENCE(seq);
seq.REMOVEAT(2);
cout<<"REMOVEAT:"<<endl;
PRINTF_SEQUENCE(seq);
}
void Test02()
{
seq_IntegerLinkList seqIntegerList;
seqIntegerList.ADD(15);
seqIntegerList.ADD(11);
seqIntegerList.ADD(13);
PRINTF_SEQUENCE(seqIntegerList);
cout<<"Sorted:"<<endl;
seqIntegerList.Sorted();
PRINTF_SEQUENCE(seqIntegerList);
seqIntegerList.INSERT(1,22);
seqIntegerList.INSERT(1,1);
seqIntegerList.INSERT(1,14);
cout<<"INSERT:"<<endl;
PRINTF_SEQUENCE(seqIntegerList);
cout<<"Sorted:"<<endl;
seqIntegerList.Sorted();
PRINTF_SEQUENCE(seqIntegerList);
seqIntegerList.REMOVEAT(2);
cout<<"REMOVEAT:"<<endl;
PRINTF_SEQUENCE(seqIntegerList);
}测试结果：
示例文件
