C/C++链表冒泡排序实现

Miracle • 2023-04-16 • C++, 数据结构与算法 • 473 阅读

概述

对于数组来说实现排序是很容易的，因为数组的数据元素的逻辑地址是连续的，并且通过下标的改变就可以轻松交换位置。

但在链表中，每个节点的逻辑地址是不确定的，所以没法直接通过索引直接映射来交换位置。

实现

在链表中实现排序的方法可以用静态链表、通过索引按链表顺序查找结点。第二种方法明显开销较大，因为每一次通过索引建立结点的关系来查找结点都需要进行遍历。不过可以进行动态缓存来降低开销。

这两种方法都需要进行额外的开销。在下面我直接采取结点间的逻辑关系来得到对应的结点。

本文链表结构与代码见文章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);
}

测试结果：