带头结点的单链表实现极快、冒泡、直接插入/选择排序
结构体
-
typedef int ElemType;
-
typedef struct LNode {
-
ElemType data;
-
struct LNode* next;//指针域
-
}LNode, * LinkList;
快速排序
-
LinkList Quicksort(LinkList* listHead, LinkList* listTail)
-
{
-
LNode* current;
-
LNode* lessHead = NULL, * lessTail = NULL, * moreHead = NULL, * moreTail = NULL;
-
current = (*listHead)->next;//每次取首节点为枢纽,current指向第二个节点用于遍历
-
if ((*listHead)->next != NULL)//当链表节点数不为1时(说明链表未排好序)
-
{
-
for (current = (*listHead)->next; current; current = current->next)
-
{
-
if (current->data < (*listHead)->data)
-
{
-
if (lessHead == NULL)
-
lessHead = current;
-
else
-
lessTail->next = current;
-
lessTail = current;
-
}//current结点key小于枢纽key时放入less链表
-
else
-
{
-
if (moreHead == NULL)
-
moreHead = current;
-
else
-
moreTail->next = current;
-
moreTail = current;
-
}//current结点key大于枢纽key时放入more链表
-
}
-
//根据枢纽结点将T链表分为less和more两个链表
-
if (moreTail)
-
moreTail->next = NULL;
-
if (lessTail)
-
lessTail->next = NULL;
-
//将more链表尾结点next域置空
-
if (moreHead != NULL)
-
{
-
moreTail->next = NULL;
-
Quicksort(&moreHead, &moreTail);
-
(*listHead)->next = moreHead;
-
*listTail = moreTail;
-
}
-
//若moreHead不空,则current为more链表的尾结点,对more链表进行递归处理,将more链表接在枢纽节点后
-
else
-
{
-
(*listHead)->next = NULL;
-
*listTail = *listHead;
-
}
-
//若moreHead为空,则只有less链表(即结点key全小于枢纽),将枢纽结点接在less节点后
-
if (lessHead != NULL)
-
{
-
lessTail->next = NULL;
-
Quicksort(&lessHead, &lessTail);
-
lessTail->next = *listHead;
-
*listHead = lessHead;
-
}
-
//若lesseHead不空,对less链表进行递归处理,再将枢纽节点接在less链表后
-
else
-
{
-
lessHead = *listHead;
-
}
-
//若lesseHead为空,则枢纽结点作为首节点
-
return lessHead;
-
}
-
else
-
return *listHead;
-
}
直接插入排序
-
//直接插入排序
-
void Insertsort1(LinkList& L) {
-
LNode* p = L->next, * q;
-
LNode* r = p->next;
-
p->next = NULL;
-
p = r;
-
while (p!=NULL)
-
{
-
r = p->next;
-
q = L;
-
while (q->next != NULL && q->next->data < p->data)
-
q = q->next;
-
p->next = q->next;
-
q->next = p;
-
p = r;
-
}
-
}
冒泡排序
-
void BubbleSort(LinkList &L)
-
{
-
LNode* r, *t, *p;
-
p = NULL;
-
-
while (L->next->next != p)
-
{
-
r = L;
-
t = L->next;
-
-
while (t->next != p)
-
{
-
if (t->data > t->next->data)
-
{
-
r->next = t->next;
-
t->next = t->next->next;
-
r->next->next = t;
-
t = r->next;
-
}
-
r = r->next;
-
t = t->next;
-
}
-
p = t;
-
}
-
-
}
直接选择
//选出最小值
LinkList MinList(LinkList &L) {
LinkList minp = L, p = L->next;//minp指向头结点
while (p != NULL) {
if ((minp->data) > (p->data)) {
minp = p;
}
p = p->next;
}
return minp;
}
//遍历链表并调用上述算法(选出最小值)
void SortList(LinkList& L) {
LNode* j, * r = L->next;//j指向链表中最小的结点,r指向链表的当前结点
int temp;//用于交换位置,设数据为整数
while (r->next != NULL) {
j = MinList(r);
if (j->data != r->data) {
temp = r->data;
r->data = j->data;
j->data = temp;
}
r = r->next;//如果当前结点数据就是最小值直接后移一位
}
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfijfib
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01