C++中怎么实现链表的排序算法

魁首哥

作者

C++中怎么实现链表的排序算法

本篇内容主要讲解“C++中怎么实现链表的排序算法”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++中怎么实现链表的排序算法”吧!

一、链表排序

最简单、直接的方式（直接采用冒泡或者选择排序，而且不是交换结点，只交换数据域）

//线性表的排序,采用冒泡排序,直接遍历链表voidListsort(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//作为一个临时量Node*p;Node*p1;//如果链表为空直接返回if(head->value==0)return;for(i=0;i<head->value-1;i++){L=head->next;for(j=0;j<head->value-i-1;j++){//得到两个值p=L;p1=L->next;//如果前面的那个比后面的那个大，就交换它们之间的是数据域if(p->value>p1->value){Elemtypetemp=p->value;p->value=p1->value;p1->value=temp;}L=L->next;}}}

因为排序中速度比较快的如快速排序是要求它们的数据域的地址是相连接的，它比较适合于顺序结构，而链式结构的时候，我们就只有使用只会进行前后两个比较多排序算法，比如冒泡排序等。我们这里是没有交换结点的一种排序方式，这种方式简单，明了，这样就是数组排序的时候是一样的。后面我会写通过交换结点的方式的排序。

下面我们就讨论讨论这个排序算法的时间复杂度了，因为它是使用冒泡排序的，它的时间只要消耗在那两重循环，所以时间复杂度为：O(n*n),这个效率实在是太低，下面我们对这个想(ˇˍˇ) 想～通过另外一种方式来实现链表的排序

二、另外一种链表排序方式

我们在讨论排序算法的时候，都是把数据存放在数组中进行讨论的，在顺序结构下，我们可以采取很多高效的排序算法，那么这个就是我们另外一种对链表排序的方式，先把链表的内容存放到数组中（时间为O(n)），然后，我们在对那个数组进行排序（最快为nlog(n)），最后，存放链表中（时间为O(n)）。通过计算，我们可以得到它的时间复杂为（O(nlogn)）,这个速度已经和顺序结构下差不多了，可以接受

voidListsort_1(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//如果链表为空直接返回if(head->value==0)return;Elemtype*copy=newElemtype[head->value];//变量链表，存放数组for(i=0;i<head->value;i++){L=L->next;copy[i]=L->value;}//调用STL中的sort函数sort(copy,copy+head->value);L=head;//存放回链表中for(i=0;i<head->value;i++){L=L->next;L->value=copy[i];}}

三、比较两种排序的效率

如图所示，在数据量为10000的时候，明显第二种排序算法消耗的时间比第一种快了28倍左右。

四、下面通过交换结点实现链表的排序

首先我们编写交换结点的函数，结点的交换主要就是考虑结点的指针域的问题，其中相邻两个结点是一种特殊的情况，要拿出来特别考虑。我们先画出结点交换的思路图，如下图

首先我们给出相邻两个结点交换的思路：

下面是普通情况下的交换如下图

//参数为头结点和需要交换的两个结点的位置（起点为1）voidswap_node(Node*&head,inti,intj){//位置不合法if(i<1||j<1||i>head->value||j>head->value){cout<<"请检查位置是否合法"<<endl;return;}//同一个位置不用交换if(i==j){return;}//相邻两个交换比较简单if(abs(i-j)==1){//位置靠前的那个结点的前一个结点Node*pre;if(i<j)pre=getitem(head,i);elsepre=getitem(head,j);//保存第一个结点Node*a=pre->next;//保存第二结点Node*b=a->next;//改变pre下一个结点的值pre->next=b;//必须先把b的下一个结点值给a先a->next=b->next;//让b的下一个结点等于ab->next=a;return;}//第一个结点前一个结点Node*a=getitem(head,i);//第二个结点的前一个结点Node*b=getitem(head,j);//第一个结点Node*p=a->next;//第二个结点Node*q=b->next;//第一个结点的下一个结点Node*p_next=p->next;//第二结点的下一个结点Node*q_next=q->next;//a的下一个结点指向第二个结点qa->next=q;//第二结点的下一个结点指向第一个结点的下一个结点q->next=p_next;//b的下一个结点指向第一个结点pb->next=p;//第一个结点的下一个结点指向第二个结点的下一个结点p->next=q_next;}

排序时候的代码，切记交换结点都是前后结点交换，所以交换完成后，L就已经被移动到下一个结点了，故不要再执行：L=L->next

//线性表的排序，交换结点voidListsort_Node(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//作为一个临时量Node*p;Node*p1;//如果链表为空直接返回if(head->value==0)return;intflag=0;cout<<head->value<<endl;for(i=0;i<head->value-1;i++){L=head->next;for(j=0;j<head->value-1-i;j++){//如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要//再执行：L=L->next;，否则会报错的if(L->value>L->next->value){flag=1;swap_node(head,j+1,j+2);}if(flag==1){flag=0;}else{L=L->next;}}}}

好了，今天的就写到这里了，今天通过写交换结点，发现链表真的很容易忽悠人，我就被忽悠了一个小时，才知道那个结点已经被移动到下一个结点了。

最后，补充一个实现链表反转的好方法（感觉你在头文件里面计算一下链表的长度可以带来很多遍历的）

voidrollback(Node*&head){//先知道了最后一个元素和第一个元素的位置intend=head->value;intstart=1;//两边同时开工//进行调换while(1){if(end==start)return;swap_node(head,end,start);--end;++start;}}

希望大家，对我写的代码做出一些评价。我想想还是直接贴个完成的代码出来好了，调转代码也在里面了

include<iostream>#include<ctime>#include<cstdlib>#include<windows.h>#include<algorithm>usingnamespacestd;typedefintElemtype;//链式结构，我们打算在链表中添加一个//保存长度的头结点，加入这个结点可以方便我们对结点做一些//基本的操作，结点保存的是线性表的长度structNode{//结点的值,如果是头结点，保存是链表的长度Elemtypevalue;//下一个结点的地址Node*next;};//创建一个空链表，每个头结点就代表一个链表voidInitList(Node*&head){head=newNode();head->value=0;head->next=NULL;}//销毁一个链表voidDestroyList(Node*&head){deletehead;head=NULL;}//清空整个列表voidClearList(Node*&head){head->value=0;head->next=NULL;}//插入函数boolListinsert(Node*&head,inti,Elemtypevalue){//插入到前面的方法intj=0;Node*L=head;//如果插入的位置不合法，直接返回错误提示if(i<1||i>head->value+1)returnfalse;//得到插入位置的前一个结点while(j<i-1){L=L->next;++j;}//s是一个临时结点Node*s=newNode();s->value=value;//先对临时结点赋值s->next=L->next;//让临时结点下一个位置指向当前需要插入前一个结点的下一个位置L->next=s;//让前一个结点下一个位置指向临时结点，完成//线性表的长度加一++head->value;returntrue;}//得到某个位置上的值Node*getitem(Node*&head,inti){//我们要求程序返回特定位置上的值//我们一样是从头结点开始寻找该位置intj=0;Node*L=head;//想要的那个位置是否合法if(i<1||i>head->value)returnNULL;//同样是先得到前一个结点while(j<i-1){L=L->next;++j;}//value=L->next->value;returnL;}//线性表的排序,采用冒泡排序,直接遍历链表voidListsort(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//作为一个临时量Node*p;Node*p1;//如果链表为空直接返回if(head->value==0)return;for(i=0;i<head->value-1;i++){L=head->next;for(j=0;j<head->value-i-1;j++){//得到两个值p=L;p1=L->next;//如果前面的那个比后面的那个大，就交换它们之间的是数据域if(p->value>p1->value){Elemtypetemp=p->value;p->value=p1->value;p1->value=temp;}L=L->next;}}}//通过数组来完成我的排序voidListsort_by_array(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//如果链表为空直接返回if(head->value==0)return;Elemtype*copy=newElemtype[head->value];//变量链表，存放数组for(i=0;i<head->value;i++){L=L->next;copy[i]=L->value;}//调用STL中的sort函数sort(copy,copy+head->value);L=head;//存放回链表中for(i=0;i<head->value;i++){L=L->next;L->value=copy[i];}}//参数为头结点和需要交换的两个结点的位置（起点为1）voidswap_node(Node*&head,inti,intj){//位置不合法if(i<1||j<1||i>head->value||j>head->value){cout<<"请检查位置是否合法"<<endl;return;}//同一个位置不用交换if(i==j){return;}//相邻两个交换比较简单if(abs(i-j)==1){//位置靠前的那个结点的前一个结点Node*pre;if(i<j)pre=getitem(head,i);elsepre=getitem(head,j);//保存第一个结点Node*a=pre->next;//保存第二结点Node*b=a->next;//改变pre下一个结点的值pre->next=b;//必须先把b的下一个结点值给a先a->next=b->next;//让b的下一个结点等于ab->next=a;return;}//第一个结点前一个结点Node*a=getitem(head,i);//第二个结点的前一个结点Node*b=getitem(head,j);//第一个结点Node*p=a->next;//第二个结点Node*q=b->next;//第一个结点的下一个结点Node*p_next=p->next;//第二结点的下一个结点Node*q_next=q->next;//a的下一个结点指向第二个结点qa->next=q;//第二结点的下一个结点指向第一个结点的下一个结点q->next=p_next;//b的下一个结点指向第一个结点pb->next=p;//第一个结点的下一个结点指向第二个结点的下一个结点p->next=q_next;}//反转voidrollback(Node*&head){//先知道了最后一个元素和第一个元素的位置intend=head->value;intstart=1;//两边同时开工//进行调换while(1){if(end<=start)return;swap_node(head,end,start);--end;++start;}}voidprint(Node*&head);//线性表的排序,采用冒泡排序,直接遍历链表//线性表的排序，交换结点voidListsort_node(Node*&head){inti=0;intj=0;//用于变量链表Node*L=head;//作为一个临时量Node*p;Node*p1;//如果链表为空直接返回if(head->value==0)return;intflag=0;for(i=0;i<head->value-1;i++){L=head->next;for(j=0;j<head->value-1-i;j++){//如果我们交换了结点，那么我们就已经在交换结点的时候，把L移动到下一个结点了，所以不要//再执行：L=L->next;，否则会报错的if(L->value>L->next->value){flag=1;swap_node(head,j+1,j+2);}if(flag==1){flag=0;}else{L=L->next;}}}}voidprint(Node*&head){//输出我们只需要传入头结点，然后循环判断当前结点下一个结点是否为空，//这样就可以输出所有内容Node*L=head;while(L->next){L=L->next;cout<<L->value<<"";}cout<<endl;}intmain(){//链表的头结点，不存放任何值，首先初始化头结点Node*head;Node*head_array;Node*head_node;Node*head_roll;srand((int)time(NULL));//每次执行种子不同，生成不同的随机数//创建一个链表InitList(head);InitList(head_array);InitList(head_node);InitList(head_roll);inti;cout<<"请输入需要插入元素个数"<<endl;intn;cin>>n;//5//cout<<"请输入"<<n<<"个值"<<endl;for(i=0;i<n;i++){Elemtypetemp;temp=rand();if(!Listinsert(head,i+1,temp)){cout<<"插入元素失败"<<endl;}if(!Listinsert(head_array,i+1,temp)){cout<<"插入元素失败"<<endl;}if(!Listinsert(head_node,i+1,temp)){cout<<"插入元素失败"<<endl;}if(!Listinsert(head_roll,i+1,temp)){cout<<"插入元素失败"<<endl;}}cout<<"初始化结果"<<endl;print(head);cout<<"反转结果"<<endl;rollback(head_roll);print(head_roll);cout<<"冒泡排序（数据域交换）"<<endl;Listsort(head);print(head);cout<<"借数组为媒介进行排序（数据域交换）"<<endl;Listsort_by_array(head_array);print(head_array);cout<<"冒泡排序（结点交换）"<<endl;Listsort_node(head_node);print(head_node);system("pause");return0;}

运行环境：vs2015

输出结果：