单链表排序的时间复杂度是什么？单链表上难以实现的排序方法

：暂无数据 2026-03-26 15:20:01 ：0

本文旨在解决您关于单链表排序的两大困惑：一是理清基本概念，二是深入解析单链表排序的时间复杂度是什么。内容干练，直奔主题。

本文目录

单链表排序的时间复杂度是什么
单链表上难以实现的排序方法
单链表排序问题
有一个带头结点的单链表L,设计一个算法使其元素递增有序排列
对单链表中的数据进行排序，用哪种算法比较好
一单链表中元素无序，编写算法将之排成有序序列

单链表排序的时间复杂度是什么

o(NlogN)，虽然不是所有的高级排序算法都适用于单链表，但是还是部分适用的，比如归并排序，希尔排序，和快速排序的特定实现。

就算这些算法你统统不考虑，还有一种简单粗暴的方法：

将链表复制到数组
排序数组
将数组还原成链表

这三步的复杂度是O(n+nlogn+n)= O(nlogn)

单链表上难以实现的排序方法

单链表上难以实现的排序方法是快速排序。根据查询相关公开信息显示，单链表上难以实现的排序方法是快速排序法，包括堆排序和希尔排序，使用数组制作的静态树，使用单链表进行该算法。

#include 《iostream》
#include 《ctime》
#define ERROR 0;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//建立链表L2，顺序插入
//输入：1，2，3，4。输出1，2，3，4
void CreateList_L2(LinkList &L,int n)
{ int i;
L=(LinkList)malloc(sizeof(LNode));
L-》data=n; L-》next=NULL;
LinkList p,q;
//q=(LinkList)malloc(sizeof(LNode));
q=L;
for(i=n;i》0;i--)
{
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p-》data);
q-》next=p;
p-》next=NULL;
q=p;
}//for
}//CreateList_L2
//按顺序打印链表
void print(LinkList L)
{ LinkList p;
p=L-》next;
while(p!=NULL)
{ printf("\t%d",p-》data);
p=p-》next;
}//while
}//print
//链表排序，非递减顺序排列
void Listsort_L(LinkList &L)
{
LinkList p,q;
ElemType temp;
for(p=L-》next;p!=NULL;p=p-》next)
{

for(q=p-》next;q!=NULL;q=q-》next)
{

if(p-》data》q-》data)
{

temp=p-》data;
p-》data=q-》data;
q-》data=temp;
}

}

}
}
void main()
{
int n;
LinkList L;
printf("how many numbers you want to input in L:");
scanf("%d",&n);
CreateList_L2(L,n);
Listsort_L(L);
printf("排序后的L是：");
print(L);
}

有一个带头结点的单链表L,设计一个算法使其元素递增有序排列

/* 插入排序法 */
void sort(Linklist *&L)
{
    LinkList *p=L-》next, *q, *r;
    if(p!=NULL)
    {
        /* 把链表分成两条，一条已经排序好了(L)，一条待排序(p)*/
        r=p-》next;
        p-》next=NULL;
        p=r;
        /* 对于所有待排序的元素 */
        while(p!=NULL)
        {
            /*把p链表的第一个元素插入到L，并且将它从p中移除*/
            r=p-》next;  //r指向p的第二个元素
            /* 找到合适的插入点 */
            q=L;
            while(q-》next!=NULL && q-》next-》data 《 p-》data)
                q=q-》next;
            /* 在q后面插入p */
            p-》next=q-》next;
            q-》next=p;
            /* 现在p的第一个元素已经被移到L中合适的位置了 */
            p=r;
        }
    }
}

对单链表中的数据进行排序，用哪种算法比较好

typedef struct __LINK
{
int data;
struct __LINK *next;
} LinkNode_t;
//冒泡排序单连表, 交换值方式
bool LinkSort( LinkNode_t* &head )
{
assert( head != NULL );
bool change = true;
LinkNode_t* p = head;
LinkNode_t* pStop = head-》next;
int ifirst = 0;
while ( pStop && pStop-》next )
{
pStop = pStop-》next;
}
LinkNode_t* pFlag = head;
while ( change )
{
change = false;
for ( p = head-》next; p != pStop; p = p-》next )
{
if ( p-》data 《 p-》next-》data )
{
int value = p-》data;
p-》data = p-》next-》data;
p-》next-》data = value;
change = true;
}
if ( p-》next == pStop ) pFlag = p;
}
pStop = pFlag;
}
return true;
}

一单链表中元素无序，编写算法将之排成有序序列

    由冒泡排序得到启示，每趟均从头节点开始扫描，比较相邻两节点的数据，
满足特定要求时进行节点交换。
    需要注意的是，必须有一个指针保存当前节点的前一个位置，这样在交换
节点后链表不会断开；并且要指定一个哨兵节点作为每趟比较的终结点，该哨
兵节点实际上就是有序区的首节点。
struct Node {
    int data;
    Node *next;
};
/* 因为排序后头结点指针可能发生改变，所以参数是二级指针 */
void listSort(Node **head)
{
    if(head == NULL || *head == NULL)
        return;

    Node *cur, *post, *pre, *sentinel = NULL;  // sentinel 标记有序区的首个节点
    bool sorted;

    do {
        pre = NULL;
        cur = *head;
        sorted = true;

        /* 反复用当前节点 cur 与下一个节点 post 进行比较 */
        while((post = cur-》next) != sentinel) {
            if(cur-》data 》 post-》data) {
                sorted = false;  // 发生交换，则仍未有序
                cur-》next = post-》next;
                post-》next = cur;

                if(pre != NULL)
                    pre-》next = post;
                pre = post;

                if(cur == *head)
                    *head = post;  // 保证头指针指向最小的节点
            } else {
                pre = cur;
                cur = post;
            }
        }
        sentinel = cur;  // cur 为该趟排好序的节点
    } while(!sorted);    // 若未发生交换，则已经有序
}